Monád (funkcionális programozás)

A számítógép-programozásban a monád a funkcionális paradigma tervmintája. Definiálja, hogyan használhatók együtt függvények, akciók, be- és kimenetek ahhoz, hogy generikus típust építsenek fel. Szerkezete a következő:

• Adattípust definiál, és megadja, hogyan kombinálhatók ennek értékei.
• Függvényeket hoz létre, amelyek használják a megadott adattípust, és akciókba csoportosítja őket, az első pont szabályai szerint.

A monád tartalmazhatja a benne definiált adattípus értékeit, a hozzá tartozó specifikus számításokkal, amelyek tipikusan a típus speciális eseteit kezelik. Például a Maybe monád változókat burkol, amiknek lehet null értékük, vagy opcionális típust reprezentálnak, és automatikusan biztosítja, hogy ne adódjanak át null értékek olyan függvényeknek, amelyek nem tudják őket kezelni. Ezzel alternatívát ad a hagyományos kivételkezeléssel (throw-catch) szemben. Egy másik példa a List monád, ahol az üres lista a monádban megadott konstans, és a cons operátor fejelemként hozzáfűz a listához egy elemet.

A monád a számításokat szekvenciális szerkezetben írja le; a monád határozza meg, hogy mi történik az utasítások összekapcsolásakor. Ez lehetővé teszi csővezetékek építését, amelyek lépések (akciók) sorozatával dolgoznak fel adatokat, ahol minden akciót dekorálnak a monád által definiált további feldolgozási szabályokkal. A monád kötelezően definiál két operátort, a return és a bind operátorokat. A return operátor létrehoz értékeket, a bind operátor kapcsolja össze az akciókat, ez utóbbit kísérik a monád törvények, amelyek szükségesek ahhoz, hogy a bind operátor általi összekapcsolás megfelelően működjön.

A monádok lehetővé tesznek egy olyan programozási stílust, amiben a programokat jól komponálható részekből hozzák létre, rugalmasan komponálva a lehetséges akciókat, amik egy adott adattípuson működnek. Emiatt a monádokat programozható pontosvesszőnek is nevezik. Több programozási nyelvben pontosvessző operátor kapcsol össze utasításokat. A monád hasonlítható futószalaghoz is, ami az egyes lépések között szállítja az adatokat.

Tisztán funkcionális programok használhatnak monádokat arra, hogy szekvenciális eljárásokat építsenek fel, az imperatív-strukturált programozási paradigmákhoz hasonlóan. Sok ismert programozási fogalom leírható monádokkal anélkül, hogy rontanák az átláthatóságot, például a mellékhatások, mint az írás-olvasás, értékadás, kivételkezelés, parszolás, nemdeterminisztikusság, konkurrencia, folytatások, vagy tartományspecifikus nyelvek. Monádokkal mindezek definiálhatók tisztán funkcionális módon, anélkül, hogy ezzel ki kellene terjeszteni a nyelv szemantikáját. Funkcionális programozási nyelvek, mint a Haskell szabványosan tartalmazzák a monádokat, ami lehetővé teszi, hogy a programozók újrahasználják formális definíciók hosszabb szakaszait, és több különböző könyvtárban használják újra ugyanazokat az interfészeket függvények kombinálására.

A fogalom és elnevezése a kategóriaelméletből származik, ahol a monádok a funktorok speciális fajtája, leképezések kategóriák között. A funkcionális programozásban a kategóriaelmélet erős monádjai jelennek meg. Cikkünkben a monádokat a Haskellen keresztül mutatjuk be, egyéb programnyelvi terminológiát, ötleteket és példákat is fogadunk.

Áttekintés

Egy monádot egy típuskonstruktor operátor, és két művelet, a kötés (bind), és a return (nevezik unitnak is) hoz létre.

• A return unáris művelete vesz egy egyszerű típusértéket, és a konstruktort használva konténerbe teszi, ezzel monadikus értéket hozva létre, például M a.
• A kötés bináris művelete, jelben >>=, egy monadikus értéket és egy függvényt, ami felhasználja az értéket.

• A kötés kivonja a beburkolt értéket, és átadja a függvénynek.
• A függvény által létrehozott értéket monadikussá teszi, ami így átadható a következő kötés operátornak.

Ezekkel az elemekkel létrehozható egy csővezeték (szekvencia), ami több bind operátort hív egymás után. Minden függvényhívás a kivonatolt értéket használja, és a bind operátor kezeli a visszaadott monadikus értéket, ami a következő lépésnek adódik át. Két függvényhívás között a bind operátor további átalakításokat is végezhet, amiket a meghívott függvény nem csinált. Ez lehetővé teszi a végrehajtás pontosabb ellenőrzését, például hogy egy függvényt csak bizonyos esetekben hívjon meg, vagy a függvényhívásokat bizonyos sorrendben hajtsa végre.

Például a következő kód definiál egy 1=x//y biztonságos osztás műveletet, ami a Maybe monád és konstruktorainak segítségével elkerüli a nullával való osztást. A két konstruktor közül a Just jelzi a művelet eredményét, és a Nothing a művelet sikertelenségét. A monadikus értékek alakja Nothing vagy Just i, ahol i egész. Az x és y monadikus értékekből kivonatolt a és b egyszerű értékeken csak akkor végzi el az osztást, ha b nem nulla.

-- Defining a safe division operator "//" (a "monadic function") using the Maybe monad
                                      -- The expression x // y is defined as the
x // y =                              -- ''bind'' binary operator (>>=) of the ''Maybe'' monad
   x >>= (\a ->                       -- which takes as parameters 'x' and an anonymous function
     y >>= (\b ->                     -- which divides x by y.
       if b == 0 then Nothing else Just (a / b))) -- The result value has type Maybe (Number)

