Skip to content

← Späť na Exercises

Haskell – úlohy na 2. písomku

Useful Files

  1. Úroveň 1 – vlastné dátové typy a record syntax
    1. Úloha 1.1 – dni v týždni
    2. Úloha 1.2 – predchádzajúci deň
    3. Úloha 1.3 – obvod útvaru
    4. Úloha 1.4 – posun útvaru
    5. Úloha 1.5 – študent (record syntax)
    6. Úloha 1.6 – knižnica
    7. Úloha 1.7 – farba a case
  2. Úroveň 2 – Maybe a Either
    1. Úloha 2.1 – bezpečné funkcie nad zoznamom
    2. Úloha 2.2 – bezpečné delenie
    3. Úloha 2.3 – hľadanie knihy
    4. Úloha 2.4 – predvolená hodnota
    5. Úloha 2.5 – telefónny zoznam s lookup
    6. Úloha 2.6 – načítanie veku cez Either
    7. Úloha 2.7 – výber z účtu
    8. Úloha 2.8 – Maybe alebo Either?
    9. Úloha 2.9 – spracovanie Either
  3. Úroveň 3 – rekurzívne typy a stromy
    1. Úloha 3.1 – aritmetický výraz
    2. Úloha 3.2 – počet operátorov a čísla vo výraze
    3. Úloha 3.3 – binárny strom s hodnotami v listoch
    4. Úloha 3.4 – binárny vyhľadávací strom
    5. Úloha 3.5 – vlastný zoznam
  4. Úroveň 4 – typové triedy
    1. Úloha 4.1 – aký je typ?
    2. Úloha 4.2 – vlastný Show
    3. Úloha 4.3 – zlomky: Eq, Ord a Show
    4. Úloha 4.4 – Eq pre strom
    5. Úloha 4.5 – vlastná typová trieda
    6. Úloha 4.6 – trieda Movable (cvičenie 6)
    7. Úloha 4.7 – Functor
    8. Úloha 4.8 – Foldable
    9. Úloha 4.9 – deriving Ord pri enumerácii
  5. Úroveň 5 – vstup a výstup (IO)
    1. Úloha 5.1 – pozdrav dvoma spôsobmi
    2. Úloha 5.2 – súčet dvoch čísel
    3. Úloha 5.3 – načítanie čísla s opakovaním
    4. Úloha 5.4 – dotazník
    5. Úloha 5.5 – očíslovaný výpis
    6. Úloha 5.6 – opakuj, kým nepríde „koniec“
    7. Úloha 5.7 – súčet čísel do prázdneho riadku
    8. Úloha 5.8 – štatistika súboru
    9. Úloha 5.9 – súčet argumentov programu
    10. Úloha 5.10 – prepis z >>= do do
  6. Úroveň 6 – monády Maybe, Either a zoznam
    1. Úloha 6.1 – reťazenie delení
    2. Úloha 6.2 – reťazenie lookup (prednáška 7)
    3. Úloha 6.3 – Either v do
    4. Úloha 6.4 – bezpečné vyhodnotenie výrazu
    5. Úloha 6.5 – zoznamová monáda
    6. Úloha 6.6 – mapM s Maybe
    7. Úloha 6.7 – čo vráti fmap?
  7. Úroveň 7 – jazyk lambda
    1. Úloha 7.1 – voľné a viazané premenné
    2. Úloha 7.2 – beta redukcia
    3. Úloha 7.3 – lambda v Haskelli
    4. Úloha 7.4 – Churchove pravdivostné hodnoty
  8. Písomky nanečisto
    1. Písomka A
      1. Úloha A1 – teplota
      2. Úloha A2 – bezpečné maximum
      3. Úloha A3 – väčšie z dvoch čísel
    2. Písomka B
      1. Úloha B1 – strom s hodnotami v uzloch
      2. Úloha B2 – peniaze
      3. Úloha B3 – prepis do >>=
    3. Písomka C
      1. Úloha C1 – produkty
      2. Úloha C2 – kontrola hesla
      3. Úloha C3 – dotazník s výpisom
    4. Písomka D
      1. Úloha D1 – Functor a Ord
      2. Úloha D2 – Foldable pre vlastný zoznam
      3. Úloha D3 – typy

Úlohy pokrývajú cvičenia 4 až 7 a prednášky 4 až 7: vlastné dátové typy, record syntax, Maybe a Either, rekurzívne typy a stromy, typové triedy, Functor a Foldable, vstup a výstup a monády.

Písomka trvá 10 až 15 minút a má 2 až 3 príklady na papier. Úlohy sú preto krátke, aby si si zvykol napísať syntax naspamäť. Všetky riešenia sú overené v GHC 9.4.

Ako s tým pracovať

  • Každú úlohu najprv napíš na papier bez počítača, až potom ju over v GHCi (ghci subor.hs, po zmene :r).
  • Vždy začni typovou signatúrou a definíciou typu data.
  • Riešenie si otvor až potom, keď máš vlastný pokus. Často je ich viac, porovnaj si ich.
  • Na konci sú štyri písomky nanečisto. Na každú si nastav časovač na 15 minút.

Úroveň 1 – vlastné dátové typy a record syntax

Cvičenie 4. Definícia data, porovnávanie vzorov s konštruktormi, deriving, record syntax a jej úprava.

Úloha 1.1 – dni v týždni

Definuj typ Day so siedmimi konštruktormi Mon až Sun. Napíš isWeekend a nextDayOfWeek.

data Day = ...

isWeekend     :: Day -> Bool
nextDayOfWeek :: Day -> Day

isWeekend Sat     == True
isWeekend Mon     == False
nextDayOfWeek Sun == Mon

Riešenie

data Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun
  deriving (Show, Eq)

-- a) vzory
isWeekend :: Day -> Bool
isWeekend Sat = True
isWeekend Sun = True
isWeekend _   = False

-- b) porovnanie (potrebuje deriving Eq)
isWeekend' :: Day -> Bool
isWeekend' d = d == Sat || d == Sun

-- c) elem (tiež potrebuje Eq)
isWeekend'' :: Day -> Bool
isWeekend'' d = d `elem` [Sat, Sun]

nextDayOfWeek :: Day -> Day
nextDayOfWeek Mon = Tue
nextDayOfWeek Tue = Wed
nextDayOfWeek Wed = Thu
nextDayOfWeek Thu = Fri
nextDayOfWeek Fri = Sat
nextDayOfWeek Sat = Sun
nextDayOfWeek Sun = Mon

Konštruktory bez parametrov tvoria enumeráciu. Vo verzii a) stačí porovnávanie vzorov a _ zachytí zvyšok. Verzie b) a c) používajú ==, preto bez deriving (Eq) neprejdú kompiláciou. Show treba, aby GHCi vedelo hodnotu vypísať.

Úloha 1.2 – predchádzajúci deň

Máš typ Date a funkciu daysInMonth z cvičenia 4. Napíš prevDay, opak nextDay.

data Date = Date Int Int Int    -- rok mesiac deň
  deriving (Show, Eq)

daysInMonth :: Int -> Int -> Int   -- daná, rok -> mesiac -> počet dní

prevDay :: Date -> Date

prevDay (Date 2024 3 1)  == Date 2024 2 29
prevDay (Date 2025 1 1)  == Date 2024 12 31
prevDay (Date 2025 5 15) == Date 2025 5 14

Riešenie

prevDay :: Date -> Date
prevDay (Date y m d)
  | d > 1     = Date y m (d - 1)
  | m == 1    = Date (y - 1) 12 31
  | otherwise = Date y (m - 1) (daysInMonth y (m - 1))

