Cvičenie 5 – Ďalšie dátové typy¶
Useful Files¶
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.
Navigation¶
- Úvod
- Krok 1: Možno
- Krok 2: Buď, alebo
- Krok 3: Strom aritmetických výrazov
- Krok 4: Rekurzívne typy
- Zdroje
Ú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:
Pri definovaní konkrétnej hodnoty bude typová premenná 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
Krok 1: Možno¶
Úloha 1.1 – safeHead, safeIndex¶
Definujte funkcie pre bezpečnú prácu so zoznamami:
V prípade, že zoznam je prázdny, alebo index je mimo rozsahu zoznamu, výsledok funkcií bude Nothing.
import Data.List ((!?))
safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x
safeIndex :: [a] -> Int -> Maybe a
safeIndex xs i = xs !? i
-- safeHead [1,2,3] = Just 1
-- safeHead [] = Nothing
-- safeIndex [1,2,3] 2 = Just 3
-- safeIndex [1,2,3] 7 = 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 – findBook, borrowerOf¶
Rozšírte riešenie úlohy z minulého cvičenia o ďalšie funkcie:
data LoanStatus
= Available
| Borrowed String -- meno osoby, ktorá si knihu požičala
deriving (Eq, Show)
data Book = Book
{ title :: String
, author :: String
, loanStatus :: LoanStatus
} deriving (Eq, Show)
library :: [Book]
library =
[ Book "Duna" "Frank Herbert" Available
, Book "1984" "George Orwell" (Borrowed "Jana")
, Book "Hobit" "J. R. R. Tolkien" (Borrowed "Peter")
]
findBook :: String -> [Book] -> Maybe Book
findBook t books = safeHead (filter hasTitle books)
where
hasTitle b = title b == t
borrowerOf :: String -> [Book] -> Maybe String
borrowerOf t books = case findBook t books of
Nothing -> Nothing
Just book -> case loanStatus book of
Available -> Nothing
Borrowed person -> Just person
-- findBook "Duna" library = Just (Book {title = "Duna", ...})
-- findBook "Dune" library = Nothing
-- borrowerOf "1984" library = Just "Jana"
-- borrowerOf "Duna" library = Nothing
findBook vyfiltruje knihy s daným názvom a z výsledku zoberie prvú pomocou safeHead — ak žiadna nie je, výsledok je Nothing. borrowerOf použije case dvakrát: najprv na výsledok hľadania a potom na stav vypožičania.
Úloha 1.3 – rozlíšenie chýb¶
Vieme pri borrowerOf rozlíšiť prípad, že kniha nie je v databáze alebo nie je vypožičaná?
-- Nie. borrowerOf vráti Nothing v oboch prípadoch: keď kniha v databáze nie je,
-- aj keď je dostupná. Rozlíšiť sa to dá cez Either:
borrowerOf' :: String -> [Book] -> Either String String
borrowerOf' t books = case findBook t books of
Nothing -> Left "kniha neexistuje"
Just book -> case loanStatus book of
Available -> Left "kniha nie je vypozicana"
Borrowed person -> Right person
-- borrowerOf' "1984" library = Right "Jana"
-- borrowerOf' "Duna" library = Left "kniha nie je vypozicana"
-- borrowerOf' "Dune" library = Left "kniha neexistuje"
Maybe vie povedať len „je výsledok / nie je výsledok". Either nesie v Left aj informáciu, prečo výsledok chýba.
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 – register¶
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í.
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ť.
register :: String -> String -> String
-> Either RegistrationError Account
register username passcode repeatedPasscode
| null username = Left EmptyUsername
| length passcode < 8 = Left (PasswordTooShort (length passcode))
| passcode /= repeatedPasscode = Left PasswordMismatch
| otherwise = Right (Account username passcode)
-- register "Jakub" "Janok123" "Janok123" = Right (Account {username = "Jakub", password = "Janok123"})
-- register "" "Janok123" "Janok123" = Left EmptyUsername
-- register "Jakub" "abc" "abc" = Left (PasswordTooShort 3)
-- register "Jakub" "Janok123" "Janok124" = Left PasswordMismatch
Strážcovia sa vyhodnocujú zhora nadol, takže sa vráti prvá chyba, ktorá nastane. PasswordTooShort nesie aj skutočnú dĺžku hesla. Ak neplatí žiadna chyba, spadne sa do otherwise a vráti sa Right s účtom.
Krok 3: Strom aritmetických výrazov¶
Úloha 3.1 – Expr¶
Definujte dátový typ pre reprezentáciu stromu aritmetických výrazov s operátormi +, -, *, /, unárnym mínus, a číslami typu Double.
Príklad
Obr. 1: Príklad stromu výrazu ((1*2)+(3-4))
data Expr = Num Double
| Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Expr
| Neg Expr
deriving Show
myExp = Add (Mul (Num 1) (Num 2)) (Sub (Num 3) (Num 4))
Typ je rekurzívny — Expr sa vyskytuje vo vlastných konštruktoroch. Num je list stromu, binárne operátory majú dva podvýrazy a Neg má jeden.
Úloha 3.2 – pretty¶
Definujte funkciu pretty, ktorá vytvorí textovú reprezentáciu výrazu (so zátvorkami).
Príklad
pretty :: Expr -> String
pretty (Num n) = showNum n
pretty (Neg n) = "(-" ++ pretty n ++ ")"
pretty (Add a b) = "(" ++ pretty a ++ " + " ++ pretty b ++ ")"
pretty (Sub a b) = "(" ++ pretty a ++ " - " ++ pretty b ++ ")"
pretty (Mul a b) = "(" ++ pretty a ++ " * " ++ pretty b ++ ")"
pretty (Div a b) = "(" ++ pretty a ++ " / " ++ pretty b ++ ")"
-- celé čísla vypíše bez .0 (1.0 -> "1")
showNum :: Double -> String
showNum x
| x == fromIntegral (round x :: Integer) = show (round x :: Integer)
| otherwise = show x
Pre každý konštruktor je jedna rovnica. Podvýrazy sa spracujú rekurzívne a obalia sa zátvorkami. Pomocná showNum zabezpečí, aby sa Num 1 vypísalo ako 1 a nie 1.0.
pretty myExp
-- = "(" ++ pretty (Mul (Num 1) (Num 2)) ++ " + " ++ pretty (Sub (Num 3) (Num 4)) ++ ")"
-- = "(" ++ "(1 * 2)" ++ " + " ++ "(3 - 4)" ++ ")"
-- = "((1 * 2) + (3 - 4))"
Úloha 3.3 – eval¶
Definujte funkciu eval, ktorá vypočíta zadaný výraz.
Príklad
eval :: Expr -> Double
eval (Num x) = x
eval (Add a b) = eval a + eval b
eval (Sub a b) = eval a - eval b
eval (Mul a b) = eval a * eval b
eval (Div a b) = eval a / eval b
eval (Neg a) = negate (eval a)
eval myExp
-- = eval (Mul (Num 1) (Num 2)) + eval (Sub (Num 3) (Num 4))
-- = (1 * 2) + (3 - 4)
-- = 2 + (-1)
-- = 1.0
Krok 4: Rekurzívne typy¶
Úloha 4.1 – BTree¶
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.
Príklad
Obr. 2: Príklad binárneho stromu
data BTree a = Leaf a
| Branch (BTree a) (BTree a)
deriving Show
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?
Na prednáške mal strom hodnoty v uzloch a prázdny list. Tu sú hodnoty iba v listoch (Leaf) a vetva (Branch) hodnotu nemá.
Úloha 4.2 – leafCount, contains, mapTree¶
Definujte funkcie pre prácu s takýmto stromom:
leafCount :: BTree a -> Int
contains :: Eq a => a -> BTree a -> Bool
mapTree :: (a -> b) -> BTree a -> BTree b
V pôvodnom zadaní je pri mapTree omylom Tree a, má byť BTree a.
leafCount :: BTree a -> Int
leafCount (Leaf _) = 1
leafCount (Branch l r) = leafCount l + leafCount r
contains :: Eq a => a -> BTree a -> Bool
contains y (Leaf x) = x == y
contains y (Branch l r) = contains y l || contains y r
mapTree :: (a -> b) -> BTree a -> BTree b
mapTree f (Leaf x) = Leaf (f x)
mapTree f (Branch l r) = Branch (mapTree f l) (mapTree f r)
-- leafCount myLittleTree = 4
-- contains 3 myLittleTree = True
-- contains 7 myLittleTree = False
-- mapTree (*10) myLittleTree = Branch (Branch (Leaf 10) (Branch (Leaf 20) (Leaf 30))) (Leaf 40)
Všetky tri funkcie majú rovnakú kostru: jedna rovnica pre Leaf (základný prípad) a jedna pre Branch, ktorá sa rekurzívne zavolá na oboch podstromoch. Líšia sa len tým, ako sa dva výsledky spoja (+, ||, nový Branch).
Úloha 4.3 – sumBTree¶
Definujte funkciu sumBTree pre výpočet súčtu hodnôt uložených v strome.
Príklad
sumBTree :: BTree Integer -> Integer
sumBTree (Leaf x) = x
sumBTree (Branch l r) = sumBTree l + sumBTree r
Úloha 4.4 – foldBTree¶
Definujte funkciu foldBTree, ktorá používa zadanú binárnu funkciu na výpočet hodnoty z údajov uložených v strome:
Príklad
foldBTree :: (a -> a -> a) -> BTree a -> a
foldBTree _ (Leaf x) = x
foldBTree f (Branch l r) = f (foldBTree f l) (foldBTree f r)
foldBTree je zovšeobecnenie sumBTree: namiesto pevného + dostane operáciu f ako parameter. Hodnotu v liste vráti, vetvy spojí pomocou f.
foldBTree (+) myLittleTree
-- = (foldBTree (+) (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3)))) + (foldBTree (+) (Leaf 4))
-- = (1 + (2 + 3)) + 4
-- = 10
sumBTree = foldBTree (+)