Mònada (programació funcional)

En programació funcional una mònada és un TAD sense tipus concrets, corresponent a una estructura algebraica d'un sol element (d'aquí el nom de mònada), on la finalitat de les operacions és modelar la composició i la seqüencialitat de les computacions (accions amb efectes) mitjançant l'encadenament, separant la composició temporal, de l'execució, així com incorporar el resultat de cada operació sobre l'entorn.

La mònada modela una computació i pot ser vista com una acció amb efecte (un canvi), que produeix un resultat.

Les mònades es poden compondre, mitjançant l'encadenament, amb operacions sobre el resultat de la precedent (que poden incloure efectes col·laterals), estalviant, respecte de la programació imperativa, les variables locals emprades per aquesta per desar resultats.

• (return v) representa una computació elemental que ofereix v com a resultat. return és el generador de la mònada.
• (>>=), anomenada bind, és la composició de computacions, encadenant una acció amb la següent en forma de funció sobre el resultat de la precedent.

En notació Haskell:

-- generador d'una computació simple, que retorna una expressió de tipus `a` com a resultat
return :: a -> efecte a

-- composició de computacions per encadenament amb el resultat
(>>=) :: efecte a -> (a -> efecte b) -> efecte b -- compon amb una altra, com a funció del resultat de la precedent

.

-- tipus de l'acció
acció :: efecte tipusDelResultat

-- exemple d'ús amb els operadors canònics:
acció = return 5 -- acció simple que ofereix el valor com a resultat

acció = acció1 >>= funcAcció2 -- retorna el resultat de la darrera acció-funció
 -- que s'aplica al resultat de la primera 

-- exemple amb niuament progressiu per retornar una expressió de resultats precedents
acció = acció1 >>= \resultat1 -> (acció2 >>= \resultat2 -> return expressió_de_resultats_precedents)

-- el mateix amb notació monàdica (sintaxi especial) denotant la precedència temporal
acció = do
 resultat1 <- acció1 -- sintaxi: resultat "<-" acció_d'efectes
 resultat2 <- acció2
 ...
 let resultatNou = expressió_de_resultats_precedents
 return resultatNou -- acció simple que retorna el valor

La mònada (signatura) s'implementa per a un tipus (estructura) que pot ser vist com un contenidor d'un sol element que pot ser el resultat, però no sempre és el resultat tot sol. #La mònada Writer aparella com a valor el resultat i un element combinable (un Monoide). #La mònada Reader conté com a valor una funció de tipus (entorn -> resultat). #La mònada State conté com a valor una altra tipus de funció (estat -> (resultat, nouEstat)).

Té aplicació en llenguatges de programació no-estrictes, on l'ordre de les operacions és indeterminat, principalment al Haskell i també en altres àmbits, en entorns on l'ordre de les operacions no està garantit, com ara encadenament de transaccions en memòria (mònada STM a Haskell i a OCaml), encadenament d'operacions asíncrones (mònada Par a Haskell, Asynchronous Workflows a F#), etc.

Això facilita als lleng. funcionals complementar la part funcional pura, amb efectes com ara operacions d'entrada/sortida, ops. sobre l'entorn exterior, canvis d'estat, i també el preprocés i optimització de les operacions abans de la seva execució.

Les lleis de la mònada.

return x >>= f	≡	f x	-- identitat per l'esquerra
m >>= return	≡	m	-- identitat per la dreta
m >>= (\x -> f x >>= g)	≡	(m >>= f) >>= g	-- associativitat

• Al llenguatge Haskell la classe de tipus Monad descriu la signatura de les operacions descrites, a banda d'altres mètodes amb motius pràctics:

 class Monad efecte where
 -- generador
 return :: a -> efecte a -- generador d'una "computació" a partir
 -- d'un valor de tipus ''a'' interpretable com a resultat

 {- encadenament (ang.: ''bind'') 
 encadena un efecte amb una funció efecte sobre el seu resultat -}
 (>>=) :: efecte a -> (a -> efecte b) -> efecte b 

 -- exemple: getline >>= putStrLn -- imprimeix la línia introduïda (resultat de l'efecte precedent)

 {- la classe Monad també incorpora els següents mètodes, per qüestions pràctiques
 però que no fan falta per la descripció teòrica: -}

 {-| (>>) modela un encadenament que ignora el resultat de la computació precedent. -}
 (>>) :: efecte a -> efecte b -> efecte b 
 m_x >> m_y = m_x >>= (\_ -> m_y) -- implementació per defecte 

 -- el mètode `fail` per disparar error cas de fallar l'encaix a la variable del resultat
 -- A partir de GHC 8.8 desapareix de Monad i obliga que els encaixos siguin irrefutables
 -- Per a l'ús de patrons refutables als encaixos caldrà que la mònada implementi MonadFail
 fail :: String -> IO a 
 fail missatge

La funció `fail` s'utilitza en la sintaxi específica de blocs d'encadenaments monàdics, els blocs do, per disparar una excepció en cas que falli l'encaix del patró del paràmetre de la funció d'efectes, però serà expulsada de la classe Mònada a GHC 8.8, cap a una classe específica MonadFail de Control.Monad.Fail. L'ús de patrons en l'encadenament requerirà que la mònada implementi MonadFail evitant les petades per l'ús de patrons en mònades que no els suporten. Fase final de la proposta implementada a GHC 8.8.

En Haskell podem expressar (>>=), en termes de fmap i join, doncs la classe Monad actualment deriva de la classe Applicative que deriva al seu torn de Functor. El nom "flatMap" que (>>=) pren en altres llenguatges (Scala, Java8) ve de l'ús d'aquests conceptes:

-- ''join'' aplana el tipus.
join :: Monad efecte => efecte (efecte a) -> efecte a

-- Si l'efecte implementa l'estructura Functor
fmap :: Functor efecte => (a -> b) -> efecte a -> efecte b

-- (>>=) :: efecte a -> (a -> efecte b) -> efecte b
 m_a >>= f = (join. fmap f) m_a -- d'aquí el nom de flatMap en altres llenguatges

• Al llenguatge OCaml: Mònada per a les computacions IO no blocants.

(* De la biblioteca Light Weight Threads.
 A l'OCaml els tipus s'apliquen en sentit invers (de dreta a esq.) *)

module LWT = sig
 type +'a t (* The type of threads returning a result of type 'a. *)
 val return : 'a -> 'a t
 val (>>=) : 'a t -> ('a -> 'b t) -> 'b t 
 val fail : exn -> 'a t
 ...
