Skip to content

← Späť na Exam 2

Haskell – ťahák na 2. písomku

  1. 1. Definícia typov
    1. Porovnávanie vzorov s konštruktormi
    2. case
    3. Record syntax
  2. 2. Maybe a Either
    1. Funkcie
    2. Typické vzory
  3. 3. Rekurzívne typy – kostra funkcie
  4. 4. Typové triedy
    1. Syntax
    2. Štandardné triedy
    3. Ako zistiť obmedzenia z tela funkcie
    4. Druhy typov (kinds)
    5. Functor a Foldable
  5. 5. Vstup a výstup (IO)
    1. Funkcie
    2. Kostry programov
    3. Prepis do ↔ >>=
    4. Pravidlá a časté chyby
    5. Kompilácia a spustenie
  6. 6. Monády
    1. Príklady
    2. Functor, Applicative a Monad
    3. Zákony monád
    4. Analógie z iných jazykov
  7. 7. Jazyk lambda (prednáška 5)
  8. 8. Na čo nezabudnúť na písomke

Cvičenia 4 až 7 a prednášky 4 až 7: dátové typy, Maybe a Either, rekurzívne typy, typové triedy, vstup a výstup a monády. Každý príklad je zapísaný ako volanie a výsledok, ako v GHCi.


1. Definícia typov

Zápis Čo robí Príklad
type nové meno pre existujúci typ, nový typ nevzniká type Name = String
data nový typ s jedným alebo viac konštruktormi data Point = Point Double Double
deriving automatická inštancia triedy deriving (Show, Eq, Ord)
-- enumerácia (konštruktory bez parametrov)
data Color = Red | Green | Blue
  deriving (Show, Eq)

-- súčinový typ (jeden konštruktor s viacerými hodnotami)
data Point = Point Double Double
  deriving (Show, Eq)

-- algebraický typ = súčet súčinov (viac konštruktorov s parametrami)
data Shape = Circle Point Double
           | Rectangle Point Point
           deriving Show

-- parametrický typ (typová premenná a)
data Pair a = Pair a a

-- rekurzívny typ (typ sa vyskytuje vo vlastnom konštruktore)
data BTree a = Leaf a | Branch (BTree a) (BTree a)
data Tree a  = Empty  | Node (Tree a) a (Tree a)
  • Názov typu aj konštruktora začína veľkým písmenom, premenné a funkcie malým.
  • Typ a konštruktor sa môžu volať rovnako (Point), sú to však dve rôzne veci.
  • Konštruktor je obyčajná funkcia: Circle :: Point -> Double -> Shape, Just :: a -> Maybe a.
  • Typová premenná musí byť aj v hlavičke: data Pair a = Pair a a, nie data Pair = Pair a a.

Porovnávanie vzorov s konštruktormi

area :: Shape -> Double
area (Circle _ r)                            = pi * r ^ 2
area (Rectangle (Point x1 y1) (Point x2 y2)) = abs (x2 - x1) * abs (y2 - y1)
  • Jedna rovnica na každý konštruktor. Vzor musí byť v zátvorkách: (Circle _ r).
  • Vzory sa dajú vnárať, napríklad útvar aj jeho body naraz.
  • _ je ľubovoľná hodnota, ktorú nepotrebuješ.
  • Vzory sa skúšajú zhora nadol, preto konkrétny vzor patrí pred všeobecný.

case

toHex :: Color -> String
toHex c = case c of
  Red   -> "#FF0000"
  Green -> "#00FF00"
  Blue  -> "#0000FF"
  • Za vzorom je ->, nie =. Všetky vetvy majú rovnaké odsadenie.
  • case sa dá použiť vnútri výrazu, napríklad na výsledok inej funkcie.
  • Vo vetve môžu byť aj strážcovia:
case readMaybe s of
  Nothing -> Left "nie je cislo"
  Just n
    | n < 0     -> Left "zaporne"
    | otherwise -> Right n

Record syntax

data Person = Person
  { name :: String
  , age  :: Int
  } deriving (Show, Eq)
Čo Zápis Výsledok
vytvorenie pozične Person "John" 30 Person {name = "John", age = 30}
vytvorenie s menami Person { name = "John", age = 30 } to isté
čítanie poľa name (Person "John" 30) "John"
úprava (nová kópia) john { age = 31 } Person {name = "John", age = 31}
vzor f (Person n a) = ... rozloží záznam
  • Record syntax vygeneruje funkcie name :: Person -> String a age :: Person -> Int.
  • p { age = 31 } vytvorí novú hodnotu, p zostane nezmenené.
  • Just b { status = X } sa číta ako Just (b { status = X }).