Vzor (Date y m d) rozloží dátum na tri čísla. Strážcovia idú od najčastejšieho prípadu: bežný deň, potom 1. január a nakoniec prvý deň iného mesiaca. Posledný deň predchádzajúceho mesiaca zistí daysInMonth.

Úloha 1.3 – obvod útvaru

Rozšír Shape z cvičenia o trojuholník a napíš perimeter.

data Point = Point Double Double deriving (Show, Eq)

data Shape = Circle Point Double
           | Rectangle Point Point
           | Triangle Point Point Point
           deriving (Show, Eq)

perimeter :: Shape -> Double

perimeter (Rectangle (Point 0 0) (Point 10 5))         == 30
perimeter (Triangle (Point 0 0) (Point 3 0) (Point 3 4)) == 12

Riešenie

perimeter :: Shape -> Double
perimeter (Circle _ r) = 2 * pi * r
perimeter (Rectangle (Point x1 y1) (Point x2 y2)) =
  2 * (abs (x2 - x1) + abs (y2 - y1))
perimeter (Triangle a b c) = dist a b + dist b c + dist c a
  where
    dist (Point x1 y1) (Point x2 y2) = sqrt ((x2 - x1)^2 + (y2 - y1)^2)

Každý konštruktor má vlastnú rovnicu. Vzory môžu byť vnorené, napríklad (Rectangle (Point x1 y1) (Point x2 y2)) rozloží útvar aj oba body naraz. Pomocná funkcia dist vo where rozkladá body priamo vo svojich parametroch.

Úloha 1.4 – posun útvaru

data Vector = Vec Double Double deriving (Show, Eq)

move :: Vector -> Shape -> Shape

move (Vec 1 2) (Circle (Point 0 0) 5) == Circle (Point 1 2) 5
move (Vec 1 1) (Rectangle (Point 0 0) (Point 2 2))
  == Rectangle (Point 1 1) (Point 3 3)

Riešenie

move :: Vector -> Shape -> Shape
move v (Circle c r)     = Circle (movePoint v c) r
move v (Rectangle a b)  = Rectangle (movePoint v a) (movePoint v b)
move v (Triangle a b c) = Triangle (movePoint v a) (movePoint v b) (movePoint v c)

movePoint :: Vector -> Point -> Point
movePoint (Vec dx dy) (Point x y) = Point (x + dx) (y + dy)

Posun útvaru znamená posunúť všetky jeho body. Výsledkom je nová hodnota, pôvodný útvar sa nemení. Polomer kruhu zostane rovnaký.

Úloha 1.5 – študent (record syntax)

data Student = Student
  { name   :: String
  , points :: Int
  } deriving (Show, Eq)

passed      :: Student -> Bool        -- aspoň 51 bodov
passedNames :: [Student] -> [String]
addPoints   :: Int -> Student -> Student

passedNames [Student "Eva" 72, Student "Adam" 43] == ["Eva"]
addPoints 10 (Student "Adam" 43) == Student "Adam" 53

Riešenie

passed :: Student -> Bool
passed s = points s >= 51

passedNames :: [Student] -> [String]
passedNames ss = map name (filter passed ss)

-- alternatíva: množinová abstrakcia
passedNames' ss = [name s | s <- ss, passed s]

addPoints :: Int -> Student -> Student
addPoints n s = s { points = points s + n }

-- alternatíva bez record syntaxe
addPointsPM n (Student nm p) = Student nm (p + n)

Record syntax vygeneruje funkcie name a points, ktoré vrátia hodnotu poľa. Zápis s { points = ... } vytvorí kópiu s so zmeneným jedným poľom, ostatné polia zostanú. Hodnota sa dá vytvoriť aj pozične, Student "Eva" 72.

Úloha 1.6 – knižnica

Typy z cvičenia 4:

data LoanStatus = Available | Borrowed String
  deriving (Eq, Show)

data Book = Book
  { title      :: String
  , author     :: String
  , loanStatus :: LoanStatus
  } deriving (Eq, Show)

availableTitles :: [Book] -> [String]
borrowedBy      :: String -> [Book] -> [Book]
returnBook      :: Book -> Book
borrowBook      :: String -> Book -> Maybe Book   -- Nothing, ak je už požičaná

Riešenie

availableTitles :: [Book] -> [String]
availableTitles bs = [title b | b <- bs, loanStatus b == Available]

borrowedBy :: String -> [Book] -> [Book]
borrowedBy who bs = filter byWho bs
  where
    byWho b = loanStatus b == Borrowed who

returnBook :: Book -> Book
returnBook b = b { loanStatus = Available }

borrowBook :: String -> Book -> Maybe Book
borrowBook who b = case loanStatus b of
  Available  -> Just b { loanStatus = Borrowed who }
  Borrowed _ -> Nothing

Borrowed who je hodnota typu LoanStatus, takže sa dá porovnať cez ==, lebo typ má deriving Eq. V borrowBook rozhoduje case o stave knihy. Just b { ... } sa číta ako Just (b { ... }), pretože úprava záznamu viaže silnejšie ako aplikácia funkcie.

Úloha 1.7 – farba a case

data Color = Red | Green | Blue deriving (Show, Eq)

toHex :: Color -> String

toHex Green == "#00FF00"

Riešenie

toHex :: Color -> String
toHex c = case c of
  Red   -> "#FF0000"
  Green -> "#00FF00"
  Blue  -> "#0000FF"

case robí to isté ako viac rovníc so vzormi, ale dá sa použiť aj vnútri výrazu. Za každým vzorom nasleduje ->, nie =, a vetvy musia byť odsadené rovnako.


Úroveň 2 – Maybe a Either

Cvičenie 5. Funkcia nemusí vždy vrátiť výsledok (Maybe), alebo vráti výsledok či chybu (Either).

Úloha 2.1 – bezpečné funkcie nad zoznamom

safeHead  :: [a] -> Maybe a
safeLast  :: [a] -> Maybe a
safeIndex :: [a] -> Int -> Maybe a

safeHead [1,2,3]     == Just 1
safeLast ""          == Nothing
safeIndex [10,20,30] 2 == Just 30
safeIndex [10,20,30] 7 == Nothing

Riešenie

safeHead :: [a] -> Maybe a
safeHead []    = Nothing
safeHead (x:_) = Just x

safeLast :: [a] -> Maybe a
safeLast []     = Nothing
safeLast [x]    = Just x
safeLast (_:xs) = safeLast xs

safeIndex :: [a] -> Int -> Maybe a
safeIndex [] _ = Nothing
safeIndex (x:xs) i
  | i < 0     = Nothing
  | i == 0    = Just x
  | otherwise = safeIndex xs (i - 1)

Kde by obyčajná funkcia spadla, vráti sa Nothing, inak Just s výsledkom. V safeLast je vzor [x] (presne jeden prvok) pred (_:xs), inak by sa nikdy nepoužil.

V novšom GHC existuje listToMaybe z Data.Maybe (to isté ako safeHead) a operátor !? z Data.List (to isté ako safeIndex).

Úloha 2.2 – bezpečné delenie

safeDiv :: Int -> Int -> Maybe Int

safeDiv 10 3 == Just 3
safeDiv 1 0  == Nothing

Riešenie

safeDiv :: Int -> Int -> Maybe Int
safeDiv _ 0 = Nothing
safeDiv a b = Just (a `div` b)

Číslo 0 sa dá použiť priamo ako vzor. Táto funkcia sa ešte vráti v úrovni 6.

