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