-- Example usages ("pipelines")
Nothing // Just 10 -- This expression returns Nothing (by definition of the ''bind'' operator (>>=) in the Maybe monad)
Just 10 // Just 5 -- This expression returns Just 2 (by definition of the // operator)
Just 10 // Just 0 -- This expression returns Nothing (by definition of the // operator)
(Just 10 // Just 0) // Just 2 -- This expression, a pipeline of two composed "//" calls, returns Nothing

A negyedik példa kifejezésben egy csővezeték két biztonságos osztást kapcsol össze; az első osztás eredménye Nothing, ami átadódik a második biztonságos osztásnak, ekkor a végeredmény is Nothing lesz. Jegyezzük meg, hogy ezt az esetet nem kell a // operátornak kezelnie, mivel ezt a Maybe monádjának bind operátora kezeli. A bind definíciója szerint, ha az x vagy y monadikus érték Nothing, akkor az "if b == 0 ..." kifejezés nem értékelődik ki.

A monádot definiáló műveleteknek több tulajdonságnak is eleget kell tenniük, hogy a monadikus függvényeket (amelyek használják a monádot) gond nélkül össze lehessen kapcsolni. Mivel a monádok további műveleteket illeszthetnek a program logikájába, a monádok aspektusorientált programozási elemnek tekinthetők. A tartománylogikát definiálhatja az alkalmazásprogramozó, míg a szükséges mellékesen meghívott függvényeket egy előre megírt és lefordított monád nyújthatja.

Motiváló példák

A Haskell szintaktikus cukrokkal teszi kényelmesebbé a monádok létrehozását. Maga a nyelv is tartalmaz több hasznos monádot, az alábbiakban ezekből mutatunk be. A maybe monád a null értékeket tartalmazó számításokat teszi kezelhetőbbé, az I/O monád pedig a környezettel való interakciót biztosítja. A későbbi Példák szakaszban szerepel majd a JavaScript Writer monádja, amivel külön fájlba lehet írni.

Maybe monád

A Maybe monád típusa a Maybe t, ami lehet Just t, ez egy értéket reprezentál a t típusból; vagy lehet Nothing, ami nem tartalmaz értéket. A különböző típusokhoz tartozó Nothingok különbözőek.

data Maybe t = Just t | Nothing

Ezt a típust használhatjuk ellenőrzött kivételek kezelésére: ha a számításnak egy ponton nincs eredménye, akkor a végeredmény Nothing lesz. A sikeres számítás végeredménye Just x, ahol x a sikeres számítás eredménye.

A következő példában az add függvény két argumentumot ad össze, amelyek típusa Maybe Int. Ha mx és my Just értékek, akkor az eredmény Just (x + y), ha pedig valamelyik Nothing, akkor az eredmény is Nothing. Naiv megvalósításban a függvényben többször szerepel az if Nothing akkor Nothing else do valamit az x értékkel, amit a Just x burkol szerkezet, ami hosszabb függvények esetén zavaró, átláthatatlanná tevő boilerplate kód:

add :: Maybe Int -> Maybe Int -> Maybe Int
add mx my =
  case mx of
    Nothing ->    Nothing
    Just x  ->    case my of
                    Nothing ->   Nothing
                    Just y  ->   Just (x + y)

Ennek elkerülésére operációkat definiálhatunk, amelyek összeláncolják ezeket a műveleteket. A bind bináris operátor (>>=) az egyik számítás eredményét átadja egy másiknak. Mindkét műveletnél előfordulhat, hogy nincs eredmény. Ha nincs eredmény, akkor a második argumentum, a függvény nem lesz figyelembe véve, és a két függvény egymásutánjának nem lesz eredménye. Ez emlékeztet a vastagvonal operátorra, ami azonban másként működik: ha az első számítás eredménytelen, akkor a maradék eredményét kapjuk, és az első számítás el lesz dobva; különben az első számítás eredményét kapjuk. Ha van eredmény, akkor annak alakja Just x, amiből a következő függvény az x értéket kapja meg, és aminek az eredménye egy Maybe monadikus érték lesz.

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing  >>= _    =    Nothing    -- A failed computation returns Nothing
(Just x) >>= f    =    f x        -- Applies function f to value x

A Just értékkonstruktor visszaad egy értéket anélkül, hogy érintené a számítás állapotát:

return :: a -> Maybe a
return x   =   Just x       -- Wraps value x, returning a value of type (Maybe a)

Ezzel a példa:

add :: Maybe Int -> Maybe Int -> Maybe Int
add mx my =             -- Adds two values of type (Maybe Int), where each input value can be Nothing
  mx   >>=   (\x ->         -- Extracts value x if mx is not Nothing
    my   >>=   (\y ->       -- Extracts value y if my is not Nothing
      return (x + y)))  -- Wraps value (x+y), returning the sum as a value of type (Maybe Int)

A Haskell szintaktikus cukorként lehetővé teszi a do jelölést:

add :: Maybe Int -> Maybe Int -> Maybe Int
add mx my = do
  x <- mx
  y <- my
  return (x + y)

Ezzel a program úgy néz ki, mintha imperatív paradigmában írták volna, ami az 'mx' és 'my' monadikus értékek Int értékeket adja értékül az ideiglenes 'x' és 'y' változóknak, és kivételt dob, ha valamelyikük Nothing. Ekkor a teljes do kifejezés értéke Nothing. A kivételkezelést a deklaráció adja meg, mivel a paraméterek típusa Maybe Int. A try … catch blokk helyett a viselkedést a bind operátor definiálja.

Mivel ez egy gyakori operáció, azért a Haskell biztosít egy liftM2 szabványos függvényt, ami vesz két monadikus értéket, és kombinálja őket egy adott függvénnyel, így a példa írható úgy is, mint

add :: Maybe Int -> Maybe Int -> Maybe Int
add = liftM2 (+)

A liftM2 definíciójának kiírása a fenti do-jelölést használó alakot nyújtja.

IO monád

Tisztán funkcionális nyelvekben, mint a Haskell, a függvényeknek nem lehet a függvény szemantikájának részeként kívülről látható mellékhatása. Megengedett azonban, hogy jelezze, milyen mellékhatást váltana ki; ezt a leírást a hívó felhasználhatja, amikor jónak látja. Haskell nyelven az IO a akciót reprezentál, ami a típusú értéket ad vissza.

Egy IO értékre akcióként gondolhatunk, aminek argumentuma a rendszer jelenlegi állapota, és visszaad egy új rendszert, aminek állapota a függvény visszatérési értékének megfelelően megváltozott. Például a Haskell szabványos könyvtárában a doesFileExist és a removeFile függvények típusa

doesFileExist :: FilePath -> IO Bool
removeFile :: FilePath -> IO ()

A removeFile egy olyan függvény, ami egy adott FilePath esetén egy olyan IO akciót ad vissza, ami végrehajtása esetén biztosítja, hogy a fájlrendszerben ne legyen a FilePath által megadott fájl. Itt az IO () típus azt jelenti, hogy a hívó számára nem lehet érdekes a visszaadott érték. A doesFileExist függvény egy olyan akciót ad vissza, ami logikai értéket burkol, ez lehet True vagy False; az új rendszerben ha a hívó végrehajtja az akciót, akkor tudni fogja, hogy a megadott fájl létezik-e vagy sem. Így a rendszer állapota akcióról akcióra kezelhető, akciók sorozatát definiálva, amelyek állapotváltozások sorozatának lépéseiként alkalmazhatók. Ez hasonlít ahhoz, ahogy a temporális logika deklaratív feltevésekkel definiálja az idő múlását. A következő példa részletesen bemutatja, hogyan kapcsolódnak össze ezek az akciók egymással.

Le kell írnunk az összes I/O műveletek alaptípusát, azaz a szöveg kiíratását a szabványos kimenetre, szöveg beolvasását a szabványos bemenetről, fájlba írás, fájl olvasása, adatküldés hálózatban, és a többi. Továbbá komponálnunk is kell mindezeket nagyobb programok létrehozásához. Szeretnénk például azt írni, hogy:

main :: IO ()
main = do
  putStrLn "What is your name?"
  name <- getLine
  putStrLn ("Nice to meet you, " ++ name ++ "!")

Hogyan formalizáljuk ezt az intuitív jelölést? Ehhez az I/O akciókkal a következő alapműveleteket kell végrehajtani:

• Képesnek kell lennünk arra, hogy összekapcsoljunk két I/O akciót. Haskellben ezt az >> infix operátor jelzi, így például az putStrLn "abc" >> putStrLn "def" akció két sor szöveget ír ki a konzolra. Az >> típusa IO a → IO b → IO b, ami azt jelenti, hogy vesz két I/O akciót, és visszaad egyet, ami az előző kettő összekapcsolása.
• Kell, hogy legyen egy akció, aminek nincs mellékhatása, csak visszaad egy értéket, mint egy identitásfüggvény. Haskellben ez az akciókonstruktor a return.
• Meg kell tudnunk határozni, hogy az előző akciók alapján mi lesz a következő akció. Erre Haskellben a >>= (bind) operátor szolgál, aminek típusa IO a → (a → IO b) → IO b. Azaz a bal oldalon szereplő operandus egy I/O akció, ami egy a típusú értéket ad vissza. A jobb oldalon álló operandus megkapja az ez által visszaadott értéket, és ennek birtokában eldönti, hogy mi lesz a következő akció. Az eredmény akció végrehajtja az első akciót, majd a kapott érték ismeretében végrehajtja a másodikat, és visszaadja annak az eredményét.

Ez utóbbira lehet egy példa a getLine >>= putStrLn, ami beolvas egy sort a szabványos bemenetről, és kiír egy sort a szabványos kimenetre. Jegyezzük meg, hogy az >> operátor ennek egy speciális esete, ami ignorálja az első akcióból kapott értéket, és attól függetlenül hajtja végre a második akciót.

Nem feltétlenül nyilvánvaló, hogy a fenti operációk a megfelelő primitív műveletekkel kiegészítve lehetővé teszik, hogy bármilyen I/O akciót elő lehessen írni, azokat is, amelyek adatokat dolgoznak fel például lambda kifejezésekkel; if/then vezérléssel, vagy rekurzió használatával ciklussal. A fenti példát egyetlen hosszabb kifejezésként is írhatjuk:

main =
  putStrLn "What is your name?" >>
  getLine >>= \name ->
  putStrLn ("Nice to meet you, " ++ name ++ "!")

A bind operátor csővezeték jellege biztosítja, hogy a getLine és a putStrLn műveletek egyszer és egymás után legyenek végrehajtva; így a mellékhatásos beolvasás és kiíratás korrektül végbemegy a funkcionális csővezetékben. Ez igaz marad akkor is, ha a nyelv egyébként a függvényeket lustán vagy meghatározatlan sorrendben értékeli ki.

Látható, hogy az I/O és a Maybe monád definíciói hasonlóak, még ha több dologban is különböznek egymástól. A monádok a hasonlóságokat absztrakcióit valósítják meg, amelyek ezek között és más monádok között fennállnak. Az általános monád fogalom minden olyan helyzetet magában foglal, amikor a programozó mellékhatással kívánja kísérni egy tisztán funkcionális függvény végrehajtását.

Formális definíció

A monád egy konstrukció, ami képes magába ágyazni egy adott típusrendszert, így újabb típusrendszert előállítani. Ezt monadikus típusrendszernek nevezik. A monadikus típusrendszer megőrzi az eredeti típusrendszer összes fontos jellemzőjét, és monadikus jellemzőket ad hozzá.

A monád szokásos megfogalmazása Kleisli-hármasként ismert, és a következő komponensekből áll:

• Típuskonstruktor, ami minden típus számára definiálja a monadikus típus létrehozását. Haskellben a monád neve reprezentálja. Ha M monád, és típuskonstruktorát a t típusra alkalmazzuk, akkor az M t típushoz jutunk.
• Egységfüggvény (unit function), ami értéket injektál a típusból a megfelelő monadikus típusba. Polimorf típusa t→M t. Az eredmény a legegyszerűbb monadikus érték, ami teljes mértékben megőrzi az eredeti értékben foglalt információt. Az egyszerűség a monád konstruktora szerint értendő. Haskellben a neve return.
• Összekapcsoló művelet, aminek polimorf típusa (M t)→(t→M u)→(M u), Haskellben >>= reprezentálja, ami kiolvasva bind. Első argumentuma monadikus típusú, második argumentuma egy függvény, ami az első argumentumban megadott elemet megkapva monadikus értéket ad vissza, eredményként pedig ezt az értéket adja vissza. A bind művelet működése négy lépésre bontható:

• Kivonatolja az értéket a monadikus értékből.
• Erre alkalmazza a függvényt, hogy monadikus értéket kapjon.
• Ebből kivonatolja az értéket, amit átadhat egy újabb függvénynek.
• A végeredményt beburkolja, és monadikus értéket ad vissza.

Adott M típuskonstruktor esetén a legtöbb környezetben egy M a típusú értékre akcióként gondolhatunk, ami a típusú értéket ad vissza. A return operáció átvesz egy a értéket, és beburkolja egy monadikus M a értékbe. A bind művelet egy M a típusú monadikus értéket közvetít egy a → M b típusú függvénynek, hogy létrehozza az M b típusú értéket.

Monadikus törvények

Ahhoz, hogy a monád hiba nélkül működjön, a definícióknak eleget kell tenniük a monadikus törvényeknek. Az ≡ jel két Haskell kifejezés ekvivalenciáját jelzi.

• A return operáció >>= neutrális elemeként működik, így:
  • (return v) >>= f ≡ f v
  • m >>= return ≡ m
• Két függvény összekapcsolása ugyanaz, mint monadikus stílusú kompozíciójuk:
  • (m >>= f) >>= g ≡ m >>= ( \x -> (f x >>= g) )

Ugyanezek az axiómák do kifejezéssel leírva:

• do { x <- return v; f x } ≡ do { f v }
• do { x <- m; return x } ≡ do { m }
• do { y <- do { x <- m; f x }; g y } ≡ do { x <- m; y <- f x; g y }

vagy a monadikus kompozíció operátorral: (f >=> g) x = (f x) >>= g:

• return >=> g ≡ g
• f >=> return ≡ f
• (f >=> g) >=> h ≡ f >=> (g >=> h)

Alternatív definíció

A monád definiálható máshogy is. Itt a return függvény ugyanaz, mint előbb, és van még két másik, a join és az fmap. Ez áll közelebb az eredeti kategóriaelméleti megfogalmazáshoz.

• Az fmap típusa (t→u) → M t→M u, paraméterként kap egy függvényt, és visszaad egy függvényt, ami ugyanazt csinálja, mint a paraméter, csak monadikus értékekkel. Ez a függvény felemeltje.
• A join típusa M (M t)→M t, két réteg monadikus információt egyrétegűvé lapít.

A műveletek kapcsolata a következő:

fmap f m = m >>= (return . f)
join n = n >>= id

m >>= g   ≡   join (fmap g m)

Itt az m típusa M t, n típusa M (M r), f típusa t → u, és g típusa t → M v. Az fmap függvény a típusok és a függvények kategóriájában minden funktorra definiálva van. Eleget tesz a funktor törvényeknek:

fmap id   ≡   id
fmap (f . g)   ≡   (fmap f) . (fmap g)

A return függvény ugyanebben a kategóriában kijelölt funktorokat jelent, azzal együtt, hogy értékeket emel fel a funktorba. A következő azonosságnak engedelmeskedik:

return . f ≡ fmap f . return

Ez másként mondható úgy, hogy a return természetes transzformáció az identitás és az fmap között.

Továbbá a join függvény:

join . fmap join     ≡ join . join
join . fmap return   ≡ join . return = id
join . fmap (fmap f) ≡ fmap f . join

Az első két törvény a monadikus törvényeknek felel meg, a harmadik azt állítja, hogy a join természetes transzformáció "fmap . fmap"-tól az "fmap"-ba.

Additív monádok

Egy monád additív, ha van monadikus zérója, mzero, és egy mplus, ami megfelel a monoid axiómáknak, az mzeroval, mint nullelemmel. Az mplus operátor típusa M t → M t → M t, ahol M a monád konstruktora, t a behelyettesített típus. Emellett asszociatív, és az mzero jobb és bal oldali azonosság. Azaz:

(a `mplus` b) `mplus` c   ≡   a `mplus` (b `mplus` c)
m `mplus` mzero           ≡   m
mzero `mplus` m           ≡   m

Tehát egy additív monád monoid is. Másrészt ez azt jelenti, hogy mzero nullelem a >>= operációra. Mivel a nullával való szorzás eredménye mindig nulla, mzero és bármely függvény bind kapcsolata mzero, akármilyen sorrendben.

mzero >>= f               ≡   mzero

m >>= (\x -> mzero)       ≡   mzero

Intuitívan, az mzero egy olyan érték, aminek nincs megfelelője a hozzárendelt típusban, csak a monádhoz kapcsolódik. A Maybe monádban a Nothing zéró; a List monádban az üres lista, [] zéró.

Do-jelölés

Habár néha van annak értelme, hogy közvetlenül használjuk a bind operátort, a do jelölés sokkal gyakrabban fordul elő. Ezt az OCaml perform jelölésnek, F#-ban számítási kifejezésnek nevezik. Hasonlóan néz ki, mint az imperatív programnyelvek szekvenciája. Ez csak szintaktikus cukor, a fordító átalakítja, hogy >>= szerepeljen benne.

Például a biztonságos osztás definíciói ekvivalensek:

x // y = do
  a <- x  -- Extract the values "inside" x and y, if there are any.
  b <- y
  if b == 0 then Nothing else Just (a / b)

x // y = x >>= (\a -> y >>= (\b -> if b == 0 then Nothing else Just (a / b)))

Egy másik példa:

a = do x <- [3..4]
       [1..2]
       return (x, 42)

amit a fordító átalakít:

a = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))