Úloha 2.3 – hľadanie knihy

Typy Book a LoanStatus z úlohy 1.6.

findBook   :: String -> [Book] -> Maybe Book
borrowerOf :: String -> [Book] -> Maybe String

borrowerOf "1984" library == Just "Jana"
borrowerOf "Duna" library == Nothing     -- dostupná
borrowerOf "X"    library == Nothing     -- neexistuje

Riešenie

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 nechá knihy s daným názvom a zoberie prvú. borrowerOf rozbalí Maybe cez case a potom ešte raz rozhodne podľa stavu. Toto vnorené case sa v úrovni 6 zjednoduší cez do.

Úloha 2.4 – predvolená hodnota

Vráť autora knihy, alebo "neznamy", ak kniha neexistuje.

authorOf :: String -> [Book] -> String

authorOf "Hobit" library == "J. R. R. Tolkien"
authorOf "X" library     == "neznamy"

Riešenie

-- a) case
authorOf t books = case findBook t books of
  Nothing -> "neznamy"
  Just b  -> author b

-- b) maybe  náhrada  funkcia  hodnota
authorOf t books = maybe "neznamy" author (findBook t books)

-- c) fromMaybe z Data.Maybe + fmap
authorOf t books = fromMaybe "neznamy" (fmap author (findBook t books))

maybe d f m vráti d pri Nothing a f x pri Just x. fromMaybe d m vráti d alebo vybalenú hodnotu. fmap author zmení Maybe Book na Maybe String bez rozbaľovania.

Úloha 2.5 – telefónny zoznam s lookup

phone :: String -> [(String, String)] -> String

phone "Eva" [("Eva", "0901 111 222")] == "0901 111 222"
phone "Mia" [("Eva", "0901 111 222")] == "cislo nenajdene"

Riešenie

phone :: String -> [(String, String)] -> String
phone who book = case lookup who book of
  Just num -> num
  Nothing  -> "cislo nenajdene"

lookup :: Eq a => a -> [(a, b)] -> Maybe b hľadá kľúč v zozname dvojíc. Je to najčastejší zdroj Maybe v štandardnej knižnici.

Úloha 2.6 – načítanie veku cez Either

Ak reťazec nie je číslo, vráť Left "nie je cislo". Ak je záporný, vráť Left "zaporny vek". Inak vráť Right s vekom.

import Text.Read (readMaybe)

parseAge :: String -> Either String Int

parseAge "25"  == Right 25
parseAge "abc" == Left "nie je cislo"
parseAge "-3"  == Left "zaporny vek"

Riešenie

parseAge :: String -> Either String Int
parseAge s = case readMaybe s of
  Nothing -> Left "nie je cislo"
  Just n
    | n < 0     -> Left "zaporny vek"
    | otherwise -> Right n

readMaybe vráti Maybe Int, pretože typ Int sa odvodí zo signatúry. Vo vetve case sa dajú použiť aj strážcovia |. Left nesie chybu, Right úspešný výsledok („right“ znamená aj „správny“).

Úloha 2.7 – výber z účtu

data WithdrawError
  = InvalidAmount
  | InsufficientFunds Double     -- koľko chýba
  deriving (Eq, Show)

withdraw :: Double -> Double -> Either WithdrawError Double
--          suma      zostatok  -> nový zostatok

withdraw 30 100  == Right 70
withdraw 0 100   == Left InvalidAmount
withdraw 150 100 == Left (InsufficientFunds 50)

Riešenie

withdraw :: Double -> Double -> Either WithdrawError Double
withdraw amount balance
  | amount <= 0      = Left InvalidAmount
  | amount > balance = Left (InsufficientFunds (amount - balance))
  | otherwise        = Right (balance - amount)

Rovnaký vzor ako register z cvičenia 5: strážcovia kontrolujú chyby zhora nadol a vráti sa prvá, ktorá nastane. Chyba je vlastný typ, takže môže niesť údaje, napríklad chýbajúcu sumu.

Úloha 2.8 – Maybe alebo Either?

borrowerOf vráti Nothing, keď kniha neexistuje, aj keď je dostupná. Uprav ju tak, aby sa tieto prípady dali rozlíšiť.

borrowerOfE :: String -> [Book] -> Either String String

borrowerOfE "1984" library == Right "Jana"
borrowerOfE "Duna" library == Left "kniha nie je vypozicana"
borrowerOfE "Dune" library == Left "kniha neexistuje"

Riešenie

borrowerOfE :: String -> [Book] -> Either String String
borrowerOfE 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

Maybe povie len „je výsledok“ alebo „nie je“. Either v Left povie aj prečo výsledok chýba.

Úloha 2.9 – spracovanie Either

Z výsledku parseAge vyrob text.

describeAge :: String -> String

describeAge "25" == "Vek: 25"
describeAge "x"  == "Chyba: nie je cislo"

Riešenie

-- a) case
describeAge s = case parseAge s of
  Left err -> "Chyba: " ++ err
  Right n  -> "Vek: " ++ show n

-- b) either  fLeft  fRight  hodnota
describeAge s = either ("Chyba: " ++) (\n -> "Vek: " ++ show n) (parseAge s)

either je pre Either to isté, čo maybe pre Maybe. Dostane funkciu pre Left, funkciu pre Right a hodnotu.


Úroveň 3 – rekurzívne typy a stromy

Cvičenie 5. Typ, ktorý sa vyskytuje vo vlastných konštruktoroch. Funkcia nad ním má jednu rovnicu na každý konštruktor.

Úloha 3.1 – aritmetický výraz

Definuj typ pre výrazy s celými číslami, +, -, * a unárnym mínusom. Napíš eval a pretty.

data Expr = ...

myExp = Add (Mul (Num 1) (Num 2)) (Sub (Num 3) (Num 4))

eval   :: Expr -> Int
pretty :: Expr -> String

eval myExp   == 1
pretty myExp == "((1 * 2) + (3 - 4))"

Riešenie

data Expr = Num Int
          | Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Neg Expr
          deriving Show

eval :: Expr -> Int
eval (Num n)   = n
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 (Neg a)   = negate (eval a)

pretty :: Expr -> String
pretty (Num n)   = show n
pretty (Add a b) = bin "+" a b
pretty (Sub a b) = bin "-" a b
pretty (Mul a b) = bin "*" a b
pretty (Neg a)   = "(-" ++ pretty a ++ ")"

bin :: String -> Expr -> Expr -> String
bin op a b = "(" ++ pretty a ++ " " ++ op ++ " " ++ pretty b ++ ")"

Num je list, binárne operátory majú dva podvýrazy a Neg jeden. Každá rovnica najprv rekurzívne spracuje podvýrazy a potom ich výsledky spojí. Pomocná bin odstráni opakovanie v pretty.

V cvičení je výraz s Double a operáciou Div, kostra riešenia je rovnaká.

Úloha 3.2 – počet operátorov a čísla vo výraze

countOps :: Expr -> Int
numbers  :: Expr -> [Int]

countOps myExp == 3
numbers myExp  == [1,2,3,4]

Riešenie

countOps :: Expr -> Int
countOps (Num _)   = 0
countOps (Add a b) = 1 + countOps a + countOps b
countOps (Sub a b) = 1 + countOps a + countOps b
countOps (Mul a b) = 1 + countOps a + countOps b
countOps (Neg a)   = 1 + countOps a

numbers :: Expr -> [Int]
numbers (Num n)   = [n]
numbers (Add a b) = numbers a ++ numbers b
numbers (Sub a b) = numbers a ++ numbers b
numbers (Mul a b) = numbers a ++ numbers b
numbers (Neg a)   = numbers a

