haskell - monadologia - monadas leibniz

¿Qué pueden hacer las flechas que las mónadas no pueden?

Question

Las flechas parecen estar ganando popularidad en la comunidad de Haskell, pero me parece que las Mónadas son más poderosas. ¿Qué se gana usando flechas? ¿Por qué no se pueden usar Mónadas en su lugar?

Answer 1

Bueno, voy a hacer un poco de trampa aquí cambiando la pregunta de Arrow a Applicative . Se aplican muchos de los mismos motivos, y conozco los aplicativos mejor que las flechas. (Y, de hecho, cada Arrow también es un Applicative pero no al revés , así que solo lo estoy bajando un poco más hacia la pendiente hasta Functor ).

Al igual que cada Monad es una Arrow , cada Monad también es un Applicative . Hay Applicatives que no son Monad s (por ejemplo, ZipList ), así que esa es una respuesta posible.

Pero supongamos que estamos tratando con un tipo que admite una instancia de Monad además de un Applicative . ¿Por qué podríamos usar la instancia de Applicative lugar de Monad ? Debido a que Applicative es menos poderoso, y eso viene con beneficios:

1. Hay cosas que sabemos que la Monad puede hacer que el Applicative no puede. Por ejemplo, si usamos la instancia Applicative de IO para ensamblar una acción compuesta de otras más simples, ninguna de las acciones que compongamos podrá usar los resultados de ninguna de las otras. Todo lo que puede hacer el IO aplicativo es ejecutar las acciones del componente y combinar sus resultados con funciones puras.
2. Applicative tipos de Applicative se pueden escribir para que podamos realizar un análisis estático de las acciones antes de ejecutarlas. Entonces, puede escribir un programa que inspeccione una acción de Applicative antes de ejecutarlo, descubra qué va a hacer y lo utiliza para mejorar el rendimiento, decirle al usuario qué va a hacer, etc.

Como ejemplo de lo primero, he estado trabajando en el diseño de un tipo de lenguaje de cálculo OLAP utilizando Applicative s. El tipo admite una instancia de Monad , pero he evitado deliberadamente tener eso, porque quiero que las consultas sean menos poderosas de lo que Monad permitiría. Applicative significa que cada cálculo se reducirá a un número predecible de consultas.

Como ejemplo de este último, usaré un ejemplo de juguete de mi biblioteca operativa operativa todavía en desarrollo . Si escribe la mónada del Reader como un programa de Applicative operativa, puede examinar los Reader resultantes para contar cuántas veces utilizan la operación ask :