Hasznos betekinteni a List monád megvalósításába, és tudni, hogy a concatMap a lista minden elemére meghívja a függvényt, és összefűzi az eredmény listákat:

instance Monad [] where
  m >>= f  = concat (map f m)
  return x = [x]
  fail s   = []

concatMap f = concat . map f

Tehát ezek a transzformációk mind ekvivalensek:

a = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))
a = [3..4] >>= (\x -> concatMap (\_ -> return (x, 42)) [1..2] )
a = [3..4] >>= (\x -> [(x,42),(x,42)] )
a = concatMap (\x -> [(x,42),(x,42)] ) [3..4]
a = [(3,42),(3,42),(4,42),(4,42)]

Jegyezzük meg, hogy az [1..2] lista elemeit nem használja a program! Balra mutató nyíl nélkül egy olyan kötéssé fordul le, ahol a függvény figyelmen kívül hagyja argumentumát, és csak a monád szerkezete fontos, nem az, ami benne van, például egy állapot monád, ami értékeket tárol anélkül, hogy visszaadna bármit is. A do-blokk jelölés használható minden monáddal; ez egy szintaktikus cukor a >>= számára.

Hasonló példa F#-ban számítási kifejezéssel:

let readNum () =
  let s = Console.ReadLine()
  let succ,v = Int32.TryParse(s)
  if (succ) then Some(v) else None

