Ciele
- Pochopiť význam typových parametrov a naučiť sa pracovať s parametrizovanými typmi.
- Naučiť sa pracovať s rekurzívnymi dátovými typmi.
Úvod
Jednotlivé konštruktory môžu mať všeobecný parameter — typovú premennú, ten však musí byť označený aj v názve typu. To umožňuje definovať generické typy.
Napríklad, v štandardnej knižnici sú definované nasledovné parametrizované typy:
data Maybe a = Just a | Nothing
data Either a b = Left a | Right b
Pri definovaní konkrétnej hodnoty, typová premenná bude nahradená za konkrétny typ:
priklad1 :: Maybe Int
priklad1 = Just 5
priklad2 :: Either Int Char
priklad2 = Right 'a'
priklad3 :: Either (Maybe Int) [Bool]
priklad3 = Left Nothing
Postup
Krok 1: Možno
Úloha 1.1
Definujte funkcie pre bezpečnú prácu s zoznamami:
safeHead :: [a] -> Maybe a
safeIndex :: [a] -> Int -> Maybe a
V prípade, že zoznam je prázdny, alebo index je mimo rozsahu zoznamu, výsledok funkcií bude Nothing.
Poznámka
V knižnici Data.Maybe už existuje funkcia listToMaybe zodpovedajúca safeHead, a v Data.List je definovaný operátor !? zodpovedajúci safeIndex.
Úloha 1.2
Rozšírte riešenie úlohy z minulého cvičenia o ďalšie funkcie:
findBook :: String -> [Book] -> Maybe Book
borrowerOf :: String -> [Book] -> Maybe String
Úloha 1.3
Vieme pri borrowerOf rozlíšiť prípad, že kniha nie je v databáze alebo nie je vypožičaná?
Krok 2: Buď, alebo
Majme definované nasledovné typy reprezentujúce používateľský účet a rôzne dôvody zlyhania vytvárania účtu.
data Account = Account
{ username :: String
, password :: String
} deriving (Eq, Show)
data RegistrationError
= EmptyUsername
| PasswordTooShort Int
| PasswordMismatch
deriving (Eq, Show)
Úloha 2.1
Definujte funkciu register pre registráciu používateľa. Funkcia dostane používateľské meno, heslo a zopakované heslo. Jej výsledkom bude buď vytvorený účet, alebo typ chyby pri jeho vytváraní.
register :: String -> String -> String
-> Either RegistrationError Account
Nech pre účty platia tieto podmienky:
- používateľské meno nesmie byť prázdne,
- heslo musí mať aspoň 8 znakov,
- heslo a zopakované heslo sa musia zhodovať.
Krok 3: Strom aritmetických výrazov
Úloha 3.1
Definujte dátový typ pre reprezentáciu stromu aritmetických výrazov s operátormi +, - *, /, unárnym mínus, a číslami typu Double.
data Expr = ...
Príklad
((1*2)+(3-4))
myExp = Add (Mul (Num 1) (Num 2)) (Sub (Num 3) (Num 4))
Úloha 3.2
Definujte funkciu pretty, ktorá vytvori textovú reprezentáciu výrazu (so zátvorkami).
pretty :: Expr -> String
Príklad
> pretty myExp
"((1.0 * 2.0) + (3.0 - 4.0))"
Úloha 3.3
Definujte funkciu eval, ktorá vypočíta zadaný výraz.
eval :: Expr -> Double
Príklad
> eval myExp
1.0
Krok 4: Všeobecný binárny strom
Úloha 4.1
Definujte typ pre binárny strom, kde každý list stromu môže obsahovať hodnotu ľubovoľného typu. Ten je ale rovnaký pre všetky listy.
data BTree a = …
Príklad
myLittleTree = Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))) (Leaf 4)
Poznámka
Príklad podobného typu sme mali aj na prednáške. Ako sa odlišuje od typu definovaného tu?
Úloha 4.2
Definujte funkcie pre prácu s takýmto stromom:
leafCount :: BTree a -> Int
contains :: Eq a => a -> BTree a -> Bool
mapBTree :: (a -> b) -> BTree a -> BTree b
Úloha 4.3
Definujte funkciu sumBTree pre výpočet súčtu hodnôt uložených v strome.
sumBTree :: BTree Integer -> Integer
Príklad
> sumBTree myLittleTree
10
Úloha 4.4
Definujte funkciu foldBtree, ktorá používa zadanú binárnu funkciu na výpočet hodnoty z údajov uložených v strome:
foldBTree :: (a -> a -> a) -> BTree a -> a
Príklad
> foldBTree (+) myLittleTree
10