2. Maybe a Either

data Maybe a    = Nothing | Just a      -- výsledok môže chýbať
data Either a b = Left a  | Right b     -- chyba (Left) alebo výsledok (Right)
Keď... Použi
výsledok môže chýbať a netreba vedieť prečo Maybe
treba vedieť, prečo výsledok chýba Either s chybou v Left

Funkcie

Funkcia Typ Príklad Výsledok
lookup Eq a => a -> [(a,b)] -> Maybe b lookup 2 [(1,"a"),(2,"b")] Just "b"
maybe b -> (a -> b) -> Maybe a -> b maybe 0 (+1) (Just 5) 6
maybe maybe 0 (+1) Nothing 0
fromMaybe a -> Maybe a -> a fromMaybe 0 (Just 5) 5
fromMaybe fromMaybe 0 Nothing 0
either (a -> c) -> (b -> c) -> Either a b -> c either length negate (Left "abc") 3
either either length negate (Right 4) -4
isJust, isNothing Maybe a -> Bool isJust (Just 1) True
listToMaybe [a] -> Maybe a listToMaybe [7,8] Just 7
catMaybes [Maybe a] -> [a] catMaybes [Just 1, Nothing, Just 3] [1,3]
mapMaybe (a -> Maybe b) -> [a] -> [b] mapMaybe readMaybe ["1","x"] :: [Int] [1]
readMaybe Read a => String -> Maybe a readMaybe "42" :: Maybe Int Just 42
readMaybe readMaybe "x" :: Maybe Int Nothing
fmap (a -> b) -> Maybe a -> Maybe b fmap (+1) (Just 2) Just 3

Importy: fromMaybe, isJust, isNothing, listToMaybe, catMaybes a mapMaybe sú v Data.Maybe, readMaybe je v Text.Read. lookup, maybe a either sú v Prelude.

Typické vzory

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

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

-- rozbalenie Maybe
case safeHead xs of
  Nothing -> "prazdny"
  Just x  -> "prvy je " ++ show x

-- validácia s Either: prvá chyba vyhráva
register :: String -> String -> Either RegistrationError Account
register u p
  | null u       = Left EmptyUsername
  | length p < 8 = Left (PasswordTooShort (length p))
  | otherwise    = Right (Account u p)

3. Rekurzívne typy – kostra funkcie

Funkcia nad rekurzívnym typom má jednu rovnicu na konštruktor. Pri rekurzívnom konštruktore sa zavolá na podštruktúry a výsledky spojí.

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

f :: BTree a -> ...
f (Leaf x)     = ...                  -- základný prípad
f (Branch l r) = ... (f l) ... (f r)  -- spojenie výsledkov podstromov
Funkcia Leaf x Branch l r
počet listov 1 leafCount l + leafCount r
hĺbka 1 1 + max (depth l) (depth r)
súčet x sumB l + sumB r
do zoznamu [x] toList l ++ toList r
obsahuje y x == y contains y l \|\| contains y r
map Leaf (f x) Branch (mapT f l) (mapT f r)
fold x g (foldB g l) (foldB g r)
zrkadlo Leaf x Branch (mirror r) (mirror l)

Strom s hodnotami v uzloch má prázdny list:

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

size Empty        = 0
size (Node l _ r) = size l + 1 + size r

inorder Empty        = []
inorder (Node l v r) = inorder l ++ [v] ++ inorder r

-- binárny vyhľadávací strom: menšie vľavo, väčšie vpravo
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

Výraz ako strom:

data Expr = Num Int | Add Expr Expr | Mul Expr Expr | Neg Expr

eval (Num n)   = n
eval (Add a b) = eval a + eval b
eval (Mul a b) = eval a * eval b
eval (Neg a)   = negate (eval a)

4. Typové triedy

Pojem Význam
trieda (class) zoznam metód, ktoré typ musí vedieť, podobne ako interface v Jave
inštancia (instance) implementácia metód pre konkrétny typ
obmedzenie (Eq a =>) typ a musí patriť do triedy Eq
deriving inštanciu vytvorí kompilátor
parametrický polymorfizmus funguje pre všetky typy rovnako, napr. length :: [a] -> Int
ad hoc polymorfizmus funguje len pre typy z triedy, každý inak, napr. (==)

Syntax

-- definícia triedy
class Movable a where
  move      :: Vector -> a -> a
  reflectX  :: a -> a
  reflectY  :: a -> a
  rotate180 :: a -> a
  rotate180 = reflectX . reflectY          -- predvolená metóda

-- inštancia
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

