Saltar al contenido

haskell – ¿Qué es una mónada?

octubre 20, 2021
apple touch icon@2

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

close