end ;;

• A Scala la mònada és el substrat de les llistes per comprensió: Vegeu #Mònades a Scala més avall.

trait FilterMonadic[+A, +Repr] extends Any {
 // flatMap: encadenament (equivalent del Haskell (>>=))
 abstract def flatMap[B, That](f: (A) ⇒ GenTraversableOnce[B])(implicit bf: CanBuildFrom[Repr, B, That]): That

 // la transformació final en una llista per comprensió requereix que implementi Functor
 // l'aplicació del mètode (map f) converteix la coŀleció Repr en una del tipus de sortida That
 abstract def map[B, That](f: (A) ⇒ B)(implicit bf: CanBuildFrom[Repr, B, That]): That

 abstract def withFilter(p: (A) ⇒ Boolean): FilterMonadic[A, Repr]
 abstract def foreach[U](f: (A) ⇒ U): Unit
}

• A Java8 la classe d'objectes Optional implementa operacions similars a les de Scala:

Class Optional<T>
 public static <T> Optional<T> of(T value) // equivalent del Haskell (return)
 public <U> Optional<U> flatMap(Function<? super T, Optional<U>> mapper) // equivalent del Haskell (>>=)
 public <U> Optional<U> map(Function<? super T, ? extends U> mapper) // equivalent del Haskell (fmap)
 Optional<T> filter(Predicate<? super T> predicate)
 ...

Mònades segons la quantificació de resultats

Seqüenciació d'accions amb

• resultat únic:
  • IO: entrada/sortida, excepcions I/O i canvis d'estat de variables globals IORef.
  • ST: encapsulament de canvis d'estat en un àmbit local (variables STRef).
• resultat opcional (de funcions o bé d'accions que poden fallar):
  • la mònada Maybe: èxit o fallada de funcions definides parcialment.
  • la mònada (Either tipusError): èxit o fallada de la validació amb try d'accions que poden llançar excepcions.
• resultat múltiple: la mònada llista (mecanisme de les llistes per comprensió).

Mònades i estrictesa

Les mònades no impliquen estrictesa (avaluació del primer argument de (>>=) malgrat que el segon no en demani el resultat com a paràmetre: cas del comodí '_') sinó que depèn de la implementació. La mònada IO és d'avaluació estricta, la mònada llista [a] no, i per exemple la mònada State té versions estricta i d'avaluació tardana (lazy)

Mònades amb efecte fallada

Afegint la llei de l'element absorbent per l'esquerra

mzero >>= f ≡ mzero

L'element absorbent per l'esquerra fa inútil l'avaluació de les computacions subseqüents, ja que el resultat és el mateix valor, i pot indicar una situació d'error que invalidi la continuació de les computacions.

L'encadenament de computacions amb mònades que compleixin la regla de l'element absorbent en (>>=) per algun valor del tipus, evita haver de comprovar resultats d'error a cada pas nou en la seqüència.

La mònada Maybe (computacions que poden fallar)

Nothing n'és l'element absorbent per l'esquerra. Optimitza la seqüència evitant l'execució de computacions subseqüents a la que falla.

-- de la definició

data Maybe a = Nothing | Just a

instance Monad Maybe where
 return x = Just x
 fail _ = Nothing

 Nothing >>= _ = Nothing -- element absorbent; no avalua la computació subseqüent 

 (Just x) >>= f = f x -- f :: a -> Maybe b

Exemple:

headMaybe :: [a] → Maybe a
headMaybe (x : _) = return x -- resultat exitós, equival a (Just x)
headMaybe [] = Nothing -- element absorbent de la mònada Maybe

doblar :: Num a => a → Maybe a
doblar x = return $ 2 * x

doblarElCap :: Num a => [a] → Maybe a
doblarElCap llista = headMaybe llista >>= doblar

-- equivalent amb notació de blocs ''do''
doblarElCap llista = do
 x <- headMaybe llista
 doblar x -- cas de llista buida, ''doblar'' no s'avalua

-- doblarElCap [] == Nothing
-- doblarElCap [1,2,3] == Just 2

La mònada Either (resultats duals)

Amplia el valor Nothing de la mònada Maybe amb un segon conjunt de valors, emprat sovint per designar els errors en computacions que poden fallar disparant excepcions.

Els constructors Left i Right, a més de l'accepció d'Esquerre i Dreta, també tenen el significat de Tort i Dret, explicitant així la correcció del resultat.

Tots els elements amb constructor Left (Left l) són elements absorbents per l'esquerra.

data Either a b = Left a | Right b

instance Monad (Either e) where
 return x = Right x

 Left l >>= _ = Left l -- element absorbent, l'encadenament no s'avalua

 Right r >>= f = f r

Exemple:

-- `try` de Control.Exception avalúa una acció que pot disparar excepcions retornant l'excepció o el resultat
try :: Exception e => IO a -> IO (Either e a)

-- `evaluate` de Control.Exception avalúa una expressió funcional per fer-ne aflorar les excepcions
evaluate :: a -> IO a -- força l'avaluació (a WHNF)

-- exemple:
import Data.Fixed (Centi) -- coma fixa centessimal per a valors monetaris
provaDivisió :: Centi -> Centi -> Either ArithException Centi
provaDivisió x y = try (evaluate (x/y))

Composició monàdica

Composició de Kleisli.

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)

La mònada IO