let secure_div =
  maybe {
    let! x = readNum()
    let! y = readNum()
    if (y = 0)
    then None
    else return (x / y)
  }

A maybe blokk szintaktikus cukra belsőleg a következő kifejezéssé alakul át:

maybe.Delay(fun () ->
  maybe.Bind(readNum(), fun x ->
    maybe.Bind(readNum(), fun y ->
      if (y=0) then None else maybe.Return(x / y))))

Generikus monadikus függvények

A biztonságos osztás által produkált értékeket további számításokhoz akarjuk felhasználni, anélkül, hogy ellenőriznünk kellene, Nothing monadikus értéket kaptunk-e. Ehhez egy felemelést végző függvényt használhatunk, ami minden monádhoz definiálható. Haskellben ez a liftM2 függvény:

liftM2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
liftM2 op mx my = do
    x <- mx
    y <- my
    return (op x y)

Emlékezzünk arra, hogy a nyilak jobbra zárójeleződnek, így a liftM2 paramétere egy bináris függvény, és bináris függvényt ad vissza. A típus szignatúrája azt jelzi, hogy: ha m monád, akkor bármely bináris függvényt felemelhetünk bele. Például:

(.*.) :: (Monad m, Num a) => m a -> m a -> m a
x .*. y = liftM2 (*) x y

