Skip to content

← Späť na FP Labs

Cvičenie 5 – Ďalšie dátové typy

Useful Files


Ciele

  1. Pochopiť význam typových parametrov a naučiť sa pracovať s parametrizovanými typmi.
  2. Naučiť sa pracovať s rekurzívnymi dátovými typmi.
  1. Úvod
  2. Krok 1: Možno
    1. Úloha 1.1 – safeHead, safeIndex
    2. Úloha 1.2 – findBook, borrowerOf
    3. Úloha 1.3 – rozlíšenie chýb
  3. Krok 2: Buď, alebo
    1. Úloha 2.1 – register
  4. Krok 3: Strom aritmetických výrazov
    1. Úloha 3.1 – Expr
    2. Úloha 3.2 – pretty
    3. Úloha 3.3 – eval
  5. Krok 4: Rekurzívne typy
    1. Úloha 4.1 – BTree
    2. Úloha 4.2 – leafCount, contains, mapTree
    3. Úloha 4.3 – sumBTree
    4. Úloha 4.4 – foldBTree
  6. 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:

data Maybe a = Just a | Nothing
data Either a b = Left a | Right b

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:

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.

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:

findBook   :: String -> [Book] -> Maybe Book
borrowerOf :: String -> [Book] -> Maybe String
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í.

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ť.
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.

data Expr = ...

Príklad

Príklad stromu výrazu ((1*2)+(3-4))

Obr. 1: Príklad stromu výrazu ((1*2)+(3-4))

myExp = Add (Mul (Num 1) (Num 2)) (Sub (Num 3) (Num 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).

pretty :: Expr -> String

Príklad

> pretty myExp
"((1 * 2) + (3 - 4))"
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.

eval :: Expr -> Double

Príklad

> eval myExp
1.0
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.

data BTree a = …

Príklad

Príklad binárneho stromu

Obr. 2: Príklad binárneho stromu

myLittleTree = Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))) (Leaf 4)
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.

sumBTree :: BTree Integer -> Integer

Príklad

> sumBTree myLittleTree
10
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:

foldBTree :: (a -> a -> a) -> BTree a -> a

Príklad

> foldBTree (+) myLittleTree
10
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 (+)

Zdroje

  1. Haskell – Data.Maybe
  2. Haskell – Data.List

Top