haskell - Flecha y Mónada, ¿dos puntos de vista independientes para componer cálculos?

monads typeclass

Question

He leído "The Typeclassopedia" de Brent Yorgey en Monad.Reader#13 , y encontré que "la jerarquía de Functor" es interdependiente de "la jerarquía de categorías" como se muestra en la Figura.1.



Y de acuerdo con el autor, ArrowApply == Monad , especialmente que la anterior es solo una instancia de clase de tipo que se puede usar cuando

"nos gustaría poder calcular una flecha a partir de resultados intermedios, y usar esta flecha calculada para continuar el cálculo. Esta es la potencia que nos da ArrowApply".

Pero, ¿cómo podemos poner estas cosas juntas? Quiero decir que hay algunas funciones de control de flujo tanto en Monad como en Arrow (como if y else vs. ArrowChoice , o forM vs. ArrowLoop ), y algunas características parecen "desaparecidas" en Monad ( (***) , (|||) o first ). Todo esto parece que necesitamos hacer una elección entre usar el sistema Monad o Arrow para construir nuestro flujo de cómputo de efectos secundarios, y perderemos algunas características en otro sistema.

Answer 1

La respuesta está en lo siguiente (todo esto es de los documentos Control.Arrow )

newtype ArrowApply a => ArrowMonad a b = ArrowMonad (a () b)
instance Monad ArrowApply a => Monad (ArrowMonad a)

El ArrowMonad ArrowMonad es el vehículo con el que definimos la instancia de ArrowApply para ArrowApply flechas ArrowApply . Podríamos haber utilizado

instance Monad ArrowApply a => Monad (a ())

pero esto hubiera causado problemas con la inferencia de clase de tipo limitada de Haskell (funcionaría con la extensión UndecideableInstances , me parece).

Puede pensar en la instancia de ArrowApply para flechas ArrowApply como la conversión de operaciones monádicas en operaciones de flecha equivalentes, como muestra la fuente:

instance ArrowApply a => Monad (ArrowMonad a) where
        return x = ArrowMonad (arr (/_ -> x))
        ArrowMonad m >>= f = ArrowMonad (m >>>
                        arr (/x -> let ArrowMonad h = f x in (h, ())) >>>
                        app)

Entonces, sabemos que ArrowApply es tan poderoso como Monad ya que podemos implementar todas las operaciones de Monad en él. Sorprendentemente, lo contrario también es cierto. Esto es dado por el nuevo tipo de Kleisli como lo anotó @hammar. Observar:

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

instance Monad m => Category (Kleisli m) where
        id = Kleisli return
        (Kleisli f) . (Kleisli g) = Kleisli (/b -> g b >>= f)

instance Monad m => Arrow (Kleisli m) where
        arr f = Kleisli (return . f)
        first (Kleisli f) = Kleisli (/ ~(b,d) -> f b >>= /c -> return (c,d))
        second (Kleisli f) = Kleisli (/ ~(d,b) -> f b >>= /c -> return (d,c))

instance Monad m => ArrowApply (Kleisli m) where
        app = Kleisli (/(Kleisli f, x) -> f x)

instance Monad m => ArrowChoice (Kleisli m) where
    left f = f +++ arr id
    right f = arr id +++ f
    f +++ g = (f >>> arr Left) ||| (g >>> arr Right)
    Kleisli f ||| Kleisli g = Kleisli (either f g)

El anterior proporciona implementaciones para todas las operaciones de flecha habituales utilizando operaciones de mónada. (***) no se menciona ya que tiene una implementación predeterminada que utiliza first y second :

f *** g = first f >>> second g

Así que ahora sabemos cómo implementar las operaciones de flecha ( Arrow , ArrowChoice , ArrowApply ) utilizando las operaciones de ArrowApply .

Para responder a su pregunta sobre por qué tenemos tanto Monad como Arrow si resultan ser equivalentes:

Las flechas menos poderosas son útiles cuando no necesitamos toda la potencia de una mónada, al igual que los funtores aplicativos pueden ser útiles. Y aunque ArrowApply y ArrowApply son equivalentes, una Arrow o ArrowChoice sin app es algo que no se puede representar en la jerarquía de Monad . Viceversa, un Applicative no se puede representar en la jerarquía de flechas. Esto se debe a que ap viene "primero" en la jerarquía de la mónada y "último" en la jerarquía de flechas.

La principal diferencia semántica entre los mundos de la mónada y la flecha es que las flechas capturan una transformación ( arr bc significa que producimos una c de una b ), mientras que las mónadas capturan una operación (la monad a produce una a ). Esta diferencia se refleja bien en los ArrowMonad Kleisli y ArrowMonad :

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }
newtype ArrowApply a => ArrowMonad a b = ArrowMonad (a () b)

En Kleisli tenemos que agregar el tipo de fuente a , y en ArrowMonad lo configuramos en () .

Espero que esto te satisfaga!