definiál egy (.*.) operátort, ami összeszoroz két számot, ha nincs köztük Nothing, különben az eredmény Nothing. Ennek az az előnye, hogy nem kell a monád implementáció részleteit figyelembe venni. Ha ugyanazt egy másik függvénnyel vagy monáddal akarjuk megvalósítani, akkor a liftM2 jelzi, hogy itt mire is gondoltunk.

A liftM2 operátor matematikai definíciója:

${\text{liftM2}}\colon \forall M\colon {\text{monad}},\;(A_{1}\to A_{2}\to R)\to M\,A_{1}\to M\,A_{2}\to M\,R=$$op\mapsto m_{1}\mapsto m_{2}\mapsto {\text{bind}}\;m_{1}\;(a_{1}\mapsto {\text{bind}}\;m_{2}\;(a_{2}\mapsto {\text{return}}\;(op\,a_{1}\,a_{2})))$

További példák

Identitásmonád

A legegyszerűbb monád az identitásmonád, ami nem ad információt az értékekhez.

Id t = t
return x = x
x >>= f = f x

Egy do blokk ezzel a monádddal helyettesítést hajt végre; do {x <- 2; return (3*x)} 6-ot eredményez.

A kategóriaelmélet szempontjából az identitásmonád az identitásfunktorok adjunkciójából származik.

Gyűjtemények

Egyes ismert gyűjtemények, mint listák, halmazok, multihalmazok monádok. A listák monádjának definíciója:

-- "return" constructs a one-item list.
return x = [x]
-- "bind" concatenates the lists obtained by applying f to each item in list xs.
xs >>= f = concat (map f xs)
-- The zero object is an empty list.
mzero = []

A lista generátor-szűrő párok a List monád speciális alkalmazásai. Például a [ 2*x | x <- [1..n], isOkay x] kódrészlet a monádban így alakul: do {x <- [1..n]; if isOkay x then return (2*x) else mzero;} Ez a jelölés a matematikai halmazdefiníciós jelölésekre hasonlít.

Egy halmaz monáddal az a probléma, hogy csak olyan típusokra alkalmazható, amelyekre értelmezve van az egyenlőség. Egy monád azonban nem írhatja elő, hogy mikre példányosítható, éppen ezért a Set korlátozott monád. A gyűjteményes monádok felfoghatók nem determinisztikus számítások eredményeinek gyűjteményeként. Például ha x <- [1,2,3,4,5], akkor x nem determinisztikusan felveheti a lista bármely értékét. Ha visszaadjuk x-et, akkor a nem determinisztikus számítás összes eredményét is visszaadtuk. A bind operátor hasonló példát követ, amikor minden elemre elvégzi a számítást, és egy listába gyűjti őket.

Gyakran láthatók olyan utasítások is, mint if feltétel x y then return () else mzero; ha a feltétel teljesül, akkor nem determinisztikusan kiválasztódik egy olyan elem az eredmények közül, ami még nincs értékül adva; ha a feltétel hamis, akkor helyére az mzero = [] elem kerül, ami 0 elem közül választódik ki nem determinisztikusan. Más számítási utak még adhatnak eredményt. Ez őrként szolgál arra, hogy csak azok a számítások folytatódjanak, amelyek megfelelnek egy feltételnek. Emiatt a gyűjtemények használhatók nem determinisztikus számítások végzésére, mint logikai feladványok vagy szudoku megoldására.

Lusta kiértékelésű nyelvekben a lista csak addig lesz kiszámítva, ameddig szükség van rá. Például ha csak az első elemet kérdezik, akkor csak az első elemet kapjuk vissza. Ez a nemdeterminisztikus számításoknál azt jelenti, hogy a listában benne van az összes eredmény, és lekérdezik az első elemet, akkor csak az számítódik ki, a többi nem. Ez megfelel a visszalépéses keresésnek. Kiválasztódik egy számítási út, és ha az egy ponton sikertelen, akkor elindul egy másik számítás az utolsó sikeres ponttól, és így tovább. Ha a második elemet kérdezik, akkor kiszámít egy második elemet, és így tovább. Így a List monád lehetővé teszi a visszalépéses keresést lusta nyelvekben. Szintén lehetséges ez olyan nyelvekben, ahol van lehetőség lustán végezni a számításokat, de ekkor figyelni kell arra, hogy a listát és a számításokat is lustának jelöljük.

A kategóriaelmélet szempontjából a gyűjtemény monádok egy szabad funtor és egy neki adott funktor adjunkciójából származnak, ahol az átadott funktor a halmazok kategóriájából a monádok kategóriájába megy. Különböző típusú monoidokat véve különböző gyűjteményeket kapunk:

Gyűjtemény típusa	Monoid típusa
lista	monoid
véges multihalmaz	kommutatív monoid
véges halmaz	idempotens kommutatív monoid
véges permutáció	idempotens nem-kommutatív monoid

