haskell - learn - Composición de mónadas v. Funcionarios aplicativos

show data haskell

Question

La sección Transformadores Typeclassopedia de Typeclassopedia explica:

Desafortunadamente, las mónadas no se componen tan bien como los aplicadores (otra razón más para usar el aplicativo si no necesita toda la potencia que proporciona Monad)

Mirando los tipos de >>= y <*> , la declaración anterior no me queda clara.

(<*>) :: Applicative f => f (a -> b) -> f a -> f b
(>>=) :: Monad m => m a -> (a -> m b) -> m b

Por favor, explique que "las mónadas no componen tan bien como los functores aplicativos".

Leí esta answer , pero ¿podría darme un ejemplo para ayudarme a entender?

Answer 1

Hay varias nociones por las cuales los tipos de tipo * -> * pueden "componer". El más importante es que puedes componerlos "secuencialmente".

newtype Compose f g x = Compose { getCompose :: f (g x) }

Aquí puede ver que Compose tiene un tipo (* -> *) -> (* -> *) -> (* -> *) muy parecido a cualquier buena composición de functores.

Entonces la pregunta es: ¿hay instancias respetuosas de la ley como las siguientes?

instance (Applicative f, Applicative g) => Applicative (Compose f g)
instance (Monad f,       Monad g)       => Monad       (Compose f g)

Y la respuesta breve de por qué las mónadas no componen tan bien como los solicitantes es que, si bien la primera instancia se puede escribir, la segunda no. ¡Intentemos!

Podemos calentarnos con Functor

instance (Functor f,     Functor g)     => Functor     (Compose f g) where
  fmap f (Compose fgx) = Compose (fmap (fmap f) fgx)

Aquí vemos que debido a que podemos fmap un fmap podemos pasarlo a través de las capas f y g como sea necesario. Un juego similar se juega con pure

instance (Applicative f, Applicative g) => Applicative (Compose f g) where
  pure a = Compose (pure (pure a))

y aunque (<*>) parece complicado, si lo miras detenidamente, es exactamente el mismo truco que usamos con fmap y pure .

  Compose fgf <*> Compose fgx = Compose ((<*>) <$> fgf <*> fgx)

En todos los casos, podemos empujar a los operadores que necesitamos "a través" de las capas de f y g exactamente como podríamos esperar.

Pero ahora echemos un vistazo a Monad . En lugar de tratar de definir Monad través de (>>=) , voy a trabajar a través de join . Para implementar Monad necesitamos implementar

join :: Compose f g (Compose f g x) -> Compose f g x

utilizando

join_f :: f (f x) -> f x  -- and
join_g :: g (g x) -> g x

o, si eliminamos el ruido del nuevo tipo, necesitamos

join :: f (g (f (g x))) -> f (g x)

En este punto, podría quedar claro cuál es el problema: solo sabemos cómo unir capas consecutivas de f s o g s, pero aquí las vemos entretejidas . Lo que encontrará es que necesitamos una propiedad de conmutatividad

class Commute f g where
  commute :: g (f x) -> f (g x)

y ahora podemos implementar

instance (Monad f, Monad g, Commute f g) => Monad (Compose f g)

con (el newtype agnóstico) join definido como

join :: f (g (f (g x))) -> f (g x)
join fgfgx = fgx where
  ffggx :: f (f (g (g x)))
  ffggx = fmap commute fgfgx
  fggx :: f (g (g x))
  fggx = join_f ffggx
  fgx :: f (g x)
  fgx = fmap join_g fggx

Entonces, ¿cuál es el resultado de todo esto? Applicative siempre Compose , pero Monad solo Compose cuando sus capas Commute .

¿Cuándo podemos commute capas? Aquí hay unos ejemplos

instance Commute ((->) x) ((->) y) where
  commute = flip

instance Commute ((,) x) ((,) y) where
  commute (y, (x, a)) = (x, (y, a))

instance Commute ((->) x) ((,) y) where
  commute (y, xa) = /x -> (y, xa x)

-- instance Commute ((,) x) ((->) y) does not exist; try to write yourself!
--
-- OR:
-- It turns out that you need to somehow "travel back in time" to make it
-- work...
-- 
-- instance Commute ((,) x) ((->) y) where
--   commute yxa = ( ..., /y -> let (x, a) = yxa y in a )