Kostra je rovnaká ako pri eval. Mení sa len to, čo vráti list a ako sa spoja výsledky podvýrazov.

Úloha 3.3 – binárny strom s hodnotami v listoch

data BTree a = Leaf a
             | Branch (BTree a) (BTree a)
             deriving Show

myLittleTree = Branch (Branch (Leaf 1) (Branch (Leaf 2) (Leaf 3))) (Leaf 4)

leafCount :: BTree a -> Int
depth     :: BTree a -> Int          -- list má hĺbku 1
toList    :: BTree a -> [a]
contains  :: Eq a => a -> BTree a -> Bool
mapTree   :: (a -> b) -> BTree a -> BTree b
foldBTree :: (a -> a -> a) -> BTree a -> a
mirror    :: BTree a -> BTree a      -- vymení ľavú a pravú vetvu

leafCount myLittleTree     == 4
depth myLittleTree         == 4
toList myLittleTree        == [1,2,3,4]
foldBTree (+) myLittleTree == 10
toList (mirror myLittleTree) == [4,3,2,1]

Riešenie

leafCount :: BTree a -> Int
leafCount (Leaf _)     = 1
leafCount (Branch l r) = leafCount l + leafCount r

depth :: BTree a -> Int
depth (Leaf _)     = 1
depth (Branch l r) = 1 + max (depth l) (depth r)

toList :: BTree a -> [a]
toList (Leaf x)     = [x]
toList (Branch l r) = toList l ++ toList 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)

foldBTree :: (a -> a -> a) -> BTree a -> a
foldBTree _ (Leaf x)     = x
foldBTree f (Branch l r) = f (foldBTree f l) (foldBTree f r)

sumBTree = foldBTree (+)     -- súčet
maxBTree = foldBTree max     -- maximum

mirror :: BTree a -> BTree a
mirror (Leaf x)     = Leaf x
mirror (Branch l r) = Branch (mirror r) (mirror l)

Všetky funkcie majú rovnakú kostru: rovnica pre Leaf (základný prípad) a rovnica pre Branch, ktorá sa zavolá na oba podstromy. Líšia sa len tým, čím sa spoja dva výsledky: +, max, ++, || alebo nový Branch.

contains má obmedzenie Eq a, lebo porovnáva hodnoty. mapTree mení typ hodnôt, preto má výsledok typ BTree b.

Úloha 3.4 – binárny vyhľadávací strom

Strom s hodnotami v uzloch, ako na prednáške. Vľavo sú menšie hodnoty, vpravo väčšie.

data Tree a = Empty
            | Node (Tree a) a (Tree a)
            deriving Show

insert   :: Ord a => a -> Tree a -> Tree a
member   :: Ord a => a -> Tree a -> Bool
inorder  :: Tree a -> [a]
size     :: Tree a -> Int
fromList :: Ord a => [a] -> Tree a

inorder (fromList [5,2,8,1,9,2]) == [1,2,5,8,9]
member 8 (fromList [5,2,8])      == True

Riešenie

insert :: Ord a => a -> Tree a -> Tree a
insert x Empty = Node Empty x Empty
insert x (Node l v r)
  | x < v     = Node (insert x l) v r
  | x > v     = Node l v (insert x r)
  | otherwise = Node l v r              -- duplicita sa nevkladá

member :: Ord a => a -> Tree a -> Bool
member _ Empty = False
member x (Node l v r)
  | x < v     = member x l
  | x > v     = member x r
  | otherwise = True

inorder :: Tree a -> [a]
inorder Empty        = []
inorder (Node l v r) = inorder l ++ [v] ++ inorder r

size :: Tree a -> Int
size Empty        = 0
size (Node l _ r) = size l + 1 + size r

fromList :: Ord a => [a] -> Tree a
fromList xs = foldr insert Empty xs

Rozdiel oproti BTree: tu je hodnota v uzle, list (Empty) je prázdny. insert nemení strom, vráti nový strom s vloženým prvkom. Ord a je potrebné kvôli < a >. inorder vráti prvky zoradené.

Úloha 3.5 – vlastný zoznam

data List a = Nil | Cons a (List a)
  deriving Show

lengthL   :: List a -> Int
toHList   :: List a -> [a]
fromHList :: [a] -> List a

lengthL (fromHList "abc") == 3
toHList (Cons 1 (Cons 2 Nil)) == [1,2]

Riešenie

lengthL :: List a -> Int
lengthL Nil         = 0
lengthL (Cons _ xs) = 1 + lengthL xs

toHList :: List a -> [a]
toHList Nil         = []
toHList (Cons x xs) = x : toHList xs

fromHList :: [a] -> List a
fromHList []     = Nil
fromHList (x:xs) = Cons x (fromHList xs)

-- alebo: Cons nahradí (:), Nil nahradí []
fromHList' = foldr Cons Nil

Vstavaný zoznam je presne takýto typ: Nil je [] a Cons je :. Preto sa rekurzia nad List píše rovnako ako nad obyčajným zoznamom.


Úroveň 4 – typové triedy

Cvičenie 6. Obmedzenia v typoch (Eq a =>), vlastné inštancie, vlastná trieda, Functor a Foldable.

Úloha 4.1 – aký je typ?

Napíš najvšeobecnejší typ funkcie. Typ si over v GHCi cez :t.

allEqual []     = True
allEqual (x:xs) = all (== x) xs

f1 x y   = x == y && x > 0
f2 xs    = concatMap show xs
g x      = x + 1
h x y    = [x, y]
k f xs   = map f (filter (> 0) xs)
m x      = fmap (+1) x

Riešenie

allEqual :: Eq a => [a] -> Bool
f1       :: (Ord a, Num a) => a -> a -> Bool
f2       :: Show a => [a] -> String
g        :: Num a => a -> a
h        :: a -> a -> [a]
k        :: (Ord a, Num a) => (a -> b) -> [a] -> [b]
m        :: (Functor f, Num b) => f b -> f b

Pravidlo: každá operácia, ktorú funkcia použije, pridá obmedzenie. == pridá Eq, > a < pridajú Ord, + a číselný literál 0 pridajú Num, show pridá Show a fmap pridá Functor.

Ord je podtrieda Eq, takže pri f1 stačí Ord a, netreba písať (Eq a, Ord a). h nič nepoužíva, preto nemá žiadne obmedzenie. Ide o parametrický polymorfizmus.

GHCi niekedy ukáže všeobecnejší typ s Foldable t => t a namiesto [a]. Pre zoznamy sú oba zápisy správne.

Úloha 4.2 – vlastný Show

Vypíš farby po slovensky.

data Color = Red | Green | Blue

show [Red, Blue] == "[cervena,modra]"

Riešenie

instance Show Color where
  show Red   = "cervena"
  show Green = "zelena"
  show Blue  = "modra"

Typ nesmie mať zároveň deriving Show, inak vzniknú dve inštancie a kompilácia zlyhá. Zoznam farieb sa vypíše sám, pretože Show [a] už existuje pre každé a zo Show.

Úloha 4.3 – zlomky: Eq, Ord a Show

Frac 1 2 a Frac 2 4 sú ten istý zlomok. Predpokladaj kladné menovatele.

data Fraction = Frac Int Int

Frac 1 2 == Frac 2 4                    -- True
Frac 1 3 < Frac 1 2                     -- True
maximum [Frac 1 2, Frac 3 4, Frac 2 3]  -- 3/4
show (Frac 3 4)                         -- "3/4"