Környezet monád

Egy környezet monád (úgy is, mint olvasó monád vagy függvény monád) megengedi, hogy a számítás eredménye egy megosztott környezet által tartalmazott értékektől függjön. A monád típuskonstruktora egy T típust E → T típusú függvényekre képez, ahol E a megosztott környezet típusa. A monád függvények:

${\begin{array}{ll}{\text{return}}\colon &T\rightarrow E\rightarrow T=t\mapsto e\mapsto t\\{\text{bind}}\colon &(E\rightarrow T)\rightarrow (T\rightarrow E\rightarrow T')\rightarrow E\rightarrow T'=r\mapsto f\mapsto e\mapsto f\,(r\,e)\,e\end{array}}$

A következő monadikus operációk hasznosak:

${\begin{array}{ll}{\text{ask}}\colon &E\rightarrow E={\text{id}}_{E}\\{\text{local}}\colon &(E\rightarrow E)\rightarrow (E\rightarrow T)\rightarrow E\rightarrow T=f\mapsto c\mapsto e\mapsto c\,(f\,e)\end{array}}$

Az ask operáció kérdezi le az aktuális környezetet, a local pedig egy számítást egy módosított alkörnyezetben hajt végre. Ahogy az állapot monádban, a számítások indíthatók azzal, hogy megadunk egy környezet értéket és alkalmazzuk a monád egy példányára.

Állapot monád

Funkcionális nyelvekben többnyire nincsenek változók, helyüket konstansok és ismeretlenek töltik be. Néha azonban mégis szükség lenne rájuk, ezen az állapot monád segít. Az állapot monád lehetővé teszi, hogy bármely számításhoz állapot információt csatoljanak. Bármely adott értéktípusra az állapot monád megfelelő típusa egy függvény, ami állapotot fogad el, eredményez egy állapotot (alább s típus) és visszaad egy értéket (alább t típus). Ez hasonló a környezet monádhoz, de itt módosuló környezetről van szó.

type State s t = s -> (t, s)

Jegyezzük meg, hogy ez a monád az eddigiektől eltérően vár egy típus paramétert, ez az állapot információ típusa. A monád műveleteit a következőképpen definiálták:

-- "return" produces the given value without changing the state.
return x = \s -> (x, s)
-- "bind" modifies m so that it applies f to its result.
m >>= f = \r -> let (x, s) = m r in (f x) s

Hasznos állapot műveletek:

get = \s -> (s, s) -- Examine the state at this point in the computation.
put s = \_ -> ((), s) -- Replace the state.
modify f = \s -> ((), f s) -- Update the state

Még egy művelet alkalmazható az állapot monádra:

runState :: State s a -> s -> (a, s)
runState t s = t s

Az állapot monád do blokkjai műveletek sorozatai, amelyek vizsgálhatják, megváltoztathatják az állapot adatokat.

Informálisan, az állapot monád az S állapot típussal leképezi a T visszatérési típusokat $S\rightarrow T\times S$ típusú függvényekre képezi, ahol S a befoglalt állapot. A return és a bind függvények:

${\begin{array}{ll}{\text{return}}\colon &T\rightarrow S\rightarrow T\times S=t\mapsto s\mapsto (t,s)\\{\text{bind}}\colon &(S\rightarrow T\times S)\rightarrow (T\rightarrow S\rightarrow T'\times S)\rightarrow S\rightarrow T'\times S\ =m\mapsto k\mapsto s\mapsto (k\ t\ s')\quad {\text{where}}\;(t,s')=m\,s\end{array}}$.

Kategóriaelmélet szempontjából az állapot monád a szorzat funktor és az exponenciális funktor közötti adjunkcióból származik, ami definíció szerint minden zárt Descartes-féle kategóriában létezik.

Író monád

Az író monád lehetővé teszi, hogy a program különböző segéd kimeneteket, amelyek több lépésben gyűjthetők össze és komponálhatók a számítás mellett. Gyakran naplózásra vagy profilozásra használják. Adott T típus esetén az író monádban levő típus W × T, ahol W el van látva egy művelettel, ami követi a monoid törvényeket. Azaz W el van látva egy bináris művelettel, (a,b) → a*b, ami asszociatív, (a*b)*c = a*(b*c), és van egy ε neutrális eleme, amire x*ε = ε*x = x minden x értékre.

A monád függvényei egyszerűek:

${\text{return}}\colon T\rightarrow W\times T=t\mapsto (\epsilon ,t)$

${\text{bind}}\colon (W\times T)\rightarrow (T\rightarrow W\times T')\rightarrow W\times T'=(w,t)\mapsto f\mapsto (w*w',\,t')\quad {\text{where}}\;(w',t')=f\,t$

ahol ε és * rendre a W monoid identitáseleme és asszociatív művelete.

JavaScriptben az író példánya egy kételemes tömbként fejezhető ki, ahol az első elem tetszőleges érték, a második egy tömb, ami extra információt fogad magába.

const writer = [value, []];

Itt a zárójelek a monád típuskonstruktoraként működnek, egyszerű komponensekből létrehozva a Writer monád egy monadikus értékét. JavaScriptben a return szó fenntartott, úgyhogy a példa az unit szót használja:

const unit = value => [value, []];

A bind egy függvényt alkalmaz az író állapotra, és egy új író példányt ad vissza, ami tartalmazza az alkalmazás eredményét, és a kezdő és új akkumulátorok algebrai összegét.

const bind = (writer, transform) => {
    const [value, log] = writer;
    const [result, updates] = transform(value);
    return [result, log.concat(updates)];
};

A pipeline egy segédfüggvény, ami bindek sorozatát kapcsolja össze egy függvénytömb elemeivel.

const pipeline = (writer, ...transforms) =>
    transforms.reduce(bind, writer);

Példák függvényekre, amelyek a fenti író monád által elvárt tíypusú értékeket adnak vissza:

const squared = x => [x * x, [`${x} was squared.`]];

const halved = x => [x / 2, [`${x} was halved.`]];

Végül egy példa arra, hogy a monáddal csővezetéket építünk algebrai függvények számára, amelyek mellékesen debugolják is az információt, alkotnak egy tömböt, amiben debug információk szerepelnek:

pipeline(unit(4), squared, halved); // [8, ['4 was squared.', '16 was halved.']]

Folytatási monád

Egy $R$ visszatérési típusú folytatási monád a $T$ típust $\left(T\rightarrow R\right)\rightarrow R$ típusú függvényekre képezi. Folytatásátadási stílus modellezésére használják. A return és a bind függvények:

${\begin{array}{ll}{\text{return}}\colon &T\rightarrow \left(T\rightarrow R\right)\rightarrow R=t\mapsto f\mapsto f\,t\\{\text{bind}}\colon &\left(\left(T\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T\rightarrow \left(T'\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T'\rightarrow R\right)\rightarrow R=c\mapsto f\mapsto k\mapsto c\,\left(t\mapsto f\,t\,k\right)\end{array}}$

A folyamatban levő folytatás-függvényhívás függvény definíciója:

${\text{call/cc}}\colon \ \left(\left(T\rightarrow \left(T'\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T\rightarrow R\right)\rightarrow R\right)\rightarrow \left(T\rightarrow R\right)\rightarrow R=f\mapsto k\mapsto \left(f\left(t\mapsto x\mapsto k\,t\right)\,k\right)$

Egyéb monádok

További fogalmak, amiket kutatók monádként fejeztek ki:

• Iterátor
• Kivételkezelés
• Grafikus felhasználói felületek
• Folyamatok közötti kommunikáció
• Parserek
• Értelmezők
• Mohó kiértékelés
• Interfészek más nyelven írt kódokhoz

Szabad monádok

A szabad monádok a monoidokhoz hasonlóak. Intuitívan kifejezik azt, ami közös a monádokban (monoidokban), így generikus monádoknak (monoidoknak) tekinthetők.

Minden t típusra t szabad monoidja [t], ellátva a ++ asszociatív bináris művelettel és [] egységelemmel. Haskellben ezt írhatjuk úgy, mint:

instance Functor [] where
   fmap _ [] = []
   fmap fun (x:xs) = fun x : fmap fun xs

instance Monoid [t] where
   mappend xs ys = xs ++ ys
   mempty = []

Ahogy konkrét monoidokban, így itt is hozzá tudunk adni t1,t2,...,tn elemeket a monád bináris műveletével; []-ben egyszerűen összefűződnek, és az eredmény [t1,t2,...,tn], ami kifejezi, hogy összetartoznak. Az összetartozás mibenlétének nem ad jelentést a generikusság miatt.

A szabad monád ugyanezen alapul. Ha vesszük a List t = Nil | Cons t (List t) definíciót, és beszúrunk egy funktort, akkor a szabad monádot kapjuk:

data Free f a = Return a | Bind (f (Free f a))

instance Functor f => Functor (Free f) where
   fmap fun (Return x) = Return (fun x)
   fmap fun (Bind x) = Bind (fmap (fmap fun) x)

instance Functor f => Monad (Free f) where
   return x = Return x
   Return x >>= fun = fun x
   Bind x >>= fun = Bind (fmap (>>= fun) x)

Az értékek listáját tároló Listtel szemben a Free funktorokjat tárol, amelyek az eredeti értékeket burkolják. Eszerint a Free Functor és Monad példányai nem csinálnak mást, mint azt, hogy átadnak egy adott függvényt, amit az fmap konkrét listára alkalmaz.

Komonádok

A komonádok a monádok kategóriaelméleti duálisai. Egy komonád definiálható típuskonstroktorával, mint például W T, és két művelettel, az egyik W T → T kibontás (extract), a másik a kiterjesztés (extend) (W T → T' ) → W T → W T' . Ezekre a következőknek kell teljesülniük:

${\text{extend}}\,\,{\text{extract}}={\text{id}}$

${\text{extract}}\circ ({\text{extend}}\,f)=f$

$({\text{extend}}\,f)\circ ({\text{extend}}\,g)={\text{extend}}\,(f\circ ({\text{extend}}\,g))$

Alternatív definíciójuk az fmap, extract, illetve duplicate műveleteket használja. Az fmap és az extract műveletek W-t mint kopontozott funktort definiálják. A duplicate művelet jellemzi a komonádot: típusa W T → W (W T), és a következők teljesülnek rá:

${\text{extract}}\circ {\text{duplicate}}={\text{id}}$

${\text{fmap}}\,{\text{extract}}\circ {\text{duplicate}}={\text{id}}$

${\text{duplicate}}\circ {\text{duplicate}}={\text{fmap}}\,{\text{duplicate}}\circ {\text{duplicate}}$

A két definíció ekvivalens:

${\begin{array}{ll}{\text{fmap}}:&(A\rightarrow B)\rightarrow \mathrm {W} \,A\rightarrow \mathrm {W} \,B=f\mapsto {\text{extend}}\,(f\circ {\text{extract}})\\{\text{duplicate}}:&\mathrm {W} \,A\rightarrow \mathrm {W} \,\mathrm {W} \,A={\text{extend}}\,{\text{id}}\\{\text{extend}}:&(\mathrm {W} \,A\rightarrow B)\rightarrow \mathrm {W} \,A\rightarrow \mathrm {W} \,B=f\mapsto ({\text{fmap}}\,f)\circ {\text{duplicate}}\end{array}}$

A monádok mellékhatásokat, a komonádok környezeteket definiálnak. Az extract függvények kivesznek egy értéket a kontextusából, míg az extend függvénnyel csővezeték építhető W A → B típusú környezetfüggő függvényekből.

Identitás komonád

Az identitás komonád a legegyszerűbb komonád, a típust önmagára képezi. Az extract az identitás, és az extend a függvény alkalmazása.

Szorzat komonád

A szorzat komonád egy adott T típust a $C\times T$-ba képezi, ahol C a komonád kontextus típusa. A komonád műveletei:

${\begin{array}{ll}{\text{extract}}:&(C\times T)\rightarrow T=(c,t)\mapsto t\\{\text{extend}}:&((C\times A)\rightarrow B)\rightarrow C\times A\rightarrow C\times B=f\mapsto (c,a)\mapsto (c,f\,(c,a))\\{\text{fmap}}:&(A\rightarrow B)\rightarrow (C\times A)\rightarrow (C\times B)=f\mapsto (c,a)\mapsto (c,f\,a)\\{\text{duplicate}}:&(C\times A)\rightarrow (C\times (C\times A))=(c,a)\mapsto (c,(c,a))\end{array}}$

Függvény komonád

A függvény komonád az adott T típust az $M\rightarrow T$ típusú függvényekbe képezi, ahol M monadikus típus. A komonád műveletei:

${\begin{array}{ll}{\text{extract}}:&(M\rightarrow T)\rightarrow T=f\mapsto f\,\varepsilon \\{\text{extend}}:&((M\rightarrow A)\rightarrow B)\rightarrow (M\rightarrow A)\rightarrow M\rightarrow B=f\mapsto g\mapsto m\mapsto f\,(m'\mapsto g\,(m*m'))\\{\text{fmap}}:&(A\rightarrow B)\rightarrow (M\rightarrow A)\rightarrow M\rightarrow B=f\mapsto g\mapsto (f\circ g)\\{\text{duplicate}}:&(M\rightarrow A)\rightarrow M\rightarrow M\rightarrow A=f\mapsto m\mapsto m'\mapsto f\,(m*m')\end{array}}$

ahol ε az M identitáseleme és * az asszociatív művelete.

Koállapot komonád

A koállapot komonád egy adott T típust az $(S\rightarrow T)\times S$ típusba képezi, ahol S a tár alaptípusa. A komonád műveletei:

${\begin{array}{ll}{\text{extract}}:&((S\rightarrow T)\times S)\rightarrow T=(f,s)\mapsto f\,s\\{\text{extend}}:&(((S\rightarrow A)\times S)\rightarrow B)\rightarrow ((S\rightarrow A)\times S)\rightarrow (S\rightarrow B)\times S\,=f\mapsto (g,s)\mapsto ((s'\mapsto f\,(g,s')),s)\\{\text{fmap}}:&(A\rightarrow B)\rightarrow ((S\rightarrow A)\times S)\rightarrow (S\rightarrow B)\times S=f\mapsto (f',s)\mapsto (f\circ f',s)\\{\text{duplicate}}:&((S\rightarrow A)\times S)\rightarrow (S\rightarrow ((S\rightarrow A)\times S))\times S=(f,s)\mapsto ((s'\mapsto (f,s')),s)\end{array}}$

Források

A magyar Wikikönyvekben
további információk találhatók

Haskell témában.

A magyar Wikikönyvekben
további információk találhatók

Monád témában.

Haskell monád tutoriálok

• Monad Tutorials Timeline Probably the most comprehensive collection of links to monad tutorials, ordered by date.
• Piponi, Dan: You Could Have Invented Monads! (And Maybe You Already Have.). A Neighborhood of Infinity, 2006. augusztus 7. — The most famous "blog post" tutorial.
• Yorgey, Brent (2009. március 12.). „The Typeclassopedia”. The Monad.Reader (13), 17–68. o.  — An attempt to explain all of the leading typeclasses in Haskell in an elementary way, with monadic functors considered as only one form, best understood by comparison with others: e.g., the more general idea of a "Functor" as something you can map over; "Applicative" functors, and so forth; contains an extensive bibliography.
• Yorgey, Brent: Abstraction, intuition, and the "monad tutorial fallacy". blog :: Brent -> [String]. WordPress.com, 2009. január 12. — Opposes the idea of making a tutorial about monads in particular.
• What a Monad is not deals with common misconceptions and oversimplifications in a humorous way.
• beelsebob: How you should(n’t) use Monad. No Ordering. WordPress.com, 2009. március 31. — Takes a similar point of view, locating monads in a much wider array of Haskell functor classes, of use only in special circumstances.
• Vanier, Mike: Yet Another Monad Tutorial (part 1: basics). Mike's World-O-Programming. LiveJournal, 2010. július 25. — An extremely detailed set of tutorials, deriving monads from first principles.
• A Fistful of Monads An explanation of Monads, building on the concepts of Functors, Applicative Functors and Monoids discussed in the previous chapter.
• Functors, Applicatives and Monads in Pictures. A humorous beginner's guide to monads.

Régebbi tutoriálok

• All About Monads
• Haskell Wiki: Monads as Computation
• Haskell Wiki: Monads as Containers
• Norvell, Theodore: Monads for the Working Haskell Programmer. Memorial University of Newfoundland
• Klinger, Stefan (2005. december 15.). „The Haskell Programmer’s Guide to the IO Monad — Don’t Panic” (5–54), Kiadó: Centre for Telematics and Information Technology, University of Twente. [2015. március 24-i dátummal az eredetiből archiválva]. ISSN 1381-3625. (Hozzáférés: 2017. november 30.) 
• Turoff, Adam: Introduction to Haskell, Part 3: Monads. ONLamp. O'Reilly Media, 2007. augusztus 2. [2017. december 1-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. november 30.)
• Monads A monad tutorial providing examples of non-trivial monads apart from the conventional IO/Maybe/List/State monads.
• Söylemez, Ertugrul: Understanding Haskell Monads, 2010. július 11.

További dokumentáció

• van Tuyl, Henk-Jan: A tour of the Haskell monad functions, 2010. február 27.
• Moggi, Eugenio. „Notions of computation and monads”.  — The original paper suggesting use of monads for programming
• Wadler, Philip (2001. augusztus 1.). „Monads for functional programming”, Kiadó: University of Glasgow.  — Describes monads in Haskell (before they were implemented)

Scala monád tutoriálok

• League, Chris. Monadologie: Professional Help for Type Anxiety (flv) [Tech talk]. New York City: New York Scala Enthusiasts.
• Morris, Tony: Understanding Monads using Scala (Part 1). λ Tony’s blog λ, 2010. június 22. [2015. szeptember 18-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. november 30.)
• Monads are Elephants, 2007. szeptember 18.
• Pro Scala: Monadic Design Patterns for the Web pp. 300, 2010. április 25.

Monádok más nyelvekben

• Monads in Perl
• Monads in Ruby
• Monads in Python
• Monads in Scala, Scala for-comprehensions FAQ
• Monads in Clojure
• Monads in JavaScript
• Introduction to monads in C# and LINQ
• Library of monads for C#
• Monads in OCaml
• Monads in PHP

Fordítás

Ez a szócikk részben vagy egészben a Monad (functional programming) című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Külső link

• https://wiki.haskell.org/Monad