Pane Tähele! Intuitsioon: monaadid on üldine järjestikuse arvutuse mudel, milles eristatakse avaldise kõrvaltoimet ja tagastusväärtust. Võimaliku kõrvaltoime defineerib konkreetne monaadi isend. Näiteks, IO monaadi kõrvalefekt on arvuti seisundi muutumine.
Sõna monaadiline kasutatakse kahes tähenduses:
Näiteks sisendi ja väljundiga arvutamisel kasutame IO monaadi. Samas,
abifunktsioonid nagu mapM defineerime kõikide monaadide jaoks
korraga.
Põhjused monaadide kasutamiseks:
Klassikaline näide monaadilisest koodist on parsimise monaad, mis on monaadiline mõlemas tähenduses. Parseri kood kirjutatakse do-notatsioonis, mille tõttu on see selge ja lihtsalt loetav. Samas saab parserile ette anda monaadi, milles väärtust parsitakse.
Alustame monaadi definitsioonist Haskellis ja seejärel vaatame näiteid.
Haskellis on monaadid tüübiklass Monad instantsid, kus
Monad on Functor ja Applicative ülemklass.
Funktori instantsid on tüübiteisendajad, millel on defineeritud funktsioon
fmap (sama mis binaarne operaator
<$>) ja operaator
(<$).
| class Functor (f :: * -> *) where fmap :: (a -> b) -> f a -> f b (<$) :: a -> f b -> f a x <$ y = fmap (const x) y f <$> x = fmap f x |
Pane Tähele! Ka tüüpidel on tüübid — neid nimeteatakse liikideks (i.k.
kind). Funktori tüübiargument f on liigiga * -> *,
mis tähendab et see võtab argumendiks tüübi ja tagastab samuti mingi tüübi.
Funktorid on niisiis struktuurid, millel on defineeritud fmap. Nagu
suurem osa konteiner andmestruktuure on ka listid ja Maybe-d
funktorid.
fmap listil ja Maybe-lstinline| instance Functor [] where fmap = map instance Functor Maybe where fmap f Nothing = Nothing fmap f (Just x) = Just (f x) |
Selleks, et funktorite käitumine oleks programmeerijale paremini ennustatav, käivad tüübiklassidega kaasas võrrandid, mis iga instants peaks rahuldama. Võrrandite kehtivust süsteem ei kontrolli — seda peab tegema programmeerija ise.
fmap id | = | id |
fmap (f . g) | = | fmap f . fmap g
|
Esimene võrrand tähendab seda, et kui võtta fmap argumendiks
identsusfunktsioon, siis jäetakse funktori väärtus samaks. Teine võrrand
tähendab, et saame järjestikused fmap-id võtta kokku järjestikuseks
argumentfunktsiooni rakenduseks. Monaadi mõttes teisendab fmap
ainult tagastusväärtust ja jätab seisundi muutmata. Ning kui ka tagastusväärtus
jäetakse samaks siis ei muudeta kokkuvõttes midagi.
Aplikatiivsetel funktoritel on defineeritud lisaks funktsioonile
fmap ka funktsioon pure ja rakenduse operaator
(<*>).
| class Functor f => Applicative (f :: * -> *) where pure :: a -> f a (<*>) :: f (a -> b) -> f a -> f b (*>) :: f a -> f b -> f b x *> y = const id <$> x <*> y (<*) :: f a -> f b -> f a x <* y = const <$> x <*> y |
Kui funktorite puhul mõtlesime, et konteineris on andmed, siis aplikatiivsete
funktorite puhul on konteineris ka funktsioonid. Operaator (<*>)
rakendabki konteineris olevad funktsioonid teises konteineris olevate andmetega
ja saab tulemuseks tagastusväärtuste konteineri. Lisaks on funktsiooniga
pure võimalik teha suvalise väärtusega kõrvalefektide suhtes
neutraalset konteinerit. Instantsid peavad rahuldama järgnevaid võrrandeid.
pure id <*> v | = | v |
pure (.) <*> u <*> v <*> w | = | u <*> (v <*> w) |
pure f <*> pure x | = | pure (f x) |
u <*> pure y | = | pure ($ y) <*> u
|
Kokkuvõtvalt: funktsiooniga pure tehtud väärtus ei tekita kõrvalefekti kui seda kombineerida operaatoriga (<*>).
Maybe kõrvalefektiks on ebaõnnestumine.| instance Applicative [] where pure x = [ x ] fs <*> xs = [ f x | f <- fs, x <- xs ] instance Applicative Maybe where pure x = Just x (Just f) <*> m = fmap f m Nothing <*> m = Nothing |
Monaad on aplikatiivne funktor, millel on defineeritud veel funktsioon fail ning nn. bind operaator (>>=). Funktsioon fail võtab argumendiks sõne ning tagastab ebaõnnestumise kõrvalefektiga väärtuse.
| class Applicative m => Monad (m :: * -> *) where (>>=) :: m a -> (a -> m b) -> m b fail :: String -> m a (>>) :: m a -> m b -> m b return :: a -> m a return = pure x >> y = x >>= const y |
Bind operaatori kirjeldamiseks peame seletama, mis juhtub kõrvalefektidega ja mis juhtub tagastusväärtustega. Esimese argumendi tagastusväärtus antakse teisele argumendile parameetriks; lõpptulemuse tagastusväärtus tuleb teisest argumendist. Kõrvalefektid pannakse aga kokku — eelistades esimese argumendi efekte.
fail).| instance Monad [] where fail _ = [] xs >>= f = concatMap f xs instance Monad Maybe where fail _ = Nothing Nothing >>= f = Nothing (Just x) >>= f = f x |
Monaadi seaduste kirjutamiseks kasutame operaatorit (>=>), mis on sümmeetriline versioon bind operaatorist. Selle abil saame püstitada parema- ja vasakpoolse ühiku ning assotsiatiivsuse reeglid.
| (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c (m >=> n) x = m x >>= n |
return >=> g | = | g |
f >=> return | = | f |
(f >=> g) >=> h | = | f >=> (g >=> h)
|
Olgu meil andmetüüp Avaldis, mis tähistab muutujatega aritmeetilist
avaldist. Operaatoriteks on liitmine, lahutamine, korrutamine ja jagamine.
Kasutada saame konstante ja sõne järgi eristatavaid muutujaid.
| data Op = Pluss | Miinus | Korda | Jagada deriving (Show, Eq) data Avaldis = Konst Double | Muutuja String | BinOp Op Avaldis Avaldis deriving (Show, Eq) |
Näiteks on toodud avaldis y*20/x . Kui x=5 ja
y=4 siis avaldise väärtus on 16. Seisundi edasiandmiseks kasutame
funktsioone tüübiga String -> Maybe Double.
| aval :: Avaldis aval = BinOp Korda (Muutuja "x") (BinOp Jagada (Konst 20.0) (Muutuja "x")) seisund :: String -> Maybe Double seisund "x" = Just 5 seisund "y" = Just 4 seisund _ = Nothing |
Tahame nüüd selliseid avaldisi väärtustada, ehk peame kirjutama funktsiooni tüübiga (String -> Maybe Double) -> Avaldis -> Maybe Double. Ilma monaadideta tuleks kirjutada järgnev kood:
| vaartusta0 :: (String -> Maybe Double) -> Avaldis -> Maybe Double vaartusta0 f (Konst k) = Just k vaartusta0 f (Muutuja m) = f m vaartusta0 f (BinOp op x y) = case vaartusta0 f x of Just a -> case vaartusta0 f y of Just b -> fopMaybe op a b Nothing -> Nothing Nothing -> Nothing |
Kasutades monaade saame binaarse operaatori juhtu kirjutada selgemalt:
| vaartusta1 :: (String -> Maybe Double) -> Avaldis -> Maybe Double vaartusta1 f (Konst k) = return k vaartusta1 f (Muutuja m) = f m vaartusta1 f (BinOp op x y) = do a <- vaartusta1 f x b <- vaartusta1 f y fopMaybe op a b |
Sellist arvutust saame teha veel rohkem monaadiliseks, kui me väldime konkreetselt Maybe monaadi mainimist.
| fopMaybe2 :: Monad m => Op -> Double -> Double -> m Double fopMaybe2 Jagada x 0 = fail "nulliga jagamine" fopMaybe2 op x y = return (fop op x y) vaartusta2 :: Monad m => (String -> m Double) -> Avaldis -> m Double vaartusta2 f (Konst k) = return k vaartusta2 f (Muutuja m) = f m vaartusta2 f (BinOp op x y) = do a <- vaartusta2 f x b <- vaartusta2 f y fopMaybe2 op a b |
[] monaadEelnevat näidet rakendada seisundile tüübiga String -> [Double],
kus list tähistab mitmesust. Sellise seisundiga (kus x=5 või 0 ning y=1
või 4) saame, et avaldise y*20/x väärtus on 4 või 16. Pane tähele, et
juht kus x=0 eemaldatakse, kuna nulliga ei saa jagada.
| seisund2 :: String -> [Double] seisund2 "x" = [5,0] seisund2 "y" = [1,4] seisund2 _ = [] |
Listimonaadi do-süntaks on väga lähedane listikomprehensioonile. Nii võime
näiteks lehel haskell.org oleva näide saab kirjutada ka niimoodi
(kasutades mooduli Control.Monad funktsiooni guard).
| primes = filterPrime [2..] where filterPrime (p:xs) = p : filterPrime (do x <- xs guard (x `mod` p /= 0) return x) |
| vaartusta3 :: Avaldis -> State (String -> Maybe Double) (Maybe Double) vaartusta3 f (Konst k) = return k vaartusta3 f (Muutuja m) = f m vaartusta3 f (BinOp op x y) = do a <- vaartusta3 f x b <- vaartusta3 f y fopMaybe op a b |
| return :: a -> State s a (>>=) :: (State s a) -> (a -> State s b) -> State s b get :: State s s put :: s -> State s () evalState :: State s a -> s -> a |
| data State s a = St s a return :: a -> State s a return x s = (x,s) get :: State s s get s = (s,s) put :: s -> State s () put x s = ((),x) runState (return 'X') 1 |
IO monaadParsec monaadSelles alampeatükis vaatame parsimismonaadi Parsec