Riešenie

instance Eq Fraction where
  Frac a b == Frac c d = a * d == c * b

instance Ord Fraction where
  compare (Frac a b) (Frac c d) = compare (a * d) (c * b)

instance Show Fraction where
  show (Frac a b) = show a ++ "/" ++ show b

Pre Eq stačí definovať ==, lebo /= má predvolenú definíciu v triede. Pre Ord stačí compare (vracia LT, EQ alebo GT). Z neho sa odvodí <, >, max, maximum aj sort.

Ord vyžaduje, aby typ mal aj Eq, lebo Eq je jeho nadtrieda. Krížové násobenie a * d == c * b porovná zlomky bez delenia.

Úloha 4.4 – Eq pre strom

data BTree a = Leaf a | Branch (BTree a) (BTree a)

Branch (Leaf 1) (Leaf 2) == Branch (Leaf 1) (Leaf 2)   -- True
Leaf 1 == Branch (Leaf 1) (Leaf 1)                     -- False

Riešenie

instance Eq a => Eq (BTree a) where
  Leaf a       == Leaf b       = a == b
  Branch l1 r1 == Branch l2 r2 = l1 == l2 && r1 == r2
  _            == _            = False

Eq a => pred inštanciou znamená, že strom vieme porovnať, len keď vieme porovnať jeho prvky (a == b). Bez tohto obmedzenia kompilácia zlyhá. Posledná rovnica _ == _ pokryje porovnanie listu s vetvou.

Úloha 4.5 – vlastná typová trieda

Definuj triedu HasArea s metódou area a predvolenou metódou describe. Urob inštancie pre štvorec a kruh.

data Square = Square Double
data Circ   = Circ Double

area (Square 3)       == 9.0
describe (Square 2)   == "utvar s obsahom 4.0"
totalArea [Square 1, Square 2] == 5.0

Riešenie

class HasArea a where
  area     :: a -> Double
  describe :: a -> String
  describe x = "utvar s obsahom " ++ show (area x)   -- predvolená

instance HasArea Square where
  area (Square s) = s * s

instance HasArea Circ where
  area (Circ r) = pi * r * r
  describe c = "kruh s obsahom " ++ show (area c)    -- prepísaná

totalArea :: HasArea a => [a] -> Double
totalArea xs = sum (map area xs)

class iba deklaruje, čo má typ vedieť. Typy metód obsahujú premennú a z hlavičky triedy. instance dodá implementáciu pre konkrétny typ. Predvolenú metódu (describe) inštancia nemusí písať, ale môže ju prepísať.

totalArea funguje pre zoznam štvorcov alebo zoznam kruhov, nie pre zoznam, v ktorom sú oba. Zoznam v Haskelli obsahuje prvky jedného typu.

Úloha 4.6 – trieda Movable (cvičenie 6)

class Movable a where
  move      :: Vector -> a -> a
  reflectX  :: a -> a
  reflectY  :: a -> a
  rotate180 :: a -> a

-- inštancie pre Point a Shape (Circle, Rectangle)
rotate180 (Point 3 4) == Point (-3) (-4)

Riešenie

class Movable a where
  move      :: Vector -> a -> a
  reflectX  :: a -> a
  reflectY  :: a -> a
  rotate180 :: a -> a
  rotate180 = reflectX . reflectY

instance Movable Point where
  move (Vec dx dy) (Point x y) = Point (x + dx) (y + dy)
  reflectX (Point x y)         = Point x (-y)
  reflectY (Point x y)         = Point (-x) y

instance Movable Shape where
  move v (Circle c r)      = Circle (move v c) r
  move v (Rectangle a b)   = Rectangle (move v a) (move v b)
  reflectX (Circle c r)    = Circle (reflectX c) r
  reflectX (Rectangle a b) = Rectangle (reflectX a) (reflectX b)
  reflectY (Circle c r)    = Circle (reflectY c) r
  reflectY (Rectangle a b) = Rectangle (reflectY a) (reflectY b)

Inštancia pre Shape volá metódy inštancie pre Point. Haskell vyberie správnu podľa typu argumentu. Otočenie o 180° je zrkadlenie podľa oboch osí, preto má predvolenú definíciu so skladaním funkcií ..

Úloha 4.7 – Functor

Urob inštanciu Functor pre tri typy.

data BTree a = Leaf a | Branch (BTree a) (BTree a)
data Pair a  = Pair a a
data Tree a  = Empty | Node (Tree a) a (Tree a)

fmap (*10) (Branch (Leaf 1) (Leaf 2)) == Branch (Leaf 10) (Leaf 20)
fmap (+1) (Pair 1 2)                  == Pair 2 3

Riešenie

instance Functor BTree where
  fmap f (Leaf x)     = Leaf (f x)
  fmap f (Branch l r) = Branch (fmap f l) (fmap f r)

instance Functor Pair where
  fmap f (Pair x y) = Pair (f x) (f y)

instance Functor Tree where
  fmap _ Empty        = Empty
  fmap f (Node l v r) = Node (fmap f l) (f v) (fmap f r)

fmap je map pre ľubovoľnú štruktúru. Zmení hodnoty, ale tvar zostane. Inštancia sa píše pre BTree, nie pre BTree a. Functor potrebuje typový konštruktor s druhom * -> *.

Úloha 4.8 – Foldable

Urob inštanciu Foldable pre BTree a Tree. Potom vyskúšaj sum, length, maximum a elem na strome.

sum myLittleTree        == 10
length myLittleTree     == 4
foldr (:) [] myLittleTree == [1,2,3,4]

Riešenie

instance Foldable BTree where
  foldr f z (Leaf x)     = f x z
  foldr f z (Branch l r) = foldr f (foldr f z r) l

instance Foldable Tree where
  foldr _ z Empty        = z
  foldr f z (Node l v r) = foldr f (f v (foldr f z r)) l

Stačí definovať foldr. Najprv sa spracuje pravý podstrom, jeho výsledok je štartovacia hodnota pre zvyšok a nakoniec sa spracuje ľavý podstrom. Vďaka tomu je poradie zľava doprava, rovnako ako pri zozname.

Zadarmo dostaneš sum, product, length, maximum, minimum, elem, null aj foldl.

Úloha 4.9 – deriving Ord pri enumerácii

Čo vrátia tieto výrazy?

data Size = Small | Medium | Large
  deriving (Show, Eq, Ord)

Small < Large
maximum [Medium, Small]
compare Large Medium

Riešenie

Small < Large           -- True
maximum [Medium, Small] -- Medium
compare Large Medium    -- GT

Pri deriving Ord platí poradie, v akom sú konštruktory zapísané: prvý je najmenší.


Úroveň 5 – vstup a výstup (IO)

Cvičenie 7. do blok, <-, let, pure/return, >>= a >>, readMaybe, mapM a mapM_, súbory a argumenty.

Úloha 5.1 – pozdrav dvoma spôsobmi

Program sa opýta na meno a pozdraví. Napíš ho s do aj cez >>=.

Ako sa volas?
Kamil
Ahoj, Kamil!

Riešenie

greet :: IO ()
greet = do
  putStrLn "Ako sa volas?"
  name <- getLine
  putStrLn ("Ahoj, " ++ name ++ "!")

greet' :: IO ()
greet' = putStrLn "Ako sa volas?"
      >> getLine
      >>= \name -> putStrLn ("Ahoj, " ++ name ++ "!")