-- inštancia s obmedzením: strom sa dá porovnať, ak sa dajú porovnať prvky
instance Eq a => Eq (BTree a) where
  Leaf a       == Leaf b       = a == b
  Branch l1 r1 == Branch l2 r2 = l1 == l2 && r1 == r2
  _            == _            = False

-- nadtrieda: každý typ v Ord musí byť aj v Eq
class Eq a => Ord a where ...

-- obmedzenie vo funkcii
allEqual :: Eq a => [a] -> Bool
f        :: (Ord a, Show a) => [a] -> String
  • Vo where inštancie sú len definície metód, bez typovej signatúry.
  • Typ nesmie mať zároveň deriving Eq a instance Eq.
  • Pri instance Ord T musí existovať aj instance Eq T.
  • Obmedzenie sa prenáša: funkcia, ktorá vnútri volá ==, dostane Eq a => aj do svojho typu.

Štandardné triedy

Trieda Metódy Minimálna definícia Príklad
Eq ==, /= == alebo /= 1 == 1 → True
Ord compare, <, <=, >, >=, max, min compare alebo <= compare 1 2 → LT
Show show show show 42 → "42"
Read read (cez deriving) read "42" :: Int → 42
Num +, -, *, negate, abs, fromInteger 3 + 4 → 7
Integral div, mod div 7 2 → 3
Fractional / 7 / 2 → 3.5
Enum succ, pred, [a .. b] succ 'a' → 'b'
Functor fmap, <$> fmap fmap (+1) [1,2] → [2,3]
Foldable foldr, sum, length, elem, maximum… foldr sum (Just 5) → 5
Monad >>=, >>, return >>= Just 1 >>= Just → Just 1

compare vracia hodnotu typu Ordering, teda LT, EQ alebo GT.

Pri deriving Ord na enumerácii platí poradie zápisu: v data Size = Small | Medium | Large je Small < Large.

Ako zistiť obmedzenia z tela funkcie

Funkcia použije Obmedzenie
==, /=, elem, lookup Eq a
<, >, max, maximum, sort Ord a (zahŕňa Eq)
+, -, *, číslo 0 Num a
div, mod Integral a
/ Fractional a
show, print Show a
read Read a
fmap, <$> Functor f
f x y = x == y && x > 0     -- (Ord a, Num a) => a -> a -> Bool
h x y = [x, y]              -- a -> a -> [a]   (bez obmedzenia)

Druhy typov (kinds)

Typ Druh Význam
Int, Bool, BTree Int, Maybe Int * konkrétny typ, má hodnoty
Maybe, [], BTree, Either String * -> * čaká na jeden typ
Either * -> * -> * čaká na dva typy

V GHCi sa druh zistí cez :k Maybe. Functor, Foldable a Monad sa píšu pre druh * -> *, preto platí instance Functor BTree, nie instance Functor (BTree a).

Functor a Foldable

class Functor f where
  fmap :: (a -> b) -> f a -> f b

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

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
  • fmap zmení hodnoty a zachová tvar štruktúry. Pri zoznamoch je to map.
  • <$> je infixový fmap: (+1) <$> Just 2 → Just 3.
  • Pri Foldable stačí foldr. Potom zadarmo fungujú sum, product, length, maximum, minimum, elem, null, foldl aj foldr (:) [], ktorý vráti prvky ako zoznam.

5. Vstup a výstup (IO)

Pojem Význam
IO a akcia, ktorá komunikuje so svetom a vráti hodnotu typu a
IO () akcia bez užitočného výsledku, napr. výpis
main :: IO () vstupný bod programu
do akcie pod sebou, vykonajú sa v poradí
x <- akcia vykoná akciu a výsledok pomenuje x
let x = výraz pomenuje čistú hodnotu, nič sa nevykoná (v do bez in)
pure x / return x akcia, ktorá len vráti x (nekončí funkciu ako v Jave)

Funkcie

Funkcia Typ Príklad Výsledok
putStrLn String -> IO () putStrLn "ahoj" vypíše ahoj a nový riadok
putStr String -> IO () putStr "ahoj" vypíše bez nového riadku
print Show a => a -> IO () print [1,2] vypíše [1,2]
getLine IO String name <- getLine prečíta riadok
readFile FilePath -> IO String s <- readFile "a.txt" celý obsah súboru
writeFile FilePath -> String -> IO () writeFile "a.txt" "ahoj" prepíše súbor
appendFile FilePath -> String -> IO () appendFile "a.txt" "x" pridá na koniec
getArgs IO [String] args <- getArgs ["values.txt"]
read Read a => String -> a read "42" :: Int 42 (pri chybe spadne)
readMaybe Read a => String -> Maybe a readMaybe "x" :: Maybe Int Nothing
mapM (a -> IO b) -> [a] -> IO [b] mapM ask qs vykoná a zozbiera výsledky
mapM_ (a -> IO b) -> [a] -> IO () mapM_ print [1,2] vypíše 1 a 2
>>= IO a -> (a -> IO b) -> IO b getLine >>= putStrLn zopakuje vstup
>> IO a -> IO b -> IO b putStr "a" >> putStr "b" ab