Haskell modela l'entrada/sortida com una seqüència encadenada d'operacions (per forçar-ne la serialització degut a l'avaluació no-estricta), encapsulant els canvis d'estat d'accés a fitxers. Aquest model encaixa amb el concepte de mònada, donant lloc a la mònada IO.

La funció inicial main de qualsevol programa en Haskell ha de ser una expressió d'operacions d'ent./sortida i per tant del tipus de la mònada IO.

 -- expressions de la ''mònada'' IO (el tipus porta com a paràmetre el tipus del resultat de les operacions)
 getLine -- captura una línia introduïda -- tipus ''IO String''
 getLine >>= putStr -- imprimeix la línia introduïda -- tipus ''IO ()''
 putStr "polseu Intro" >> hFlush stdout >> getLine >> putStrLn "Fet" >> return True -- tipus ''IO Bool''

 (>>=) -- encadena aplicant la funció següent al resultat de la computació precedent
 (>>) -- encadena ignorant el resultat de la computació precedent.

 return x -- op. generadora de la computació mònada amb x com a resultat
 -- quedant, per ex., del tipus IO X si la mònada és IO
 -- no pressuposa ''retorn'' d'enlloc; per ex. (return 5) :: IO Int

 fail missatge -- per al cas que el paràmetre de la funció d'efectes no sigui irrefutable i falli l'encaix
 -- fail s = IO.failIO s

 -- a partir de GHC 8.0 la funció 'fail' es trasllada a una classe diferent: la MonadFail

Vegeu el tipus de (failIO s)

$ ghci
Prelude> fail "pífia"
*** Exception: user error (pífia)
Prelude> :t fail "pífia"
fail "pífia" :: Monad m => m a

Blocs do: notació especial de les expressions monàdiques

La clàusula do exposa l'encadenament de manera seqüencial, amb una expressió monàdica per línia, introduint l'estil imperatiu.

bloc = do 
 x <- getLine -- resultat "<-" efecte
 putStrLn x
 putStrLn "Fet"
 return x

-- equival a l'expressió següent, encadenant cada línia amb (>>=) o bé (>>) 

-- * les corresponents al patró (resultat "<-" efecte (";"|"\n") resta_del_bloc)
-- es tradueixen per (efecte >>= \ resultat -> resta_del_bloc)

bloc = getLine >>= \ x -> (-- la resta_del_bloc té accés a l'argument de la lambda 
 putStrLn x >>
 putStrLn "Fet" >>
 return x
)

-- actualment s'incorpora una opció per al cas de fallada de l'encaix, 
-- cridant al mètode 'fail' de la classe Monad, que 
-- des de GHC 8.x passa a la classe MonadFail
-- de manera que caldrà que l'acció implementi MonadFail (de Control.Monad.Fail) 
-- per a emprar patrons no irrefutables

bloc = let segonaAcció patróDelResultatPrecedent = resta_del_bloc 
 segonaAcció _ = fail "encaix fallit a la posició tal" -- generat sempre a GHC <= 8.0
 in primeraAcció >>= segonaAcció

el bloc do és un artifici sintàctic que es tradueix a una única expressió, relligant les línies amb operacions de mònada com el que segueix:

• les del tipus x <- expr_monàdica es concatenen amb les següents per encadenament (>>=) amb funció anònima de param. x i la continuació com a cos.
• les altres es concatenen amb encadenament (>>) sense passar resultats

Clàusula let dins el bloc do

let a nivell de do (NO és el mateix que let..in) permet establir definicions basant-se en resultats d'efectes precedents, cosa que no és possible amb clàusules where.

"let" var1 "=" expr1 {";" var2 "=" expr2}

obté el valor de les expressions. let introdueix un subbloc, que es podrà delimitar o bé pel sagnat, o bé amb claus {} i separadors ';', i quines variables definides queden visibles a la resta del bloc do.

main = do
 print "Entreu un mot: "
 x <- getLine
 print "Entreu-ne un altre: "
 y <- getLine

 -- subbloc ''let'' de definicions basades en resultats d'efectes precedents
 let { z = x ++ y; w = z ++ "." }

 -- equivalent amb sagnat
 let z = x ++ y 
 w = z ++ "." -- cal alinear el bloc a la variable definida 

 putStrLn ("La concatenació és: " ++ show w)

Control imperatiu

Operacions comparables al control dels llenguatges imperatius.

El mòdul Control.Monad de Haskell aporta entre d'altres les següents funcions:

-- sequence: encadena una llista d'operacions monàdiques

sequence :: Monad m => [m a] -> m [a] -- oferint la llista de resultats

sequence_ :: Monad m => [m a] -> m () -- igual descartant resultats

-- forever: encadena una acció monàdica amb ella mateixa de manera indefinida (bucle infinit)
-- finalitzant només en cas d'excepció

forever :: Monad m => m a -> m b 

-- replicateM: encadena una acció monàdica amb ella mateixa, un nombre finit de vegades.

replicateM :: Monad m => Int -> m a -> m [a] -- oferint la lista de resultats

replicateM_ :: Monad m => Int -> m a -> m () -- descartant resultats

-- iteracions amb efectes col·laterals:
-- forM i mapM: encadena les aplicacions d'una "funció d'efectes col·laterals (tipus mònada en el retorn)" 
-- a cadascun dels elements d'una llista, preservant l'ordre

forM :: Monad m => [a] -> (a -> m b) -> m [b] -- oferint la llista de resultats

forM_ :: Monad m => [a] -> (a -> m b) -> m () -- descartant resultats

-- mapM === forM amb els paràmetres canviats (oferint llista de resultats)
-- mapM_ === forM_ amb els paràmetres canviats (descartant resultats)

-- mapM i també ''sequence'', tenen una versió genèrica en el tipus de la col·lecció, 
-- definides a la classe Traversable de Data.Traversable

 -- exemple: encadena la impressió dels elements d'una llista per oferir-los ordenadament.

 forM_ [1..10] $ \x -> print x 

 mapM_ (\x -> print x) [1..10] -- equivalent de l'anterior (estil funcional)

 -- amb llista que conté generador i filtre:

 forM_ [i^3 | i <-[1..10], i `mod` 2 == 0] $ \x -> print x 

 -- amb un bloc ''do'' (estil imperatiu)

 forM_ [i^3 | i <-[1..10], i `mod` 2 == 0] $ \x -> do
 putStr "següent valor: "
 print x 

-- exec. condicional 
when :: Monad m => Bool -> m () -> m ()

-- exec. condicional negada
unless :: Monad m => Bool -> m () -> m ()

if-then-else dins la clàusula do

-- segons el Haskell 98

if e1 then e2 else e3 === case e1 of { True -> e2; False -> e3 } 

-- segons el Haskell 2010 varia la sintaxi com a

if exp1 [;] then exp2 [;] else exp3 -- separable en línies pels ';'

acceptant el següent format:

f_exemple :: Monad m => Bool -> m Int
f_exemple cond = do
 if cond 
 then return 1
 else return 2

Subblocs do

Per posar més d'una instrucció en una branca d'un if o d'un case cal fer-ho en un subbloc do.

{-# LANGUAGE ScopedTypeVariables #-}
import Control.Monad as Monad
import Control.Exception

main = do
 print "Farem l'eco fins que l'entrada sigui buida."
 catch(
 Monad.forever $ do -- bucle infinit, cal una excepció per trencar-lo
 x <- getLine
 case x of -- alternativa 
 [] -> ioError (userError "Línia buida") -- llança excepció per sortir del "forever"
 _ -> do -- subbloc do per encabir més d'una instrucció a la branca
 putStrLn x
 putStrLn "tornem-hi" 
)
 (\(excep :: SomeException) -> print excep
)

Recursivitat en els blocs do

Parlem de Recursivitat mútua en definicions i accions amb efectes.

Als subblocs let de definicions amb encaix

Els blocs let permeten, per l'avaluació tardana, la recursivitat mútua de les variables definides.

(anglès) >> In Haskell let is really let_rec

f :: Int -> [Int] -> [Int]
f r llista = llista ++ [r] -- per exemple, afegeix al final

let_és_let_rec = do
 let llista @ (x:xs) = f r [1..9] -- utilitza el valor ''r'' de la definició que segueix
 r = x * 2 -- utilitza la ''x'' de l'encaix de la definició precedent
 return (r, llista)

main = do
 (r, ll) <- let_és_let_rec
 putStrLn $ "resultat: " ++ show r ++ "; llista: " ++ show ll

dona:

resultat: 2; llista: [1,2,3,4,5,6,7,8,9,2]

Als subblocs rec d'efectes amb recursivitat mútua

A GHC, permeten recursivitat mútua a les accions (efectes col·laterals). Cal esmentar la pragma {-# LANGUAGE RecursiveDo #-} Vegeu ref.

{-# LANGUAGE RecursiveDo #-}
import Data.IORef

-- crea nodes amb referències mútues

data Node = Node Int (IORef Node)

mk2nodes = do
 rec refS <- newIORef (Node 0 refR)
 refR <- newIORef (Node 1 refS)
 return refS

main = do
 refP <- mk2nodes
 putStrLn "nodes creats"
 Node x refQ <- readIORef refP -- obté els components del contingut de la ref.
 print x
 Node y _ <- readIORef refQ
 print y

Seqüències de computacions sense lligar resultats - Functors aplicatius

De vegades interessa només obtenir la llista de resultats d'una seqüència de computacions amb efectes col·laterals però sense encadenar resultats.

L'operació sequence esmentada prèviament fa aquesta funció.

sequence :: [IO a] -> IO [a]
sequence [] = return []
sequence (c : cs) = do
 x <- c -- primera computació
 xs <- sequence cs -- crida recursiva per a les següents computacions
 return $ (x :) xs -- aplicació parcial que afegeix x al capdavant dels resultats amb (:)

Aquest patró correspon a un combinador de la biblioteca Control.Monad que es diu ap (de aplicatiu)

ap :: Monad m => m (a -> b) -> m a -> m b
ap m_f m_x = do
 f <- m_f -- computació de resultat funció
 x <- m_x -- computació posterior
 return (f x) -- combina el resultat de la segona amb la funció resultat de la primera

Elevant una funció a efecte, la podrem utilitzar com a combinador:

computació :: Monad m => m r
computació = ap (return f) m_x -- per a f :: a -> r

Una funció de n paràmetres ens permet combinar els resultats de n efectes

comp2 :: Monad m => m r
comp2 = (return f2) `ap` m_x `ap` m_y -- per a f2 :: a -> b -> r

compN :: Monad m => m r
compN = (return fn) `ap` m_x `ap` m_y `ap` ... `ap` m_N -- per a fn :: a1 -> a2 -> ... -> aN -> r

Llavors la funció sequence es pot escriure

sequence :: [IO a] -> IO [a]
sequence [] = return []
sequence (c : cs) = (return (:)) `ap` c `ap` (sequence cs)

Generalitzant la manera de combinar una seqüència de computacions, en una mònada, sense encadenar resultats:

import Control.Monad
-- definits liftM, liftM2, .. liftM5 a Control.Monad com segueix

liftM :: (Monad m) => (a -> b) -> m a -> m b
liftM f x1 = (return f) `ap` x1 -- per a ''f'' d'un sol argument

liftM2 f2 x1 x2 = (return f2) `ap` x1 `ap` x2 -- on f2 :: a1 -> a2 -> b

liftMn fn x1 ... xn = (return fn) `ap` x1 `ap` ... `ap` xn -- on fn :: a1 -> ... -> an -> b

Això dona lloc a l'abstracció Applicative més simple que la Mònada però que està en els fonaments dels llenguatges funcionals.

La classe Applicative

Expressa la combinació de computacions (amb efectes col·laterals) sense l'encadenament del resultat que permet la mònada. Signatura.

class Functor efecte => Applicative efecte where
 -- genera una dada efecte a partir d'un valor interpretable com a resultat
 pure :: a -> efecte a

 -- combina resultats avaluant les computacions seqüencialment
 -- la primera computació retorna una funció que és aplicada al resultat de la segona
 -- vegeu més amunt la definició de ''ap''
 (<*>) :: efecte (a -> b) -> efecte a -> efecte b

 -- encadena seqüencialment dos efectes, oferint com a resultat el del segon
 (*>) :: efecte a -> efecte b -> efecte b

 -- encadena seqüencialment dos efectes, oferint com a resultat el del primer
 (<*) :: efecte a -> efecte b -> efecte a

La classe Functor:

class Functor contenidor where
 fmap :: (a -> b) -> contenidor a -> contenidor b

-- les instàncies de ''functor'' han de complir
-- fmap id == id
-- fmap (f. g) == fmap f. fmap g

Per aplicar una funció de n arguments als resultats de n computacions en seqüència definides Applicative tenim les funcions liftAn:

import Control.Applicative
-- definits liftA, liftA2, i liftA3 a Control.Applicative

(<$>) = fmap -- definició per a l'ús com operador en pos. ''infix'' (entremig)

liftA :: (Applicative m) => (a -> b) -> m a -> m b
liftA f x1 = fmap f x1 -- f té un sol argument
 = f <$> x1 -- equivalent

liftA2 f2 x1 x2 = f2 <$> x1 <*> x2 -- f2 :: a1 -> a2 -> b

liftAn fn x1 ... xn = fn <$> x1 <*> x2 <*> ... <*> xn -- fn :: a1 -> ... -> an -> b

A la mònada tenim les següents equivalències

 pure = return
 (<*>) = ap 
 (*>) = (>>)
 f_a <* f_b = do
 x <- f_a
 f_b
 return x

però GHC defineix la instanciació a partir d'un tipus derivat (amb newtype) de nom WrappedMonad. per establir la relació entre els tipus.

newtype WrappedMonad m a = WrapMonad { unwrapMonad :: m a }

instance Monad m => Applicative (WrappedMonad m) where
 pure = WrapMonad. return
 WrapMonad f <*> WrapMonad v = WrapMonad (f `ap` v)

Un exemple d'ús el trobem en els formularis web en haskell anomenats Formlets.

Aquí una versió de collita pròpia, com a producte de parells (entrada, resultat) per mostrar entrades i errors a validar per l'usuari:

type TEntrada = String
data TError = ErrValorInvàlid | ErrLlargExcessiva | ...
-- camps amb (entrada, resultat)
data TFormPersona = FormPersona {campNom :: (TEntrada, Either TError String)
, campEdat :: (TEntrada, Either TError Int)
, campAdrElec :: (TEntrada, Either TError TAdrElec)}

llegirFormulariPersona :: Applicative f => f TFormPersona
llegirFormulariPersona = 
 FormPersona <$> llegeixCampNom <*> llegeixCampEdat <*> llegeixCampAdreçaElec

-- o també
llegirFormulariPersona = 
 liftA3 FormPersona llegeixCampNom llegeixCampEdat llegeixCampAdreçaElec

-- on els tipus
llegeixCampNom :: Applicative f => f (TEntrada, Either TError String)
llegeixCampEdat :: Applicative f => f (TEntrada, Either TError Int)
llegeixCampAdreçaElec :: Applicative f => f (TEntrada, Either TError TAdrElec)

La classe Alternative (computacions alternatives)

Defineix un monoide sobre els functors aplicatius.

class Applicative efecte => Alternative efecte where
 -- | L'element neutre de '<|>'
 empty :: efecte a

 -- | Una operació binària associativa
 (<|>) :: efecte a -> efecte a -> efecte a

 ...

instance Alternative Maybe where
 empty = Nothing

 Nothing <|> p = p
 Just x <|> _ = Just x

La interpretació de l'op. binària (<|>) no és sempre la intuïtiva. Està previst que Applicative esdevingui superclasse de Monad a GHC 7.10. De cara a una eliminació de duplicitats entre Mònada i Applicative es pretén que la relació d'Alternative amb Applicative sigui similar a la de MonadPlus amb Monad i que la implementació dels monoides d'Alternative i de MonadPlus donin el mateix resultat per als tipus que implementin ambdues classes. És el cas de les llistes.

• De la proposta Functor-Applicative-Monad:

import Control.Applicative (Alternative(..))
import Control.Monad (mzero, mplus)

-- MonadPlus m

instance Alternative m where
 (<|>) = mplus
 empty = mzero

La classe MonadPlus (computacions amb solucions múltiples)

Defineix un Monoide sobre les computacions mònada. Permet expressar computacions amb solucions múltiples (zero o més) i l'opció de fallada (no avaluació de les computacions posteriors) i obtenir-ne la combinació de solucions.

class Monad m => MonadPlus m where
 mzero :: m a -- element absorbent (fallada de la mònada)
 mplus :: m a -> m a -> m a -- combina solucions

-- "mzero" ha de satisfer:
 mzero >>= f = mzero
 m_x >> mzero = mzero

exemple: la mònada Llista

-- de la definició a Control.Monad.Instances
instance Monad [] where
 return x = [x]
 fail _ = []

 -- encadenant amb una funció (f :: a -> [b]), aplana la llista de llistes resultant concatenant amb (++)
 xs >>= f = foldr ((++). f) [] xs 

 -- encadenant amb una llista ys, mapeja amb (const ys), concatenant ys (length xs) vegades
 xs >> ys = foldr ((++). (\ _ -> ys)) [] xs

instance MonadPlus [] where
 mzero = []
 mplus = (++)

Exemple d'ús:

-- computació de solucions a l'equació de segon grau sobre tres fonts d'entrada
import Control.Monad

arrels :: (Floating t, Ord t) => [] t -> [] t -> [] t -> [] t
arrels m_a m_b m_c = do
 a <- m_a
 b <- m_b
 c <- m_c
 if (a == 0) -- evita div-per-zero
 then mzero -- retorna [] (fail de la mònada llista)
 else do
 let discriminant = b * b - 4 * a * c
 denom = 2 * a
 sol_única = (-b) / denom
 biaix = sqrt discriminant / denom

 case () of -- http://www.haskell.org/haskellwiki/Case#Using_syntactic_sugar

 _ | discriminant < 0 -> mzero
 | discriminant == 0 -> return sol_única
 | otherwise -> return (sol_única + biaix) `mplus` return (sol_única - biaix)

main = do
 putStrLn $ "discriminant negatiu: " ++ show (arrels [1] [1] [1] :: [Float])
 putStrLn $ "discriminant zero: " ++ show (arrels [1] [2] [1] :: [Float])
 putStrLn $ "discriminant positiu: " ++ show (arrels [1] [4] [1] :: [Float])
 putStrLn $ "conjunt solucions: " ++ show (arrels [0, 1] [1, 2, 4] [1] :: [Float]) -- inclou 0 en posició a

dona

discriminant negatiu: []
discriminant zero: [-1.0]
discriminant positiu: [-0.26794922,-3.732051]
conjunt solucions: [-1.0,-0.26794922,-3.732051]

Llista per comprensió monàdica

Generalitzen la notació de Llistes per comprensió. L'ús de filtres requereix que la mònada implementi la classe MonadPlus

Vegeu ref.

{-# LANGUAGE PackageImports #-}
import Control.Monad (guard)
import "HUnit" Test.HUnit -- del paquet HUnit -- cabal install HUnit

llista_esperada = [ (x, y) | x <- [1..10], y <- [1..x], x+y < 10]

-- traducció monàdica

llista_actual :: (Num a, Ord a, Enum a) => [] (a, a)
llista_actual = do
 x <- [1..10]
 y <- [1..x]
 guard (x+y < 10)
 return (x, y)

-- de la definició de ''guard'' :: MonadPlus m => Bool -> m ()

-- guard False = mzero -- element absorbent, invalida l'encadenament posterior
-- guard True = return () -- no fa res, permet continuar

prova = TestCase $ assertEqual "comprensió monàdica: " llista_esperada llista_actual

main = do
 comptaTests <- runTestTT prova
 print comptaTests

Ús de la construcció llista per comprensió amb qualsevol instància de MonadPlus

L'extensió MonadComprehensions permet emprar qualsevol mònada que sigui instància de MonadPlus, en la construcció llista per comprensió. Cal GHC >= 7.2.1

En el següent cas ja no és una llista per comprensió sinó una Maybe per comprensió

{-# LANGUAGE MonadComprehensions #-}

val_mònada :: (Num a) => Maybe a
val_mònada = [ x + y | x <- Just 1, y <- Just 2 ]

main = print val_mònada

dona

Just 3

Transformadors de mònades

Aplicació sobre el tipus d'una mònada que en combina l'operativa (permet l'ús dels mètodes de diverses mònades en una), encapsulant una mònada dins la mònada transformada resultant. Vegeu

Implementen la classe MonadTrans

class MonadTrans t where
 -- 'lift' eleva un efecte del tipus de la "mònada m" al tipus de la "mònada transformada (t m)"
 -- el tipus resultant té un nivell més que el d'origen.
 lift :: (Monad m) => m a -> t m a

Les transformacions són apilables: se'n poden aplicar diverses. Si t i t' són transformadors de mònades, llavors el tipus (t' t m a) constitueix la mònada (t' t m) transformada de la (t m)

La classe MonadIO és per definir una versió optimitzada de lift de MonadTrans per elevar el tipus dels efectes des de la mònada IO quan hi ha transformacions interposades.

class Monad m => MonadIO m where
 liftIO :: IO a -> m a -- eleva el tipus d'un efecte des de la mònada IO

Implementació del transformador MaybeT

El transformador MaybeT permetrà ampliar una mònada qualsevol amb la característica afegida de la mònada Maybe, d'evitar l'execució dels efectes posteriors a una fallada (op. fail).

-- el constructor MaybeT (a la dreta de la def.) incorporarà 
-- un sol component de tipus ''m (Maybe a)'' amb accessor ''runMaybeT''

newtype MaybeT m a = MaybeT {runMaybeT :: m (Maybe a)} 

 -- MaybeT :: m (Maybe a) -> MaybeT m a -- constructor
 -- runMaybeT :: MaybeT m a -> m (Maybe a) -- inversa del constructor 

instance (Monad m) => Monad (MaybeT m) where

 return x = MaybeT $ return $ Just x -- genera valor mònada exitosa
 fail _ = MaybeT $ return Nothing -- assenyala fallada

 
 tm_v >>= f = MaybeT (do -- el tipus del bloc do és :: m (Maybe a)
 -- (el del component del constructor MaybeT)
 maybeV <- runMaybeT tm_v
 case maybeV of
 Nothing -> return Nothing -- no avalúa l'efecte subseqüent
 Just v -> runMaybeT $ f v -- sí que l'avalua (f :: a -> MaybeT m a)
)

La classe MonadTrans

La classe MonadTrans aporta lift que eleva un efecte des d'una mònada m a la mònada transformada (t m). Continuant el codi anterior:

-- liftM (de Control.Monad) eleva el tipus d'una funció de valors
-- a una funció d'efectes

liftM :: (Monad m) => (a -> b) -> (m a -> m b)
liftM f = \m_x -> do 
 x <- m_x
 return (f x)

-- ''lift'' de MonadTrans eleva un efecte de la "mònada m" a la "mònada (t m)"

class MonadTrans t where
 lift :: (Monad m) => m a -> t m a 

-- implementació per a MaybeT

instance MonadTrans MaybeT where
 -- elevem efectes de ''m'' amb categoria d'exitoses

 lift m_x = (MaybeT. liftM Just) m_x

Exemple d'ús

Farem servir el transformador MaybeT que combina les computacions que poden fallar (vegeu més amunt) sobre la mònada IO resultant la mònada (MaybeT IO)

Caldrà elevar el tipus de les operacions sobre la mònada IO al de la mònada (MaybeT IO) amb lift.

runMaybeT permet "rebaixar" (contrari de lift: elevar) el tipus d'un efecte, de la mònada transformada (MaybeT m) al tipus de la mònada subjacent:

{-# LANGUAGE PackageImports #-}
import Numeric (readSigned, readFloat)
import Text.Printf (printf)
import System.IO (hFlush, stdout)
-- les importacions següents del MaybeT oficial 
-- poden ser substituïdes per la implementació de l'apartat precedent
import "transformers" Control.Monad.Trans.Maybe (MaybeT(..))
import "transformers" Control.Monad.Trans.Class (lift)


llegirReal :: String -> Maybe Double
llegirReal str = case (readSigned readFloat) str of
 [(r, "")] -> Just r -- només val si no hi ha altres caràcters
 _ -> Nothing

deMaybe_a_MaybeTIO :: Maybe a -> MaybeT IO a
deMaybe_a_MaybeTIO = MaybeT. return

obtenirRealVàlid :: MaybeT IO Double -- mònada (MaybeT IO)
obtenirRealVàlid = do
 lift $ putStr "entreu nombre real: "
 lift $ hFlush stdout
 strLínia <- lift getLine
 deMaybe_a_MaybeTIO $ llegirReal strLínia

obtenirLArrelQuadrada :: Double -> MaybeT IO Double
obtenirLArrelQuadrada x
 | x < 0 = do
 lift $ putStrLn "Entrada negativa"
 fail ""
 | x == 0 = return 0
 | otherwise = return $ sqrt x

-- en cas que ''obtenirRealVàlid'' falli, ''obtenirLArrelQuadrada'' no s'avalua.

main = do

 v <- runMaybeT $ obtenirRealVàlid >>= obtenirLArrelQuadrada
 case v of
 Just v -> printf "el valor és: %6.2f\n" v
 Nothing -> putStrLn "lectura fallida, o bé, valor iŀlegal"

Excepcions en una mònada - La classe MonadError

És un mecanisme de simulació d'excepcions només amb el tractament monàdic.

Implementa l'estratègia de combinar computacions que poden llançar excepcions saltant-se les computacions encadenades que segueixen la que llança l'error, fins a la sortida del gestor d'excepcions on recupera l'encadenament habitual.

class Monad m => MonadError excep m | m -> excep where
 throwError :: excep -> m a -- llança l'excepció
 catchError :: m a -> (excep -> m a) -> m a -- caça l'excepció i la gestiona
 -- do { acció1; throwError err; acció3 } `catchError` gestorDExcepcions
 -- el bloc i el gestor d'excepcions han de donar resultat del mateix tipus
 -- segons es desprèn de la definició 
 -- i es mostra a la implementació de l'exemple que segueix

Exemple: la mònada (Either tipusExcepció)

El tipus (Either tipusExcepció tipusResultat) millora la info. del tipus Maybe afegint-hi informació de l'error. El constructor Right introdueix el resultat Correcte i el constructor Left l'Error. Igual que amb el tipus Maybe, el podem fer servir de tipus de computació com a mònada ((Either tipusExcepció) tipusResultat).

data Either tipusExcepció tipusResultat = Left tipusExcepció | Right tipusResultat

-- prenem errors de tipus String per fer-ho senzill

instance Monad (Either String) where
 return x = Right x
 fail err = Left err

 (Left err) >>= _ = Left err -- element absorbent en (>>=), no avalua la computació subseqüent
 (Right x) >>= f = f x 

instance MonadError String (Either String) where

 throwError err = Left err -- assenyala excepció

 catchError (Left err) gestorDExcepcions = gestorDExcepcions err -- gestiona l'excepció
 catchError (Right x) _ = Right x -- no hi ha hagut excepció

Més mònades rellevants en Haskell

La mònada Writer

Facilita la generació de traces i enregistraments (ang:logs) sense barrejar-los amb els resultats.

El domini de la mònada és un parell amb el resultat i l'enregistrament. Aquest darrer ha d'implementar un Monoide.

newtype Writer log a = Writer { runWriter :: (a, log) } -- ''log'' és l'enregistrament

instance (Monoid log) => Monad (Writer log) where
 return x = Writer (x, mempty) -- genera una dada efecte amb el ''log'' buit
 (Writer (x, log)) >>= f = let (x', log') = runWriter $ f x -- l'aplicació de l'efecte funció (segon operand) genera un log'
 in Writer (x', log `mappend` log') -- que s'afegeix al log preexistent

--
class (Monoid log, Monad m) => MonadWriter log m | m -> log where
 pass :: m (a, log -> log) -> m a 
 listen :: m a -> m (a, log)
 tell :: log -> m ()

instance (Monoid log) => MonadWriter log (Writer log) where
 pass (Writer ((x, f), logval)) = Writer (x, f logval) -- sobre una computació de resultat parell (valor, f: log -> log)
 -- aplica la funció sobre el log i retorna el valor com a resultat 
 listen (Writer (x, logval)) = Writer ((x, logval), logval) -- ofereix el parell com a resultat
 tell s = Writer ((), s) -- estableix ''s'' al ''log''

-- censor: aporta la funció per aplicar al ''log'' mitjançant ''pass''
censor :: (MonadWriter log m) => (log -> log) -> m a -> m a 
censor f m_x = pass $ do x <- m_x ; 
 return (x, f) 

-- listens: obté el parell retornat per listen i hi aplica un selector al segon element
listens :: (MonadWriter log m) => (log -> b) -> m a -> m (a, b)
listens sel m_x = listen m_x >>= (return. fmap sel)

pass

passa una funció per aplicar sobre l'enregistrament, aparellant-la amb el resultat

listen

obté el parell (resultat, enregistrament)

tell

estableix l'enregistrament al valor especificat

censor

aporta la funció per aplicar a l'enregistrament i l'aplica amb pass

listens

obté el parell retornat per listen i el retorna aplicant un selector a l'enregistrament

• Exemple d'ús amb el transformador WriterT.

import Control.Monad.Writer 

exemple :: Monad m => WriterT String m Int
exemple = tell "a" >> tell "b" >> return 1

main = runWriterT exemple >>= print

dona el resultat

$ runhaskell prova.hs
(1,"ab")

• Exemple d'ús sense transformador. la biblioteca de GHC a Control.Monad.Writer no inclou el tipus, i cal definir-lo, instanciant les classes requerides:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

import Data.Monoid
import qualified Control.Monad.Writer as W

newtype Writer log a = Writer { runWriter :: (a, log) }

-- instanciem la classe Functor, base per a la classe Applicative
instance Functor (Writer log) where
 fmap f (Writer (x, w)) = Writer (f x, w)

-- instanciem la classe Applicative, base per a la Monad
instance (Monoid log) => Applicative (Writer log) where
 pure x = Writer (x, mempty)
 Writer (f, w) <*> Writer (x, w') = Writer (f x, w `mappend` w')

-- finalment instanciem Monad
instance (Monoid log) => Monad (Writer log) where
 Writer (x, w) >>= f = let (x', w') = runWriter $ f x
 in Writer (x', w `mappend` w')

-- i també MonadWriter
instance (Monoid log) => W.MonadWriter log (Writer log) where
 pass (Writer ((x, f), w)) = Writer (x, f w)
 listen (Writer (x, w)) = Writer ((x, w), w)
 tell s = Writer ((), s)

exemple :: Writer String Int
exemple = W.tell "a" >> W.tell "b" >> return 1

main = print $ runWriter exemple

dona el resultat

$ runhaskell prova.hs
(1,"ab")

La mònada State

Facilita l'enfilada d'un estat a través de computacions que el modifiquen, encapsulant-ne els canvis en codi funcional pur.

Els valors de la mònada State són funcions de transició entre estats del tipus (estat -> (resultat, nouEstat)). Per avaluar-lo caldrà aplicar-lo sobre un estat inicial, obtenint un parell amb el resultat en primera posició: (runState computacióMonadState) estatInicial

newtype State s a = State { runState :: (s -> (a, s)) } 

instance Monad (State s) where 
 return x = State $ \s -> (x, s) -- estableix el resultat
 (State tf) >>= f = State $ \s -> let (x, s') = tf s -- obté el (resultat, nouEstat) del primer efecte 
 in runState (f x) s' -- aplica (runState (f resultat)) sobre el nouEstat del primer efecte

---
class MonadState m s | m -> s where 
 get :: m s
 put :: s -> m ()

instance MonadState (State s) s where 
 get = State $ \s -> (s, s) -- obté l'estat
 put s = State $ \_ -> ((), s) -- estableix l'estat

La mònada Reader

Facilita l'arrossegament d'un entorn d'associacions variable, per exemple la substitució de textos definits en plantilles, que poden augmentar o ésser tapades per noves definicions.

El valor de la mònada Reader és una funció sobre l'entorn: (entorn -> resultat). Per avaluar-lo caldrà aplicar-lo sobre un entorn inicial: (runReader computacióMonadReader) entornInicial

newtype Reader env a = Reader { runReader :: (env -> a) } -- env per environment 

instance Monad (Reader env) where
 return x = Reader $ \_ -> x -- genera computació amb resultat fix
 (Reader r) >>= f = Reader $ \env -> runReader (f (r env)) env -- r :: (env -> a)

--
class MonadReader env m | m -> env where
 ask :: m env
 local :: (env -> env) -> m a -> m a

instance MonadReader (Reader env) where
 ask = Reader id
 local f computació = Reader $ \env -> runReader computació (f env)

asks :: (MonadReader env m) => (env -> a) -> m a
asks sel = ask >>= return. sel

ask

obté l'entorn

local

avalua un efecte havent modificat l'entorn amb una funció (env -> env)

asks

obté el resultat d'aplicar un selector (env -> a) sobre l'entorn.

Vegeu l'exemple.

La mònada STM

STM (Software Transactional Memory) permet l'actualització consistent de variables en diferents fils d'execució mitjançant transaccions en memòria que admeten tot o res d'una seqüència de lectures i modificacions de les variables transaccionals.

Vegeu Haskell concurrent - STM.

La mònada Par

Encadenament de càlculs simultanis

El Functor aplicatiu Concurrently

A la biblioteca async, facilita l'execució simultània d'operacions I/O no blocants on el tipus Concurrently implementa un functor aplicatiu que permet combinar els resultats d'accions engegades asíncronament, esperant-ne la finalització conjunta, i també implementa Alternative per obtenir el resultat de la primera que acaba, anul·lant els fils d'execució de la resta d'operacions engegades.

Mònades a l'OCaml

• la biblioteca LWT (light-weight cooperative threads) modela la seqüenciació de computacions d'entrada/sortida no-blocants (asíncrones) en una mònada.

• la biblioteca coThreads proporciona la mònada STM a OCaml

• Guia sobre Mònades per a OCaml Arxivat 2012-02-27 a Wayback Machine. (anglès)

• Extensió sintàctica per a les mònades a OCaml.

Mònades a l'F#

Vegeu Computation expressions i també Async. Workflows

• Extensió sintàctica per a les Mònades a F#.

Mònades a Scala

La clàusula for corresponent a les llistes per comprensió respon a un encadenament monàdic.

Si en comptes de llistes hi subministrem dades de tipus Option[A] el resultat és també del tipus de la mònada Option (equivalent de la Maybe en Haskell).

Vegeu presentació "Introduction to Monads in Scala".

scala> val opt3 = Some(3)
scala> val opt4 = Some(4)

scala> for { x <- opt3; y <- opt4} yield (x+y)
res4: Option[Int] = Some(7)

// desplegament equivalent en termes de ''flatMap'' i ''map'' (ops. de FilterMonadic)
scala> opt3 .flatMap { x => opt4 .map { y => x + y}}
res5: Option[Int] = Some(7)

Relacionat

• Functor aplicatiu
• Fletxa (programació funcional)

Enllaços externs

• Haskell.org - Tot sobre les mònades (anglès)
• Mònades al viquillibre anglès sobre Haskell (anglès)
• Difference between State, ST, IORef, and MVar Diferències entre les mònades State i ST, i les referències (punters) IORef i MVar