Cvičenie 8 – Aplikatívne funktory a monády¶
Useful Files¶
Riešenia všetkých úloh sú v main8.hs (spustenie: runghc main8.hs, alebo ghci main8.hs a potom main).
Navigation¶
- Základné pojmy
- Krok 1 – Aplikatívne funktory
- Krok 2 – Monáda Maybe
- Krok 3 – Bezpečný výpočet výrazu
- Krok 4 – Typ chyby (Either)
- Krok 5 – Zoznam ako monáda
- Doplňujúca úloha
- Prehľad príkazov
1. Základné pojmy¶
| pojem | význam |
|---|---|
| kontext | „obal“ okolo hodnoty: Maybe (hodnota môže chýbať), [] (viac hodnôt), Either e (hodnota alebo chyba), IO (akcia) |
Functor |
vie aplikovať obyčajnú funkciu na hodnotu v obale: fmap / <$> |
Applicative |
navyše vie aplikovať funkciu s viacerými argumentmi na viac hodnôt v obale: <*>, pure |
Monad |
navyše vie reťaziť kroky, kde ďalší krok závisí od výsledku predošlého: >>=, do |
pure x / return x |
zabalí x do kontextu: Just x, [x], Right x |
| operátor | typ | význam |
|---|---|---|
<$> |
(a -> b) -> f a -> f b |
funkcia na hodnotu v obale |
<*> |
f (a -> b) -> f a -> f b |
funkcia v obale na hodnotu v obale |
>>= |
m a -> (a -> m b) -> m b |
vybalí hodnotu a pošle ju do ďalšieho kroku |
Ako čítať f <$> a <*> b <*> c: odmysli si operátory, dostaneš f a b c, len hodnoty sú v obale.
Vždy je jedno <$> (pri prvom argumente) a za ním jedno <*> na každý ďalší argument.
Čo robí kontext:
| typ | keď niečo chýba / zlyhá | pri viacerých hodnotách |
|---|---|---|
Maybe |
celý výsledok je Nothing |
– |
Either e |
celý výsledok je prvé Left chyba |
– |
[] |
prázdny zoznam → [] |
všetky kombinácie |
2. Krok 1 – Aplikatívne funktory¶
add :: Int -> Int -> Int
add x y = x + y
result = add <$> Just 3 <*> Just 5 -- Just 8
result2 = pure add <*> Just 3 <*> Just 5 -- Just 8 (to isté)
Úloha 1.1¶
Definujte
maybeAreaamakeRectangle, ktoré pracujú s chýbajúcimi hodnotami.
data Rectangle = Rectangle Double Double
deriving (Show, Eq)
area :: Rectangle -> Double
area (Rectangle w h) = w * h
maybeArea :: Maybe Rectangle -> Maybe Double
maybeArea r = area <$> r
makeRectangle :: Maybe Double -> Maybe Double -> Maybe Rectangle
makeRectangle w h = Rectangle <$> w <*> h
area <$> r– zavoláareana hodnotu vJust,Nothingnechá takRectangle(konštruktor) je tiež funkcia s 2 argumentmi →<$>+ jedno<*>- verzia bez operátora:
> maybeArea (Just (Rectangle 2 3))
Just 6.0
> maybeArea Nothing
Nothing
> makeRectangle (Just 2) (Just 3)
Just (Rectangle 2.0 3.0)
> makeRectangle (Just 2) Nothing
Nothing
Pozor na zátvorky: makeRectangle Just 2 Just 3 je chyba (4 argumenty), správne makeRectangle (Just 2) (Just 3).
Úloha 1.2¶
Vytvorte všetky obdĺžniky, ktorých šírka je z jedného zoznamu a výška z druhého.
Rovnaký zápis ako pri Maybe, ale pri zozname <*> skúsi každú šírku s každou výškou.
> allRectangles [1, 2] [5, 6]
[Rectangle 1.0 5.0,Rectangle 1.0 6.0,Rectangle 2.0 5.0,Rectangle 2.0 6.0]
3. Krok 2 – Monáda Maybe¶
Pri Maybe operátor >>= reťazí kroky, ktoré môžu zlyhať: ak hocijaký vráti Nothing, celý výsledok je Nothing.
Pôvodná verzia s vnorenými case:
getTaxOwed :: String -> Maybe Double
getTaxOwed name =
case lookup name phonebook of
(Just number) -> case lookup number governmentDatabase of
(Just registration) -> lookup registration taxDatabase
Nothing -> Nothing
Nothing -> Nothing
Úloha 2.1¶
Zjednodušte
getTaxOwedpomocou>>=.
getTaxOwedV1 :: String -> Maybe Double
getTaxOwedV1 name =
lookup name phonebook
>>= \number -> lookup number governmentDatabase
>>= \registration -> lookup registration taxDatabase
lookup name phonebookvrátiMaybe String>>= \number -> ...– ak jeJust number, pokračuje snumber, priNothingskončí- všetky
Nothing -> Nothingvetvy robí>>=za nás
Úloha 2.2¶
Prepíšte
getTaxOwedpomocoudo-notácie.
getTaxOwedV2 :: String -> Maybe Double
getTaxOwedV2 name = do
number <- lookup name phonebook
registration <- lookup number governmentDatabase
lookup registration taxDatabase
Rovnaké ako pri IO: x <- ... vybalí hodnotu z Just. Ak niektorý riadok dá Nothing, ďalšie sa nevykonajú.
> getTaxOwedV2 "Fred"
Just 64.65
> getTaxOwedV2 "Bob" -- KE215AB nie je v taxDatabase
Nothing
> getTaxOwedV2 "Nikto"
Nothing
Prečo <$>/<*> nestačí: pri <*> sú argumenty nezávislé. Tu druhé hľadanie potrebuje výsledok prvého (number), preto treba >>= / do.
4. Krok 3 – Bezpečný výpočet výrazu¶
data Expr
= Num Double
| Var String
| Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
| Div Expr Expr
| Neg Expr
deriving Show
type Env = [(String, Double)]
type Env = ... je len iný názov pre existujúci typ (alias), nie nový typ.
Úloha 3.1¶
eval :: Env -> Expr -> Maybe Double– pri neznámej premennej alebo delení nulou vrátiNothing.
eval :: Env -> Expr -> Maybe Double
eval _ (Num x) = pure x
eval env (Var v) = lookup v env
eval env (Add a b) = (+) <$> eval env a <*> eval env b
eval env (Sub a b) = (-) <$> eval env a <*> eval env b
eval env (Mul a b) = (*) <$> eval env a <*> eval env b
eval env (Neg a) = negate <$> eval env a
eval env (Div a b) = do
x <- eval env a
y <- eval env b
if y == 0
then Nothing
else pure (x / y)
pure x=Just xlookup v envuž vraciaMaybe Double, nič netreba baliť(+) <$> ... <*> ...– sčíta dveMaybehodnoty ((+)je funkcia s 2 argumentmi)Divpotrebuje pozrieť na hodnotuy(či je 0), pretodo
env1 = [("x", 4), ("y", 2)]
> eval env1 (Add (Var "x") (Num 1))
Just 5.0
> eval env1 (Div (Var "x") (Var "y"))
Just 2.0
> eval env1 (Var "z")
Nothing
> eval env1 (Div (Num 1) (Num 0))
Nothing
5. Krok 4 – Typ chyby (Either)¶
Maybe povie len že nastala chyba, Either povie aj akú.
Úloha 4.1¶
Verzia
eval, ktorá vraciaEither EvalError Double.
evalE :: Env -> Expr -> Either EvalError Double
evalE _ (Num x) = pure x
evalE env (Var v) =
case lookup v env of
Nothing -> Left (UnknownVariable v)
Just x -> Right x
evalE env (Add a b) = (+) <$> evalE env a <*> evalE env b
evalE env (Sub a b) = (-) <$> evalE env a <*> evalE env b
evalE env (Mul a b) = (*) <$> evalE env a <*> evalE env b
evalE env (Neg a) = negate <$> evalE env a
evalE env (Div a b) = do
x <- evalE env a
y <- evalE env b
if y == 0
then Left DivisionByZero
else pure (x / y)
Oproti Maybe sa zmenilo len:
Maybe |
Either |
|---|---|
pure x = Just x |
pure x = Right x |
Nothing |
Left DivisionByZero |
lookup v env |
case → Left (UnknownVariable v) |
<$>, <*> a do fungujú rovnako – pri prvom Left sa výpočet zastaví.
> evalE env1 (Mul (Var "x") (Neg (Var "y")))
Right (-8.0)
> evalE env1 (Var "z")
Left (UnknownVariable "z")
> evalE env1 (Div (Num 1) (Num 0))
Left DivisionByZero
(V main8.hs sa volá evalE, lebo dve funkcie v jednom súbore nemôžu mať rovnaký názov.)
6. Krok 5 – Zoznam ako monáda¶
Pri zozname x <- xs v do znamená „pre každé x zo zoznamu“ a výsledky všetkých vetiev sa spoja.
type Graph = [(Int, [Int])]
myGraph :: Graph
myGraph = [(1, [2, 3]), (2, [3]), (3, [1])]
-- 1 -> 2, 1 -> 3, 2 -> 3, 3 -> 1
Úloha 5.1¶
neighborsvráti susedov uzla, ak uzol nie je v grafe, vráti[].
neighbors :: Graph -> Int -> [Int]
neighbors graph node =
case lookup node graph of
Nothing -> []
Just ns -> ns
Kratšie: neighbors graph node = maybe [] id (lookup node graph).
Úloha 5.2¶
walks graph k start– všetky cesty zstarts presnekhranami (vrcholy sa môžu opakovať). Prek = 0je výsledok[[start]].
walks :: Graph -> Int -> Int -> [[Int]]
walks _ 0 start = [[start]]
walks graph k start = do
next <- neighbors graph start -- pre každého suseda
rest <- walks graph (k - 1) next -- pre každú cestu z neho
pure (start : rest)
next <- neighbors ...– rozvetví výpočet pre každého susedarest <- walks ...– rekurzia, cesta o 1 hranu kratšiapure (start : rest)– pridá aktuálny uzol na začiatok cesty- uzol bez susedov →
neighborsdá[]→ vetva zmizne
Postup pre walks myGraph 2 1: susedia 1 sú 2, 3 →
z 2 (k=1): sused 3 → [2,3] → [1,2,3];
z 3 (k=1): sused 1 → [3,1] → [1,3,1].
7. Doplňujúca úloha¶
Úloha A.1¶
Upravte
walkstak, aby vrátila len cesty bez opakovania vrcholov.
walksUnique :: Graph -> Int -> Int -> [[Int]]
walksUnique graph k start = go k [start]
where
go 0 path = [reverse path]
go n path@(cur:_) = do
next <- neighbors graph cur
if next `elem` path
then [] -- slepá vetva, zahodí sa
else go (n - 1) (next : path)
go _ [] = []
path– doteraz navštívené uzly (otočene, posledný je na začiatku →cur)path@(cur:_)– celý zoznam jepath, prvý prvokcur[]v zoznamovej monáde = „táto vetva nedáva výsledok“- na konci
reverse, aby cesta išla odstart
8. Prehľad príkazov¶
| príkaz | čo robí | príklad | výstup |
|---|---|---|---|
fmap / <$> |
funkcia na hodnotu v obale | (+1) <$> Just 2 |
Just 3 |
(+1) <$> [1,2] |
[2,3] |
||
(+1) <$> Nothing |
Nothing |
||
<*> |
ďalší argument v obale | add <$> Just 3 <*> Just 5 |
Just 8 |
(+) <$> [1,2] <*> [10,20] |
[11,21,12,22] |
||
pure |
zabalí hodnotu | pure 5 :: Maybe Int |
Just 5 |
pure 5 :: [Int] |
[5] |
||
>>= |
reťazenie krokov | Just 4 >>= \x -> Just (x*2) |
Just 8 |
Nothing >>= \x -> Just (x*2) |
Nothing |
||
[1,2] >>= \x -> [x, x*10] |
[1,10,2,20] |
||
do (Maybe) |
krajší zápis >>= |
do { x <- Just 2; pure (x+1) } |
Just 3 |
do (zoznam) |
všetky kombinácie | do { x <- [1,2]; y <- "ab"; pure (x,y) } |
[(1,'a'),(1,'b'),(2,'a'),(2,'b')] |
lookup |
hľadanie v zozname dvojíc | lookup 2 [(1,"a"),(2,"b")] |
Just "b" |
maybe |
spracuje Maybe |
maybe [] id (Just [1]) |
[1] |
Left / Right |
chyba / úspech | Left DivisionByZero |
– |
type |
alias typu | type Env = [(String, Double)] |
– |