Importy: getArgs je v System.Environment, readMaybe v Text.Read, toUpper a isDigit v Data.Char.

Kostry programov

-- otázka a odpoveď
main :: IO ()
main = do
  putStrLn "Ako sa volas?"
  name <- getLine
  let msg = "Ahoj, " ++ name ++ "!"
  putStrLn msg

-- čítanie čísla
main = do
  line <- getLine
  let n = read line :: Int
  print (n * 2)

-- opakovanie = rekurzia
getInt :: IO Int
getInt = do
  line <- getLine
  case readMaybe line of
    Just n  -> pure n
    Nothing -> do
      putStrLn "Zle, znova:"
      getInt

-- cyklus do ukončovacieho slova
loop :: IO ()
loop = do
  line <- getLine
  if line == "koniec"
    then putStrLn "Koniec."
    else do
      putStrLn (reverse line)
      loop

-- rekurzia, ktorá zbiera výsledky
askAll :: [String] -> IO [String]
askAll []     = pure []
askAll (q:qs) = do
  a  <- ask q
  as <- askAll qs
  pure (a : as)

-- súbor z argumentu
main = do
  args <- getArgs
  case args of
    [file] -> do
      content <- readFile file
      print (length (lines content))
    _ -> putStrLn "Pouzitie: runghc main.hs <subor>"

Prepis do ↔ >>=

do >>=
x <- akcia akcia >>= \x -> ...
akcia (bez výsledku) akcia >> ...
let x = v let x = v in ...
posledný riadok posledný výraz
main = do                              main = putStrLn "Meno?"
  putStrLn "Meno?"                       >> getLine
  name <- getLine                        >>= \name ->
  let msg = "Ahoj " ++ name                let msg = "Ahoj " ++ name
  putStrLn msg                             in putStrLn msg

Pravidlá a časté chyby

  • Hodnotu z IO vybalíš len vnútri inej IO akcie cez <-. Z IO String nikdy nevznikne obyčajný String v čistej funkcii.
  • let x = getLine pomenuje akciu, nevykoná ju. Na výsledok treba x <- getLine.
  • x <- 5 + 1 je chyba, lebo vpravo od <- musí byť akcia. Na čistý výpočet treba let.
  • Posledný riadok do bloku musí byť výraz (akcia), nie x <- ... ani let.
  • if v do musí mať else. Vetva s viacerými akciami potrebuje vlastné do.
  • return nekončí funkciu, len zabalí hodnotu: return 5 :: IO Int.
  • map print xs iba vytvorí zoznam akcií. Na vykonanie treba mapM_ print xs.
  • Spájanie textu a čísla: "Vek: " ++ show n, nie "Vek: " ++ n.
  • read potrebuje vedieť cieľový typ: read s :: Int, alebo ho odvodí zo signatúry.

Kompilácia a spustenie

Príkaz Čo robí
ghc main.hs skompiluje do spustiteľného súboru
runghc main.hs arg1 spustí bez kompilácie s argumentmi
ghci main.hs interaktívne, :r načíta zmeny, :t ukáže typ, :k druh
cabal init, cabal run projekt s balíkmi (napr. random)

6. Monády

class Monad m where
  (>>=)  :: m a -> (a -> m b) -> m b
  (>>)   :: m a -> m b -> m b
  return :: a -> m a

do notácia funguje v každej monáde, nielen v IO.

Monáda >>= urobí return x Kedy sa zastaví
IO vykoná akciu a pošle výsledok ďalej akcia vracajúca x nikdy
Maybe pri Just x pošle x ďalej Just x pri prvom Nothing
Either e pri Right x pošle x ďalej Right x pri prvom Left (vráti chybu)
[] (zoznam) pre každý prvok, výsledky spojí [x] prázdny zoznam
instance Monad Maybe where
  Just x  >>= k = k x
  Nothing >>= _ = Nothing

instance Monad (Either e) where
  Left l  >>= _ = Left l
  Right r >>= k = k r

instance Monad [] where
  xs >>= f = concat (map f xs)

Príklady