name <- getLine vykoná akciu a jej výsledok (String) pomenuje name. V >>= verzii z toho vznikne lambda \name -> .... Riadok bez <- sa prepíše na >>, ktorý výsledok zahodí.

Úloha 5.2 – súčet dvoch čísel

Prečítaj dva riadky a vypíš súčet.

3
4
Sucet: 7

Riešenie

sumTwo :: IO ()
sumTwo = do
  a <- getLine
  b <- getLine
  let s = read a + read b :: Int
  putStrLn ("Sucet: " ++ show s)

getLine vracia String, preto treba read. Typ :: Int povie, na aký typ sa má reťazec previesť. let v do bloku pomenuje čistú hodnotu a píše sa bez in. show prevedie číslo späť na text.

Častá chyba je let a = getLine. Tým pomenuješ akciu, nevykonáš ju. Na výsledok akcie treba <-.

Úloha 5.3 – načítanie čísla s opakovaním

getInt sa pýta, kým používateľ nezadá platné celé číslo.

getInt :: IO Int

Riešenie

import Text.Read (readMaybe)

getInt :: IO Int
getInt = do
  putStrLn "Zadaj cele cislo:"
  line <- getLine
  case readMaybe line of
    Just n  -> pure n
    Nothing -> do
      putStrLn "To nie je cislo."
      getInt

-- kratšia verzia z cvičenia
getInt' :: IO Int
getInt' = putStrLn "Zadaj cele cislo:" >> getLine >>= maybe getInt' pure . readMaybe

Cyklus v Haskelli je rekurzia: pri zlom vstupe sa getInt zavolá znova. pure n zabalí Int do IO Int, aby sedel typ. Vetva Nothing potrebuje vlastné do, lebo obsahuje dve akcie.

readMaybe na rozdiel od read nespadne, ale vráti Nothing.

Úloha 5.4 – dotazník

ask položí otázku a vráti odpoveď. askAll položí všetky otázky a vráti zoznam odpovedí. Napíš askAll rekurziou aj cez mapM.

ask    :: String -> IO String
askAll :: [String] -> IO [String]

Riešenie

ask :: String -> IO String
ask q = do
  putStrLn q
  getLine              -- výsledok poslednej akcie je výsledok ask

askAll :: [String] -> IO [String]
askAll []     = pure []
askAll (q:qs) = do
  a  <- ask q
  as <- askAll qs
  pure (a : as)

askAll' :: [String] -> IO [String]
askAll' qs = mapM ask qs

Rekurzia má rovnaký tvar ako pri zozname, len každý krok je akcia. mapM f xs je map pre akcie: vykoná ich po poradí a výsledky zozbiera.

Pozor, map ask qs má typ [IO String]. Je to zoznam akcií, ktoré sa nevykonajú.

Úloha 5.5 – očíslovaný výpis

printNumbered :: [String] -> IO ()

printNumbered ["mlieko", "chlieb"]
-- 1. mlieko
-- 2. chlieb

Riešenie

printNumbered :: [String] -> IO ()
printNumbered xs = mapM_ putStrLn (zipWith format [1 ..] xs)
  where
    format i s = show i ++ ". " ++ s

Čistá časť (zipWith format) vyrobí riadky textu a mapM_ putStrLn ich vypíše. mapM_ zahodí výsledky, takže typ je IO (). Oddeliť čistý výpočet od IO je presne to, čo odporúča prednáška.

Úloha 5.6 – opakuj, kým nepríde „koniec“

Každý riadok vypíš veľkými písmenami. Na slovo koniec sa rozlúč a skonči.

ahoj
AHOJ
koniec
Dovidenia.

Riešenie

import Data.Char (toUpper)

shout :: IO ()
shout = do
  line <- getLine
  if line == "koniec"
    then putStrLn "Dovidenia."
    else do
      putStrLn (map toUpper line)
      shout

if v do bloku musí mať aj else. Obe vetvy sú akcie typu IO (). Vetva s dvoma akciami potrebuje vlastné do.

Úloha 5.7 – súčet čísel do prázdneho riadku

Načítavaj čísla po jednom na riadok. Pri prázdnom riadku vráť ich súčet.

sumUntilEmpty :: IO Int

Riešenie

sumUntilEmpty :: IO Int
sumUntilEmpty = do
  line <- getLine
  if null line
    then pure 0
    else do
      rest <- sumUntilEmpty
      pure (read line + rest)

Rovnaký vzor ako rekurzívny sum nad zoznamom: prázdny riadok je základný prípad, ktorý vráti 0. Výsledok rekurzie treba vybaliť cez <- a až potom pripočítať.

Úloha 5.8 – štatistika súboru

fileStats :: FilePath -> IO ()

-- súbor t.txt: "a b\nc\n"
fileStats "t.txt"   -- Riadky: 2, slova: 3

Riešenie

fileStats :: FilePath -> IO ()
fileStats path = do
  content <- readFile path
  let ls = length (lines content)
      ws = length (words content)
  putStrLn ("Riadky: " ++ show ls ++ ", slova: " ++ show ws)

readFile vráti celý súbor ako jeden String. Ďalej pracuješ s obyčajnými funkciami lines a words. V jednom let môže byť viac definícií pod sebou, ak sú zarovnané.

Úloha 5.9 – súčet argumentov programu

runghc sucet.hs 1 2 3 vypíše 6.

Riešenie

import System.Environment (getArgs)

main :: IO ()
main = do
  args <- getArgs
  let nums = map read args :: [Int]
  print (sum nums)

getArgs :: IO [String] vráti argumenty bez názvu programu. print x je putStrLn (show x).

Úloha 5.10 – prepis z >>= do do

Prepíš do do notácie.

countdown :: IO ()
countdown = getInt >>= \n -> mapM_ print [n, n-1 .. 0] >> putStrLn "Start!"

Riešenie

countdown :: IO ()
countdown = do
  n <- getInt
  mapM_ print [n, n-1 .. 0]
  putStrLn "Start!"
>>= do
akcia >>= \x -> ... x <- akcia
akcia >> ... akcia na samostatnom riadku
let x = ... in ... let x = ...

Úroveň 6 – monády Maybe, Either a zoznam

Prednáška 7. do funguje aj pre Maybe, Either a zoznamy. Pri Maybe sa výpočet zastaví pri prvom Nothing, pri Either pri prvom Left.

Úloha 6.1 – reťazenie delení

Vypočítaj a / b / c + 1 cez safeDiv z úlohy 2.2. Ak sa niekde delí nulou, vráť Nothing. Napíš verziu s case, s do a s >>=.

calc :: Int -> Int -> Int -> Maybe Int

calc 100 5 2 == Just 11
calc 100 0 2 == Nothing

Riešenie

-- a) vnorené case
calc a b c = case safeDiv a b of
  Nothing -> Nothing
  Just x  -> case safeDiv x c of
    Nothing -> Nothing
    Just y  -> Just (y + 1)

-- b) do
calc a b c = do
  x <- safeDiv a b
  y <- safeDiv x c
  pure (y + 1)

-- c) >>=
calc a b c = safeDiv a b >>= \x -> safeDiv x c >>= \y -> return (y + 1)

Všetky tri verzie robia to isté. >>= pre Maybe pri Nothing hneď vráti Nothing a pri Just x pošle x ďalej. do je kratší zápis toho istého, rovnako ako pri IO.

Úloha 6.2 – reťazenie lookup (prednáška 7)

studentIDs  = [("Eva", 1), ("Adam", 2), ("Mia", 3)]
statuses    = [(1, "A"), (2, "P")]
statusNames = [("A", "aktivny"), ("P", "preruseny")]

