Skip to content

← Späť na FP Labs

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

  1. Základné pojmy
  2. Krok 1 – Aplikatívne funktory
  3. Krok 2 – Monáda Maybe
  4. Krok 3 – Bezpečný výpočet výrazu
  5. Krok 4 – Typ chyby (Either)
  6. Krok 5 – Zoznam ako monáda
  7. Doplňujúca úloha
  8. 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 maybeArea a makeRectangle, 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á area na hodnotu v Just, Nothing nechá tak
  • Rectangle (konštruktor) je tiež funkcia s 2 argumentmi → <$> + jedno <*>
  • verzia bez operátora:
maybeArea r = case r of
    Nothing   -> Nothing
    Just rect -> Just (area rect)
> 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.

allRectangles :: [Double] -> [Double] -> [Rectangle]
allRectangles ws hs = Rectangle <$> ws <*> hs

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 getTaxOwed pomocou >>=.

getTaxOwedV1 :: String -> Maybe Double
getTaxOwedV1 name =
    lookup name phonebook
      >>= \number       -> lookup number governmentDatabase
      >>= \registration -> lookup registration taxDatabase
  • lookup name phonebook vráti Maybe String
  • >>= \number -> ... – ak je Just number, pokračuje s number, pri Nothing skončí
  • všetky Nothing -> Nothing vetvy robí >>= za nás

Úloha 2.2

Prepíšte getTaxOwed pomocou do-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áti Nothing.

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 x
  • lookup v env už vracia Maybe Double, nič netreba baliť
  • (+) <$> ... <*> ... – sčíta dve Maybe hodnoty ((+) je funkcia s 2 argumentmi)
  • Div potrebuje pozrieť na hodnotu y (či je 0), preto do
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ú.

data EvalError
    = UnknownVariable String
    | DivisionByZero
    deriving Show

Úloha 4.1

Verzia eval, ktorá vracia Either 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

neighbors vrá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).

> neighbors myGraph 1
[2,3]
> neighbors myGraph 9
[]

Úloha 5.2

walks graph k start – všetky cesty z start s presne k hranami (vrcholy sa môžu opakovať). Pre k = 0 je 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 suseda
  • rest <- walks ... – rekurzia, cesta o 1 hranu kratšia
  • pure (start : rest) – pridá aktuálny uzol na začiatok cesty
  • uzol bez susedov → neighbors dá [] → vetva zmizne
> walks myGraph 0 1
[[1]]
> walks myGraph 2 1
[[1,2,3],[1,3,1]]

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 walks tak, 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 je path, prvý prvok cur
  • [] v zoznamovej monáde = „táto vetva nedáva výsledok“
  • na konci reverse, aby cesta išla od start
> walksUnique myGraph 2 1
[[1,2,3]]                 -- [1,3,1] vypadla, 1 sa opakuje

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)] –

Top