-- Maybe: reťazenie, ktoré sa môže kedykoľvek zastaviť
calc a b c = do
  x <- safeDiv a b
  y <- safeDiv x c
  pure (y + 1)
-- calc 100 5 2 == Just 11,  calc 100 0 2 == Nothing

-- reťazenie lookup (prednáška 7)
studentStatus name = do
  sid    <- lookup name studentIDs
  status <- lookup sid statuses
  lookup status statusNames

-- Either: prvá chyba sa vráti
addStrings a b = do
  x <- parseNum a          -- Left "..." tu ukončí výpočet
  y <- parseNum b
  pure (x + y)

-- zoznam: všetky kombinácie
pairs xs ys = do
  x <- xs
  y <- ys
  pure (x, y)
-- to isté ako [(x, y) | x <- xs, y <- ys]

-- mapM v Maybe
mapM readMaybe ["1","2"] :: Maybe [Int]   -- Just [1,2]
mapM readMaybe ["1","x"] :: Maybe [Int]   -- Nothing

Functor, Applicative a Monad

Trieda Operátor Čo robí Príklad Výsledok
Functor fmap, <$> obyčajná funkcia na zabalenú hodnotu (+1) <$> Just 2 Just 3
Applicative <*> zabalená funkcia na zabalenú hodnotu Just (+1) <*> Just 2 Just 3
Monad >>= funkcia, ktorá vráti zabalenú hodnotu Just 4 >>= safeDiv 8 Just 2
fmap (*2) [1,2,3]               -- [2,4,6]
fmap length (Right "abc")       -- Right 3
fmap length (Left 7)            -- Left 7
[(*2), (+3)] <*> [1, 2, 3]      -- [2,4,6,4,5,6]
fmap (*2) (+1) 5                -- 12  (pri funkciách je fmap skladanie)

Zákony monád

Zákon Rovnica
ľavá identita return a >>= h = h a
pravá identita m >>= return = m
asociativita (m >>= g) >>= h = m >>= (\x -> g x >>= h)

Analógie z iných jazykov

Haskell Java JavaScript
>>= flatMap() na Optional a Stream then() na Promise
return Optional.of(), Stream.of() Promise.resolve()
fmap map() then() s obyčajnou hodnotou

7. Jazyk lambda (prednáška 5)

Slajdy k tejto prednáške som nemal k dispozícii. Toto je štandardná teória, zápis si porovnaj s prednáškou.

Pojem Zápis Haskell
premenná x x
abstrakcia (funkcia) λx. M \x -> M
aplikácia M N m n
viac parametrov λx. λy. M \x y -> M
  • Aplikácia sa združuje zľava: M N P = (M N) P.
  • Telo abstrakcie siaha čo najďalej doprava: λx. M N = λx. (M N).
  • Viazaná premenná je pod λ s rovnakým menom, inak je voľná. Vo výraze λx. x y je x viazaná a y voľná.
  • Alfa konverzia premenuje viazanú premennú: λx. x ≡ λy. y.
  • Beta redukcia dosadí argument: (λx. M) N → M[x := N], napr. (λx. x x) a → a a.
  • Eta redukcia: λx. f x → f, ak x nie je voľné v f. V Haskelli \x -> show x = show.
  • Normálna forma je výraz, ktorý sa už nedá redukovať. Normálne poradie redukuje najľavejší vonkajší redex a vždy ju nájde, ak existuje.
TRUE  = λt. λf. t                 0 = λf. λx. x
FALSE = λt. λf. f                 1 = λf. λx. f x
AND   = λp. λq. p q p             2 = λf. λx. f (f x)
NOT   = λp. p FALSE TRUE       SUCC = λn. λf. λx. f (n f x)

I = λx. x        K = λx. λy. x        S = λx. λy. λz. x z (y z)

8. Na čo nezabudnúť na písomke

  • Napíš typovú signatúru aj deriving, ak používaš == (Eq) alebo výpis (Show).
  • Vzor s konštruktorom s parametrami daj do zátvoriek: f (Leaf x), nie f Leaf x.
  • Pri Maybe a Either pokry obe možnosti: Nothing aj Just, Left aj Right.
  • Pri rekurzívnom type nezabudni na základný prípad (Leaf, Empty, Nil).
  • Pri inštancii s typovou premennou napíš zátvorky a obmedzenie: instance Show a => Show (BTree a).
  • Functor a Foldable píš pre BTree, nie pre BTree a.
  • V do bloku: <- pre akciu, let pre čistú hodnotu. Na konci musí byť akcia.
  • Čísla na text cez show, text na čísla cez read alebo readMaybe s typom.

Top