tl; dr
{-# LANGUAGE InstanceSigs #-}
newtype Id t = Id t
instance Monad Id where
return :: t -> Id t
return = Id
(=<<) :: (a -> Id b) -> Id a -> Id b
f =<< (Id x) = f x
Prólogo
El operador de la aplicación $ de funciones
forall a b. a -> b
está definido canónicamente
($) :: (a -> b) -> a -> b
f $ x = f x
infixr 0 $
en términos de la aplicación de la función primitiva de Haskell f x (infixl 10).
Composición . se define en términos de $ como
(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = x -> f $ g x
infixr 9 .
y satisface las equivalencias forall f g h.
f . id = f :: c -> d Right identity
id . g = g :: b -> c Left identity
(f . g) . h = f . (g . h) :: a -> d Associativity
. es asociativo, y id es su identidad de derecha e izquierda.
El triple de Kleisli
En programación, una mónada es un constructor de tipo functor con una instancia de la clase de tipo mónada. Hay varias variantes equivalentes de definición e implementación, cada una con intuiciones ligeramente diferentes sobre la abstracción de la mónada.
Un functor es un constructor de tipos f de amable * -> * con una instancia de la clase de tipo functor.
{-# LANGUAGE KindSignatures #-}
class Functor (f :: * -> *) where
map :: (a -> b) -> (f a -> f b)
Además de seguir el protocolo de tipo aplicado estáticamente, las instancias de la clase de tipo de functor deben obedecer al algebraico leyes functor forall f g.
map id = id :: f t -> f t Identity
map f . map g = map (f . g) :: f a -> f c Composition / short cut fusion
Functor cálculos tener el tipo
forall f t. Functor f => f t
Un cálculo c r consiste en resultados r dentro de contexto c.
Funciones monádicas unarias o Flechas de Kleisli tener el tipo
forall m a b. Functor m => a -> m b
Las flechas de Kleisi son funciones que toman un argumento a y devuelve un cálculo monádico m b.
Las mónadas se definen canónicamente en términos de Kleisli triple forall m. Functor m =>
(m, return, (=<<))
implementado como la clase de tipo
class Functor m => Monad m where
return :: t -> m t
(=<<) :: (a -> m b) -> m a -> m b
infixr 1 =<<
los Identidad Kleisli return es una flecha de Kleisli que promueve un valor t en contexto monádico m. Extensión o Aplicación Kleisli =<< aplica una flecha de Kleisli a -> m b a los resultados de un cálculo m a.
Composición de Kleisli <=< se define en términos de extensión como
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
f <=< g = x -> f =<< g x
infixr 1 <=<
<=< compone dos flechas Kleisli, aplicando la flecha izquierda a los resultados de la aplicación de la flecha derecha.
Las instancias de la clase de tipo mónada deben obedecer las leyes de la mónada, expresado de la manera más elegante en términos de composición de Kleisli: forall f g h.
f <=< return = f :: c -> m d Right identity
return <=< g = g :: b -> m c Left identity
(f <=< g) <=< h = f <=< (g <=< h) :: a -> m d Associativity
<=< es asociativo, y return es su identidad de derecha e izquierda.
Identidad
El tipo de identidad
type Id t = t
es la función de identidad en tipos
Id :: * -> *
Interpretado como un funtor,
return :: t -> Id t
= id :: t -> t
(=<<) :: (a -> Id b) -> Id a -> Id b
= ($) :: (a -> b) -> a -> b
(<=<) :: (b -> Id c) -> (a -> Id b) -> (a -> Id c)
= (.) :: (b -> c) -> (a -> b) -> (a -> c)
En Haskell canónico, la mónada de identidad se define
newtype Id t = Id t
instance Functor Id where
map :: (a -> b) -> Id a -> Id b
map f (Id x) = Id (f x)
instance Monad Id where
return :: t -> Id t
return = Id
(=<<) :: (a -> Id b) -> Id a -> Id b
f =<< (Id x) = f x
Opción
Un tipo de opción
data Maybe t = Nothing | Just t
codifica el cálculo Maybe t que no necesariamente da un resultado t, cálculo que puede «fallar». La opción mónada está definida
instance Functor Maybe where
map :: (a -> b) -> (Maybe a -> Maybe b)
map f (Just x) = Just (f x)
map _ Nothing = Nothing
instance Monad Maybe where
return :: t -> Maybe t
return = Just
(=<<) :: (a -> Maybe b) -> Maybe a -> Maybe b
f =<< (Just x) = f x
_ =<< Nothing = Nothing
a -> Maybe b se aplica a un resultado solo si Maybe a produce un resultado.
newtype Nat = Nat Int
Los números naturales se pueden codificar como números enteros mayores o iguales a cero.
toNat :: Int -> Maybe Nat
toNat i | i >= 0 = Just (Nat i)
| otherwise = Nothing
Los números naturales no se cierran mediante la resta.
(-?) :: Nat -> Nat -> Maybe Nat
(Nat n) -? (Nat m) = toNat (n - m)
infixl 6 -?
La opción mónada cubre una forma básica de manejo de excepciones.
(-? 20) <=< toNat :: Int -> Maybe Nat
Lista
La lista mónada, sobre el tipo de lista
data [] t = [] | t : [t]
infixr 5 :
y su operación de monoide aditivo «agregar»
(++) :: [t] -> [t] -> [t]
(x : xs) ++ ys = x : xs ++ ys
[] ++ ys = ys
infixr 5 ++
codifica no lineal cálculo [t] produciendo una cantidad natural 0, 1, ... de resultados t.
instance Functor [] where
map :: (a -> b) -> ([a] -> [b])
map f (x : xs) = f x : map f xs
map _ [] = []
instance Monad [] where
return :: t -> [t]
return = (: [])
(=<<) :: (a -> [b]) -> [a] -> [b]
f =<< (x : xs) = f x ++ (f =<< xs)
_ =<< [] = []
Extensión =<< concatena ++ todas las listas [b] resultante de aplicaciones f x de una flecha de Kleisli a -> [b] a elementos de [a] en una sola lista de resultados [b].
Dejemos que los divisores propios de un entero positivo n ser
divisors :: Integral t => t -> [t]
divisors n = filter (`divides` n) [2 .. n - 1]
divides :: Integral t => t -> t -> Bool
(`divides` n) = (== 0) . (n `rem`)
luego
forall n. let { f = f <=< divisors } in f n = []
Al definir la clase de tipo mónada, en lugar de extensión =<<, el estándar Haskell usa su tapa, la unir operador >>=.
class Applicative m => Monad m where
(>>=) :: forall a b. m a -> (a -> m b) -> m b
(>>) :: forall a b. m a -> m b -> m b
m >> k = m >>= _ -> k
{-# INLINE (>>) #-}
return :: a -> m a
return = pure
En aras de la simplicidad, esta explicación utiliza la jerarquía de clases de tipos
class Functor f
class Functor m => Monad m
En Haskell, la jerarquía estándar actual es
class Functor f
class Functor p => Applicative p
class Applicative m => Monad m
porque no solo cada mónada es un funtor, sino que cada aplicativo es un funtor y cada mónada es también un aplicativo.
Usando la lista mónada, el pseudocódigo imperativo
for a in (1, ..., 10)
for b in (1, ..., 10)
p <- a * b
if even(p)
yield p
se traduce aproximadamente a la bloquear,
do a <- [1 .. 10]
b <- [1 .. 10]
let p = a * b
guard (even p)
return p
el equivalente comprensión de la mónada,
[ p | a <- [1 .. 10], b <- [1 .. 10], let p = a * b, even p ]
y la expresion
[1 .. 10] >>= ( a ->
[1 .. 10] >>= ( b ->
let p = a * b in
guard (even p) >> -- [ () | even p ] >>
return p
)
)
Las comprensiones de notación y mónada son azúcar sintáctico para expresiones de vinculación anidadas. El operador de vinculación se utiliza para la vinculación de nombres locales de resultados monádicos.
let x = v in e = ( x -> e) $ v = v & ( x -> e)
do { r <- m; c } = ( r -> c) =<< m = m >>= ( r -> c)
dónde
(&) :: a -> (a -> b) -> b
(&) = flip ($)
infixl 0 &
La función de guardia está definida
guard :: Additive m => Bool -> m ()
guard True = return ()
guard False = fail
donde el tipo de unidad o «tupla vacía»
data () = ()
Mónadas aditivas Ese apoyo elección y falla se puede abstraer usando una clase de tipo
class Monad m => Additive m where
fail :: m t
(<|>) :: m t -> m t -> m t
infixl 3 <|>
instance Additive Maybe where
fail = Nothing
Nothing <|> m = m
m <|> _ = m
instance Additive [] where
fail = []
(<|>) = (++)
dónde fail y <|> formar un monoide forall k l m.
k <|> fail = k
fail <|> l = l
(k <|> l) <|> m = k <|> (l <|> m)
y fail es el elemento cero absorbente / aniquilador de las mónadas aditivas
_ =<< fail = fail
Si en
guard (even p) >> return p
even p es cierto, entonces el guardia produce [()], y, por la definición de >>, la función constante local
_ -> return p
se aplica al resultado (). Si es falso, entonces el guardia produce la lista de mónadas. fail ( [] ), que no produce ningún resultado para que se aplique una flecha de Kleisli >> a, entonces esto p se omite.
Estado
Infamemente, las mónadas se utilizan para codificar cálculos con estado.
A procesador de estado es una función
forall st t. st -> (t, st)
que hace la transición de un estado st y da un resultado t. los estado st puede ser cualquier cosa. Nada, bandera, recuento, matriz, mango, máquina, mundo.
El tipo de procesadores de estado se suele llamar
type State st t = st -> (t, st)
La mónada del procesador de estado es la especie * -> * functor State st. Las flechas de Kleisli de la mónada del procesador de estado son funciones
forall st a b. a -> (State st) b
En Haskell canónico, la versión perezosa de la mónada del procesador de estado se define
newtype State st t = State { stateProc :: st -> (t, st) }
instance Functor (State st) where
map :: (a -> b) -> ((State st) a -> (State st) b)
map f (State p) = State $ s0 -> let (x, s1) = p s0
in (f x, s1)
instance Monad (State st) where
return :: t -> (State st) t
return x = State $ s -> (x, s)
(=<<) :: (a -> (State st) b) -> (State st) a -> (State st) b
f =<< (State p) = State $ s0 -> let (x, s1) = p s0
in stateProc (f x) s1
Un procesador de estado se ejecuta proporcionando un estado inicial:
run :: State st t -> st -> (t, st)
run = stateProc
eval :: State st t -> st -> t
eval = fst . run
exec :: State st t -> st -> st
exec = snd . run
El acceso de estado es proporcionado por primitivas get y put, métodos de abstracción sobre con estado mónadas:
{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}
class Monad m => Stateful m st | m -> st where
get :: m st
put :: st -> m ()
m -> st declara un dependencia funcional del tipo de estado st en la mónada m; que una State t, por ejemplo, determinará el tipo de estado a ser t de forma única.
instance Stateful (State st) st where
get :: State st st
get = State $ s -> (s, s)
put :: st -> State st ()
put s = State $ _ -> ((), s)
con el tipo de unidad utilizado análogamente a void C ª.
modify :: Stateful m st => (st -> st) -> m ()
modify f = do
s <- get
put (f s)
gets :: Stateful m st => (st -> t) -> m t
gets f = do
s <- get
return (f s)
gets se utiliza a menudo con accesos de campo de registro.
El equivalente de la mónada de estado del subproceso variable
let s0 = 34
s1 = (+ 1) s0
n = (* 12) s1
s2 = (+ 7) s1
in (show n, s2)
dónde s0 :: Int, es el igualmente transparente referencialmente, pero infinitamente más elegante y práctico
(flip run) 34
(do
modify (+ 1)
n <- gets (* 12)
modify (+ 7)
return (show n)
)
modify (+ 1) es un cálculo de tipo State Int (), excepto por su efecto equivalente a return ().
(flip run) 34
(modify (+ 1) >>
gets (* 12) >>= ( n ->
modify (+ 7) >>
return (show n)
)
)
La ley de la asociatividad de las mónadas se puede escribir en términos de >>= forall m f g.
(m >>= f) >>= g = m >>= ( x -> f x >>= g)
o
do { do { do {
r1 <- do { x <- m; r0 <- m;
r0 <- m; = do { = r1 <- f r0;
f r0 r1 <- f x; g r1
}; g r1 }
g r1 ...