studentStatus :: String -> Maybe String

studentStatus "Eva" == Just "aktivny"
studentStatus "Mia" == Nothing     -- nemá stav
studentStatus "Jan" == Nothing     -- neexistuje

Riešenie

studentStatus :: String -> Maybe String
studentStatus name = do
  sid    <- lookup name studentIDs
  status <- lookup sid statuses
  lookup status statusNames

studentStatus' name =
  lookup name studentIDs
    >>= \sid -> lookup sid statuses
    >>= \status -> lookup status statusNames

Posledný riadok do bloku už vracia Maybe String, preto netreba pure.

Úloha 6.3 – Either v do

Sčítaj dve čísla zadané ako text. Ak jedno nie je číslo, vráť chybu s tým reťazcom.

parseNum   :: String -> Either String Int
addStrings :: String -> String -> Either String Int

addStrings "2" "40" == Right 42
addStrings "2" "x"  == Left "zle cislo: x"

Riešenie

parseNum :: String -> Either String Int
parseNum s = case readMaybe s of
  Nothing -> Left ("zle cislo: " ++ s)
  Just n  -> Right n

addStrings :: String -> String -> Either String Int
addStrings a b = do
  x <- parseNum a
  y <- parseNum b
  pure (x + y)

Pri Either sa výpočet zastaví na prvom Left a táto chyba sa vráti. pure tu znamená Right.

Úloha 6.4 – bezpečné vyhodnotenie výrazu

Výraz s delením. Delenie nulou vráti chybu.

data Expr = Num Int | Add Expr Expr | Div Expr Expr

safeEval :: Expr -> Either String Int

safeEval (Add (Num 1) (Div (Num 6) (Num 3)))           == Right 3
safeEval (Div (Num 1) (Add (Num 1) (Num (-1))))         == Left "delenie nulou"

Riešenie

safeEval :: Expr -> Either String Int
safeEval (Num n)   = Right n
safeEval (Add a b) = do
  x <- safeEval a
  y <- safeEval b
  pure (x + y)
safeEval (Div a b) = do
  x <- safeEval a
  y <- safeEval b
  if y == 0
    then Left "delenie nulou"
    else pure (x `div` y)

Spája sa tu rekurzívny typ z úrovne 3 s monádou Either. Keď niektorý podvýraz vráti chybu, do ju pošle až na výstup a netreba ju ručne kontrolovať.

Úloha 6.5 – zoznamová monáda

Vytvor všetky dvojice z dvoch zoznamov tromi spôsobmi.

pairs :: [a] -> [b] -> [(a, b)]

pairs [1,2] "ab" == [(1,'a'),(1,'b'),(2,'a'),(2,'b')]

Riešenie

-- a) do
pairs xs ys = do
  x <- xs
  y <- ys
  pure (x, y)

-- b) množinová abstrakcia
pairs xs ys = [(x, y) | x <- xs, y <- ys]

-- c) >>=
pairs xs ys = xs >>= \x -> ys >>= \y -> return (x, y)

Pri zozname x <- xs znamená „pre každé x zo xs“. Množinová abstrakcia je len iný zápis zoznamovej monády.

Úloha 6.6 – mapM s Maybe

Preveď všetky reťazce na čísla. Ak niektorý nejde, vráť Nothing.

parseAll :: [String] -> Maybe [Int]

parseAll ["1","2","3"] == Just [1,2,3]
parseAll ["1","x"]     == Nothing

Riešenie

parseAll :: [String] -> Maybe [Int]
parseAll xs = mapM readMaybe xs

mapM funguje v každej monáde, nielen v IO. Pri Maybe vráti Just zoznam, keď sa podarí každý prvok, inak Nothing.

Úloha 6.7 – čo vráti fmap?

fmap (+1) (Just 2)
fmap (+1) Nothing
fmap (*2) [1,2,3]
fmap length (Right "abc")
fmap length (Left 7)
(+1) <$> Just 5

Riešenie

fmap (+1) (Just 2)        -- Just 3
fmap (+1) Nothing         -- Nothing
fmap (*2) [1,2,3]         -- [2,4,6]
fmap length (Right "abc") -- Right 3
fmap length (Left 7)      -- Left 7    (Left sa nemení)
(+1) <$> Just 5           -- Just 6    (<$> je fmap)

fmap aplikuje funkciu na hodnotu vnútri obalu a obal ponechá.


Úroveň 7 – jazyk lambda

Prednáška 5. Slajdy k nej som nemal k dispozícii, preto sú úlohy zo štandardnej teórie. Zápis si porovnaj s prednáškou, napríklad či používa bodku λx.M, alebo iný oddeľovač.

Úloha 7.1 – voľné a viazané premenné

Ktoré premenné sú voľné?

a) λx. x y z
b) (λx. x) (λy. x y)
c) λx. λy. x y

Riešenie

a) y, z           (x je viazané λx)
b) x              (x v druhej časti nie je pod λx)
c) žiadne         (výraz je uzavretý, kombinátor)

Premenná je viazaná, ak je v tele nejakej λ s rovnakým menom. Inak je voľná.

Úloha 7.2 – beta redukcia

Zredukuj do normálnej formy.

a) (λx. x) a
b) (λx. λy. x) a b
c) (λx. x x) (λy. y)
d) (λf. λx. f (f x)) g a

Riešenie

a) (λx. x) a            →β  a
b) (λx. λy. x) a b      →β  (λy. a) b   →β  a
c) (λx. x x) (λy. y)    →β  (λy. y) (λy. y)  →β  λy. y
d) (λf. λx. f (f x)) g a →β (λx. g (g x)) a  →β  g (g a)

Beta redukcia nahradí parameter argumentom v tele funkcie: (λx. M) N → M[x := N]. Aplikácia sa združuje zľava, M N P je (M N) P.

Úloha 7.3 – lambda v Haskelli

Prepíš výrazy z 7.2 b) a d) do Haskellu a vyhodnoť.

Riešenie

(\x -> \y -> x) 'a' 'b'          -- 'a'
(\x y -> x) 'a' 'b'              -- to isté, skrátený zápis
(\f x -> f (f x)) (+1) 5         -- 7

\x y -> M je skratka pre \x -> \y -> M. Funkcia viacerých parametrov je funkcia, ktorá vracia funkciu (currying), presne ako v jazyku lambda.

Úloha 7.4 – Churchove pravdivostné hodnoty

TRUE  = λt. λf. t
FALSE = λt. λf. f
AND   = λp. λq. p q p

Vyhodnoť AND TRUE FALSE.

Riešenie

AND TRUE FALSE
→ (λq. TRUE q TRUE) FALSE
→ TRUE FALSE TRUE
→ (λf. FALSE) TRUE
→ FALSE

TRUE vyberá prvý argument, FALSE druhý. AND p q vráti q, keď je p pravda, a p, teda FALSE, keď je p nepravda.


Písomky nanečisto

Každá písomka má tri úlohy na 15 minút. Píš na papier a až potom si pozri riešenie.

Písomka A

Úloha A1 – teplota

Definuj typ Temperature s konštruktormi Celsius Double a Fahrenheit Double. Napíš toCelsius (°C = (°F − 32) · 5 / 9) a warmer, ktorá zistí, či je prvá teplota vyššia.

toCelsius (Fahrenheit 212)          == 100.0
warmer (Celsius 30) (Fahrenheit 50) == True

Riešenie

data Temperature = Celsius Double | Fahrenheit Double
  deriving Show