{-# LANGUAGE GADTs, RankNTypes, ScopedTypeVariables #-}

import Control.Applicative.Operational

-- | A ''Reader'' is an ''Applicative'' program that uses the ''ReaderI'' 
-- instruction set.
type Reader r a = ProgramAp (ReaderI r) a

-- | The only ''Reader'' instruction is ''Ask'', which requires both the
-- environment and result type to be @r@.
data ReaderI r a where
    Ask :: ReaderI r r

ask :: Reader r r
ask = singleton Ask

-- | We run a ''Reader'' by translating each instruction in the instruction set
-- into an @r -> a@ function.  In the case of ''Ask'' the translation is ''id''.
runReader :: forall r a. Reader r a -> r -> a
runReader = interpretAp evalI
    where evalI :: forall x. ReaderI r x -> r -> x
          evalI Ask = id

-- | Count how many times a ''Reader'' uses the ''Ask'' instruction.  The ''viewAp''
-- function translates a ''ProgramAp'' into a syntax tree that we can inspect.
countAsk :: forall r a. Reader r a -> Int
countAsk = count . viewAp
    where count :: forall x. ProgramViewAp (ReaderI r) x -> Int
          -- Pure :: a -> ProgamViewAp instruction a
          count (Pure _) = 0
          -- (:<**>) :: instruction a 
          --         -> ProgramViewAp instruction (a -> b)
          --         -> ProgramViewAp instruction b
          count (Ask :<**> k) = succ (count k)

Como mejor entiendo, no puedes escribir countAsk si implementas Reader como una mónada. (Mi entendimiento viene de preguntar aquí mismo en , agregaré ).

Este mismo motivo es en realidad una de las ideas detrás de Arrow s. Uno de los grandes ejemplos de motivación para Arrow fue el diseño de un combinador de analizador que utiliza "información estática" para obtener un mejor rendimiento que los analizadores monádicos. Lo que quieren decir con "información estática" es más o menos lo mismo que en mi ejemplo de Reader : es posible escribir una instancia de Arrow en la que los analizadores puedan ser inspeccionados de manera muy similar a la de mi Reader . Luego, la biblioteca de análisis puede, antes de ejecutar un analizador, inspeccionarla para ver si puede predecir con anticipación que fallará, y omitirla en ese caso.

En uno de los comentarios directos a su pregunta, Jberryman menciona que las flechas pueden estar perdiendo popularidad. Yo agregaría que, tal como lo veo, Applicative es a lo que las flechas están perdiendo popularidad.

Referencias:

• Paolo Capriotti y Ambrus Kaposi, "Free Applicative Functors" . Muy recomendable.
• Gergo Erdi, "Análisis estático con aplicativos" . Inspirador, pero me cuesta seguirlo ...

Answer 2

Cada mónada da lugar a una flecha.

newtype Kleisli m a b = Kleisli (a -> m b)
instance Monad m => Category (Kleisli m) where
   id = Kleisli return
   (Kleisli f) . (Kleisli g) = Kleisli (/x -> (g x) >>= f)
instance Monad m => Arrow (Kleisli m) where
   arr f = Kleisli (return . f)
   first (Kleisli f) = Kleisli (/(a,b) -> (f a) >>= /fa -> return (fa,b))

Pero, hay flechas que no son mónadas. Por lo tanto, hay flechas que hacen cosas que no puedes hacer con las mónadas. Un buen ejemplo es el transformador de flecha para agregar información estática.

data StaticT m c a b = StaticT m (c a b)
instance (Category c, Monoid m) => Category (StaticT m c) where
   id = StaticT mempty id
   (StaticT m1 f) . (StaticT m2 g) = StaticT (m1 <> m2) (f . g)
instance (Arrow c, Monoid m) => Arrow (StaticT m c) where
   arr f = StaticT mempty (arr f)
   first (StaticT m f) = StaticT m (first f)

Este transformador de flechas es útil porque se puede utilizar para realizar un seguimiento de las propiedades estáticas de un programa. Por ejemplo, puede usar esto para instrumentar su API para medir de manera estática cuántas llamadas está haciendo.

Answer 3

La pregunta no es del todo correcta. Es como preguntar por qué comerías naranjas en lugar de manzanas, ya que las manzanas parecen más nutritivas en general.

Las flechas, como las mónadas, son una forma de expresar cálculos, pero tienen que obedecer a un conjunto diferente de laws . En particular, las leyes tienden a hacer que las flechas sean más fáciles de usar cuando tienes cosas similares a una función.

El Wiki de Haskell enumera algunas introducciones a las flechas. En particular, el Wikibook es una buena introducción de alto nivel, y el tutorial de John Hughes es una buena descripción general de los distintos tipos de flechas.

Para un ejemplo del mundo real, compare este tutorial que usa la interfaz basada en flechas de Hakyll 3, con aproximadamente lo mismo en la interfaz basada en mónada de Hakyll 4.

Answer 4

Siempre encontré uno de los casos de uso muy prácticos de las flechas para ser la programación de secuencias .

Mira esto:

data Stream a = Stream a (Stream a)
data SF a b = SF (a -> (b, SF a b))

SF ab es una función de flujo síncrono. Puede definir una función a partir de ella que transforme la Stream a en la Stream b que nunca se cuelga y siempre genera una b para una a :

(<<$>>) :: SF a b -> Stream a -> Stream b
SF f <<$>> Stream a as = let (b, sf'') = f a
                         in  Stream b $ sf'' <<$>> as

Hay una instancia de Arrow para SF . En particular, puedes componer SF s:

(>>>) :: SF a b -> SF b c -> SF a c

Ahora trata de hacer esto en mónadas. No funciona bien Se podría decir que Stream a == Reader Nat a y, por lo tanto, es una mónada, pero la instancia de mónada es muy ineficiente. Imagina el tipo de join :

join :: Stream (Stream a) -> Stream a

Tienes que extraer la diagonal de un flujo de corrientes. Esto significa O(n) complejidad para el elemento n , ¡pero el uso de la instancia de Arrow para SF s le da en principio O(1) ! (Y también se ocupa de las fugas de tiempo y espacio.)

Answer 5

Siempre me ha resultado difícil pensar en el tema en estos términos: lo que se gana con las flechas. Como otros comentaristas han mencionado, cada mónada puede convertirse trivialmente en una flecha. Así que una mónada puede hacer todas las cosas con flechas. Sin embargo, podemos hacer flechas que no sean mónadas. Es decir, podemos hacer tipos que puedan hacer estas cosas con flechas sin que sean compatibles con el enlace monádico. Puede que no parezca el caso, pero la función de enlace monádico es en realidad una operación bastante restrictiva (por lo tanto, poderosa) que descalifica a muchos tipos.

Mira, para admitir el enlace, tienes que poder afirmar que, independientemente del tipo de entrada, lo que saldrá va a estar envuelto en la mónada.

(>>=) :: forall a b. m a -> (a -> m b) -> m b

Pero, ¿cómo definiríamos el enlace para un tipo de data Foo a = F Bool a Seguramente, podríamos combinar un Foo''s con otro pero cómo combinaríamos los Bools? Imagine que el Bool marcó, digamos, si el valor del otro parámetro ha cambiado o no. Si tengo a = Foo False whatever y lo vinculo a una función, no tengo idea de si esa función va a cambiar o no. No puedo escribir un enlace que establece correctamente el Bool. Esto a menudo se llama el problema de la meta-información estática. No puedo inspeccionar la función vinculada para determinar si modificará o no lo que whatever .

Hay varios otros casos como este: tipos que representan funciones de mutación, analizadores que pueden salir antes, etc. Pero la idea básica es esta: las mónadas establecen una barra alta que no todos los tipos pueden borrar. Las flechas le permiten componer tipos (que pueden o no ser capaces de soportar este estándar alto y vinculante) de manera poderosa sin tener que satisfacer el enlace. Por supuesto, pierdes algo del poder de las mónadas.

Moraleja de la historia: no hay nada que una flecha pueda hacer que una mónada no pueda, porque una mónada siempre puede convertirse en una flecha. Sin embargo, a veces no puede hacer que sus tipos se conviertan en mónadas, pero aún así desea permitirles tener la mayor flexibilidad y el poder de composición de las mónadas.

Muchas de estas ideas se inspiraron en el magnífico Understanding Haskell Arrows.