toCelsius :: Temperature -> Double
toCelsius (Celsius c)    = c
toCelsius (Fahrenheit f) = (f - 32) * 5 / 9

warmer :: Temperature -> Temperature -> Bool
warmer a b = toCelsius a > toCelsius b

Dve stupnice prevedieš na spoločnú a až potom porovnávaš.

Úloha A2 – bezpečné maximum

safeMaximum :: Ord a => [a] -> Maybe a

safeMaximum [3,9,2] == Just 9
safeMaximum []      == Nothing

Riešenie

safeMaximum :: Ord a => [a] -> Maybe a
safeMaximum [] = Nothing
safeMaximum xs = Just (maximum xs)

-- bez maximum, s akumulátorom
safeMaximum' []     = Nothing
safeMaximum' (x:xs) = Just (go x xs)
  where
    go best []     = best
    go best (y:ys) = go (max best y) ys

Obmedzenie Ord a je potrebné kvôli maximum a max.

Úloha A3 – väčšie z dvoch čísel

Program načíta dve celé čísla a vypíše väčšie z nich, alebo že sú rovnaké.

Prve cislo:
3
Druhe cislo:
8
Vacsie je 8

Riešenie

main :: IO ()
main = do
  putStrLn "Prve cislo:"
  a <- getLine
  putStrLn "Druhe cislo:"
  b <- getLine
  let x = read a :: Int
      y = read b :: Int
  if x == y
    then putStrLn "Cisla su rovnake."
    else putStrLn ("Vacsie je " ++ show (max x y))

Písomka B

Úloha B1 – strom s hodnotami v uzloch

data Tree a = Empty | Node (Tree a) a (Tree a)

height  :: Tree a -> Int          -- prázdny strom má výšku 0
sumTree :: Num a => Tree a -> a
leaves  :: Tree a -> [a]          -- hodnoty uzlov bez potomkov

t1 = Node (Node Empty 1 Empty) 5 (Node (Node Empty 6 Empty) 8 Empty)
height t1 == 3,  sumTree t1 == 20,  leaves t1 == [1,6]

Riešenie

height :: Tree a -> Int
height Empty        = 0
height (Node l _ r) = 1 + max (height l) (height r)

sumTree :: Num a => Tree a -> a
sumTree Empty        = 0
sumTree (Node l v r) = sumTree l + v + sumTree r

leaves :: Tree a -> [a]
leaves Empty                = []
leaves (Node Empty v Empty) = [v]
leaves (Node l _ r)         = leaves l ++ leaves r

V leaves musí byť vzor (Node Empty v Empty) pred všeobecným (Node l _ r), lebo vzory sa skúšajú zhora.

Úloha B2 – peniaze

Money eura centy sa vypíše ako 12.05 EUR. Dve sumy sa rovnajú, ak predstavujú rovnaké množstvo peňazí.

data Money = Money Int Int

show (Money 12 5)          == "12.05 EUR"
Money 1 150 == Money 2 50  -- True

Riešenie

instance Show Money where
  show (Money e c) = show e ++ "." ++ cents ++ " EUR"
    where
      cents = if c < 10 then '0' : show c else show c

instance Eq Money where
  Money e1 c1 == Money e2 c2 = e1 * 100 + c1 == e2 * 100 + c2

Aj v metóde inštancie sa dá použiť where. Rovnosť porovnáva celkový počet centov.

Úloha B3 – prepis do >>=

hello :: IO ()
hello = do
  putStrLn "Meno:"
  name <- getLine
  putStrLn "Vek:"
  age <- getLine
  let msg = name ++ " ma " ++ age ++ " rokov."
  putStrLn msg

Riešenie

hello :: IO ()
hello = putStrLn "Meno:"
  >> getLine
  >>= \name -> putStrLn "Vek:"
  >> getLine
  >>= \age ->
    let msg = name ++ " ma " ++ age ++ " rokov."
    in putStrLn msg

Lambda \name -> ... siaha až na koniec výrazu, preto je name viditeľné aj v poslednom riadku. let v >>= verzii potrebuje in.

Písomka C

Úloha C1 – produkty

data Product = Product
  { pname :: String
  , price :: Double
  , stock :: Int
  } deriving (Show, Eq)

inStock  :: [Product] -> [String]               -- názvy produktov so stock > 0
discount :: Double -> [Product] -> [Product]    -- zľava v percentách

Riešenie

inStock :: [Product] -> [String]
inStock ps = [pname p | p <- ps, stock p > 0]

discount :: Double -> [Product] -> [Product]
discount pct ps = map cheaper ps
  where
    cheaper p = p { price = price p * (1 - pct / 100) }

Úloha C2 – kontrola hesla

Heslo musí mať aspoň 8 znakov a aspoň jednu číslicu.

validatePassword :: String -> Either String String

validatePassword "abc"      == Left "heslo je prilis kratke"
validatePassword "abcdefgh" == Left "heslo musi obsahovat cislicu"
validatePassword "abcdefg1" == Right "abcdefg1"

Riešenie

import Data.Char (isDigit)

validatePassword :: String -> Either String String
validatePassword pw
  | length pw < 8        = Left "heslo je prilis kratke"
  | not (any isDigit pw) = Left "heslo musi obsahovat cislicu"
  | otherwise            = Right pw

Úloha C3 – dotazník s výpisom

Polož všetky otázky a potom vypíš každú otázku s odpoveďou.

survey :: [String] -> IO ()

Riešenie

survey :: [String] -> IO ()
survey qs = do
  answers <- mapM ask qs
  mapM_ putStrLn (zipWith line qs answers)
  where
    ask q    = putStrLn q >> getLine
    line q a = q ++ " " ++ a

where platí pre celé telo do bloku. mapM zozbiera odpovede a mapM_ vypíše riadky.

Písomka D

Úloha D1 – Functor a Ord

data Box a = NoBox | Box a
data Suit  = Hearts | Spades
data Card  = Card Int Suit

-- a) instance Functor Box
-- b) karty sa porovnávajú len podľa hodnoty (Eq aj Ord)

fmap (+1) (Box 1) == Box 2
Card 10 Hearts == Card 10 Spades   -- True

Riešenie

instance Functor Box where
  fmap _ NoBox   = NoBox
  fmap f (Box x) = Box (f x)

instance Eq Card where
  Card a _ == Card b _ = a == b

instance Ord Card where
  compare (Card a _) (Card b _) = compare a b

Box je vlastná verzia Maybe. Pre Ord treba aj Eq, lebo Eq je nadtrieda Ord.

Úloha D2 – Foldable pre vlastný zoznam

data List a = Nil | Cons a (List a)

sum (Cons 1 (Cons 2 (Cons 3 Nil))) == 6

Riešenie

instance Foldable List where
  foldr _ z Nil         = z
  foldr f z (Cons x xs) = f x (foldr f z xs)

Je to presne definícia foldr pre obyčajný zoznam. Nil nahradíš z a Cons nahradíš f.

Úloha D3 – typy

Napíš typ:

a) \x -> x == 'a'
b) Just
c) fmap show
d) mapM_ print
e) lookup 3

Riešenie

a) Char -> Bool
b) a -> Maybe a
c) (Functor f, Show a) => f a -> f String
d) Show a => [a] -> IO ()           -- všeobecne Foldable t => t a
e) (Eq a, Num a) => [(a, b)] -> Maybe b

Konštruktor je obyčajná funkcia, preto má Just typ a -> Maybe a. Pri čiastočnej aplikácii (fmap show, lookup 3) zostane typ bez prvého parametra.


Top