teoria monadas moderna leibniz las filosofia educatina doctrina conocimiento haskell functional-programming monads arrows

haskell - moderna - monadas leibniz



¿Puede alguien explicarme por qué la función de aplicación de ArrowApply los hace tan poderosos como las mónadas? (3)

Alerta de declaraciones multiplicable-interpretable:

"A es más poderoso que B" ... "C es una generalización de D" ... "E puede hacer todo lo que F puede hacer, y más" ... "G es un subconjunto de H" ...

Primero debemos entender qué significamos con fuerza, etc. Supongamos que tenemos una clase GripHandle para cosas que tienen un mango de agarre, y otra clase de Screwdriver para destornilladores. ¿Cuál es más poderoso?

  • Claramente, si solo tienes una manija de agarre, eso no es tan útil como si fueras un destornillador; una empuñadura de agarre por sí sola no es de mucha utilidad, así que, obviamente, dado que se puede hacer más con un destornillador que con una manija de agarre, los destornilladores son más potentes.
  • Claramente, hay más cosas que tienen mango de agarre que solo destornilladores: taladros, cuchillos y tenedores, todo tipo de cosas tienen agarraderas, por lo que las manijas de agarre son más potentes y flexibles.
  • Claramente, si tienes un destornillador, no solo puedes sostenerlo, puedes girarlo, y tener la habilidad de girar en lugar de solo sostenerlo hace que los destornilladores sean mucho más potentes y flexibles que los asideros.

OK, eso es un argumento tonto, pero plantea un buen punto acerca de cómo la frase "Puedes hacer más con un _____" es bastante ambigua.

Si te fijas solo en la interfaz, un destornillador es más útil que un mango, pero todas las cosas con agarraderas son más útiles que todos los destornilladores si utilizas más funciones que solo la interfaz.

Cómo funciona la jerarquía

A es más general que B
= A capacidades de solo interfaz de A son un subconjunto de B ''s = puede hacer más con una instancia B (solo)
= La clase de todos B s es un subconjunto de la clase de todos A s = hay más A s que B s = puede hacer más con la clase A

mas general
= más instancias posibles
= capaz de ser más ampliamente utilizado
= puede hacer cosas extra detrás de la escena
= se especifican menos capacidades en la interfaz
= puede hacer menos cosas a través de la interfaz

¿Cuál es la jerarquía entre flechas y mónadas?

  • Arrow es más general que Monad .
  • ArrowApply es exactamente tan general como Monad .

Estas dos afirmaciones se prueban con todo detalle en el documento al que Petr Pudlák se relaciona en su comentario: los modismos son ajenos, las flechas son meticulosas, las mónadas son promiscuas .

Las aserciones en A y B

  • "Las flechas pueden hacer todo lo que las mónadas pueden hacer, y más".
    Esto es marketing. Es cierto, pero tienes que saltar un poco semánticamente para hacerlo realidad. Una instancia de ArrowApply en sí misma le permite hacer todo lo que hace una instancia de ArrowApply . No puede hacer más con un ArrowApply que con un Monad . Puedes hacer más con cosas que son Arrows . El reclamo "todo lo que las mónadas pueden hacer" probablemente se refiere a ArrowApply mientras que el reclamo "y más" probablemente se refiera a Arrow . La junta de marketing de Monad podría decir "Con Mónadas, puedes hacer todo lo que las flechas pueden hacer, y más" debido a la mayor expresividad de la interfaz. Estas declaraciones son ambiguas y tienen poco significado formal debido a eso.
  • "Son más o menos comparables a las mónadas con un componente estático".
    Estrictamente hablando, no, eso es algo que puedes hacer con Arrow que no puedes hacer directamente con una Monad , no es un hecho matemático sobre la interfaz de Arrow. Es una forma de ayudarlo a comprender lo que podríamos hacer con una Flecha, de forma similar a la analogía de que una Mónada es una caja con un valor. No todas las mónadas son fácilmente interpretables como una caja con un valor en, pero podría ayudarte un poco en las primeras etapas.
  • "Las flechas son un subconjunto de mónadas"
    Esto es quizás engañoso. Es cierto que las capacidades solo de interfaz de las flechas son un subconjunto de las capacidades de solo interfaz de las mónadas, pero es más justo decir que la clase de todas las mónadas es un subconjunto de la clase de todas las flechas, porque la Arrow es más general.
  • "Con ArrowApply podemos definir una mónada"
    Sí. Ver más adelante, y con una Mónada, podemos definir un ArrowApply.

Tus cuatro preguntas

  1. ¿Hay algo de verdad en el punto de vista A?
    Algunos. Véase más arriba. Hay algo de verdad en B también. Ambos son engañosos de una manera u otra.

  2. ¿Qué tipo de funcionalidad no tienen las flechas? He leído que la diferencia tiene que ver con la composición, entonces, ¿qué nos permite el operador >>> que >> >> no haga?
    De hecho, >>= permite hacer más de >>> (más capacidad suministrada por la interfaz). Te permite cambiar de contexto. Esto es porque Monad m => a -> mb es una función, por lo que puede ejecutar código puro arbitrario en la entrada a antes de decidir qué cosa monádica ejecutar, mientras que Arrow m => mab no es una función, y usted ha decidió qué cosa de flecha se ejecutará antes de examinar la entrada a .

    monadSwitch :: Monad m => m a -> m a -> (Bool -> m a) monadSwitch computation1 computation2 test = if test then computation1 else computation2

    No es posible simular esto usando Arrow sin usar la app de ArrowApply

  3. ¿Qué hace la aplicación exactamente? su tipo ni siquiera tiene un (->)
    Le permite usar la salida de una flecha como una flecha. Veamos el tipo.

    app :: ArrowApply m => m (m b c, b) c

    Prefiero usar m a a porque m parece más a un cálculo y se siente como un valor. A algunas personas les gusta usar un operador de tipo (constructor tipo infijo), por lo que obtienes

    app :: ArrowApply (~>) => (b ~> c, b) ~> c

    Pensamos en b ~> c como una flecha, y pensamos en una flecha como una cosa que toma b s, hace algo y da c s. Entonces, esto significa que la app es una flecha que toma una flecha y un valor, y puede producir el valor que la primera flecha habría producido en esa entrada.

    No tiene -> en la firma de tipo porque al programar con flechas, podemos convertir cualquier función en una flecha usando arr :: Arrow (~>) => (b -> c) -> b ~> c , pero no se puede convertir cada flecha en una función, así (b ~> c, b) ~> c es utilizable donde (b ~> c, b) -> c o (b -> c, b) ~> c No ser.

    Podemos crear fácilmente una flecha que produzca una flecha o incluso varias flechas, incluso sin ArrowApply, solo haciendo produceArrow :: Arrow (~>) => (b ~> c) -> (any ~> (b ~> c)) definido con produceArrow a = arr (const a) . La dificultad está en hacer que la flecha funcione: ¿cómo lograr que una flecha que produjese sea la siguiente? No puede mostrarlo como el siguiente cálculo usando >>> como lo puede hacer con una función monádica Monad m => a -> mb (simplemente haga id :: ma -> ma !), Porque, de manera crucial, las flechas aren ''t funciona, pero al usar la app , podemos hacer que la flecha siguiente haga lo que haya hecho la flecha producida por la flecha anterior.

    Por lo tanto, ArrowApply le ofrece la capacidad de ejecución generada en tiempo de ejecución que tiene de Monad.

  4. ¿Por qué querríamos usar flechas aplicativas sobre mónadas?
    Er, ¿te refieres a Flechas o Funcionadores Aplicativos? Los funtores aplicativos son geniales. Son más generales que Monad o Arrow (ver el documento) por lo que tienen menos funcionalidad especificada por la interfaz, pero son más ampliamente aplicables (¿es aplicable? / Aplicativo chortle chortle lol rofl category theory humor jajajaja).

    Los funtores aplicativos tienen una sintaxis encantadora que se parece mucho a la aplicación de función pura. f <$> ma <*> mb <*> mc ejecuta ma luego mb luego mc y aplica la función pura f a los tres resultados. Por ejemplo. (+) <$> readLn <*> readLn lee dos enteros del usuario y los agrega.

    Puede usar Applicative para obtener la generalidad, y puede usar Monads para obtener la funcionalidad de interfaz, por lo que podría argumentar que, teóricamente, no los necesitamos, pero a algunas personas les gusta la notación de flechas porque es como notación de notación, y de hecho, puede usar Arrow para implementar analizadores sintácticos que tengan un componente estático, y así aplicar optimizaciones en tiempo de compilación. Creo que puedes hacer eso con Applicative, pero primero se hizo con Arrow.

    Una nota acerca de que Applicative es "menos poderoso":
    El documento señala que Applicative es más general que Monad , pero podría hacer que los funtores Applicative tengan las mismas habilidades al proporcionar una función run :: Applicative f => f (fb) -> fb que le permite ejecutar un cálculo producido, o use :: Applicative f => f (a -> fb) -> fa -> fb que le permite promover un cálculo producido a un cálculo. Si definimos join = run y unit = (<$>) obtenemos las dos funciones que hacen una base teórica para las mónadas, y si definimos (>>=) = flip (use.pure) y return = unit obtenemos el otro que se usa en Haskell. No hay una clase ApplicativeRun , simplemente porque si puedes hacer eso, puedes hacer una mónada, y las firmas de tipo son casi idénticas. La única razón por la que tenemos ArrowApply lugar de reutilizar Monad es porque los tipos no son idénticos; ~> se abstrae (se generaliza) en la interfaz en ArrowApply, pero la aplicación de función -> se usa directamente en Monad. Esta distinción es lo que hace que la programación con Arrows se sienta diferente en muchos sentidos a la programación en mónadas, a pesar de la equivalencia de ArrowApply y Monad.

  5. <tos> ¿Por qué querríamos usar Arrows / ArrowApply sobre Monad?
    De acuerdo, admito que sabía que eso era lo que querías decir, pero quería hablar sobre funtores Aplicativos y me dejé llevar. ¡Olvidé responder!

    Razones de la capacidad: Sí, desearía utilizar Arrow sobre Monad si tuviera algo que no se pueda convertir en una mónada. El ejemplo motivador que nos trajo Arrows en primer lugar fueron los analizadores sintácticos: puede usar Arrow para escribir una biblioteca de analizadores que realiza análisis estáticos en los combinadores, lo que hace que los analizadores sean más eficientes. Los analizadores Monadic anteriores no pueden hacer esto porque representan un analizador como una función, que puede hacer cosas arbitrarias a la entrada sin registrarlas estáticamente, por lo que no puede analizarlas en tiempo de compilación / tiempo de combinación.

    Razones sintácticas: No, personalmente no me gustaría utilizar analizadores basados ​​en Flechas, porque no me gusta la notación de flecha proc / do . Encuentro que es incluso peor que la notación monádica. Mi notación preferida para los analizadores sintácticos es Aplicativa, y es posible que pueda escribir una biblioteca de analizador aplicativo que haga el análisis estático eficiente que hace Arrow, aunque admito que las bibliotecas de analizadores que utilizo habitualmente no lo hacen, posiblemente porque lo desean. para suministrar una interfaz Monadic.

    • Monada:

      parseTerm = do x <- parseSubterm o <- parseOperator y <- parseSubterm return $ Term x o y

    • Flecha:

      parseTerm = proc _ -> do x <- parseSubterm -< () o <- parseOperator -< () y <- parseSubterm -< () returnA -< Term x o y

    • Aplicativo:

      parseTerm = Term <$> parseSubterm <*> parseOperator <*> parseSubterm

      Eso simplemente parece una aplicación de función usando $ unas cuantas veces. Mmmmm. Ordenado. Claro. Baja sintaxis Me recuerda por qué prefiero Haskell a cualquier lenguaje de programación imperativo.

¿Por qué la aplicación en ArrowApply hace una Mónada?

Hay una instancia de Monad en la sección ArrowApply del módulo Control.Arrow , y voy a editar en (~>) lugar de a para mi claridad de pensamiento. (Dejé Functor porque es tonto definir Monad sin Functor de todos modos, debes definir fmap f xs = xs >>= return . f ):

newtype ArrowMonad (~>) b = ArrowMonad (() ~> b) instance Arrow (~>) => Functor (ArrowMonad (~>)) where fmap f (ArrowMonad m) = ArrowMonad $ m >>> arr f instance ArrowApply (~>) => Monad (ArrowMonad (~>)) where return x = ArrowMonad (arr (/_ -> x)) ArrowMonad m >>= f = ArrowMonad $ m >>> arr (/x -> let ArrowMonad h = f x in (h, ())) >>> app

¿Qué hace eso? Bueno, primero, ArrowMonad es un newtype lugar de un sinónimo de tipo solo para que podamos hacer la instancia sin todo tipo de desagradables problemas de sistema de tipo, pero vamos a ignorar eso para obtener claridad conceptual sobre la compibilidad al sustituirla como si fuera type ArrowMonad (~>) b = () ~> b

instance Arrow (~>) => Functor (() ~>) where fmap f m = m >>> arr f

(utilizando una sección de operador de tipo no compilable (()~>) como constructor de tipo)

instance ArrowApply (~>) => Monad (() ~>) where -- return :: b -> (() ~> b) return x = arr (/_ -> x) -- (>>=) :: ()~>a -> (a -> ()~>b ) -> ()~>b m >>= f = m >>> arr (/x -> (f x, ()) ) >>> app

OK, eso está un poco más claro de lo que está pasando. Observe primero que la correspondencia entre flechas y mónadas es entre Monad m => b -> mc y Arrow (~>) => b ~> c , pero la clase mónada no involucra la b en la declaración. Es por eso que necesitamos suministrar el valor ficticio () en () ~> b para que todo comience con entrada cero y replicar algo de tipo mb .

  • El equivalente de fmap donde aplica una función a su salida, es solo producir la salida, luego ejecutar la función en forma de flecha: fmap fm = m >>> arr f
  • El equivalente de return (que solo produce el valor especificado x ) es simplemente ejecutar la función const x en forma de flecha, por lo tanto, return x = arr (/_ -> x) .
  • El equivalente de bind >>= , que ejecuta un cálculo y luego usa la salida como la entrada a una función f que luego puede calcular el siguiente cálculo para ejecutar es: Primero m >>> ejecuta el primer cálculo m , luego arr (/x -> (fx, .... con la salida, aplique la función f , luego use esa flecha como entrada a la app que se comporta como si fuera la flecha emitida que actúa sobre la entrada suministrada () como siempre. ¡Aseado!

Así que dividiré mi pregunta en 4 partes, pero primero algunos antecedentes:

Me siento relativamente cómodo con las Mónadas, pero no muy cómodo con Arrows. Supongo que el principal problema que tengo con ellos es que no veo para qué sirven. Independientemente de que sea o no formalmente correcto, entiendo que las mónadas son una herramienta que nos permite introducir efectos colaterales a partir del cálculo. A medida que generalizan fragmentos de programa de valores puros a valores encuadrados con otras acciones. Desde mi enfoque de "leer todos los papeles" para aprender sobre las flechas, me he encontrado con dos puntos de vista conflictivos:

R. Las flechas son más poderosas que las Mónadas / son generalizaciones de Mónadas. La wiki de haskell comienza con "Pueden hacer todo lo que las mónadas pueden hacer, y más. Son más o menos comparables a las mónadas con un componente estático".

B. Las flechas son un subconjunto de Mónadas con ArrowApply podemos definir una mónada

  1. ¿Hay algo de verdad en el punto de vista A?
  2. ¿Qué tipo de funcionalidad no tienen las flechas? He leído que la diferencia tiene que ver con la composición, entonces, ¿qué nos permite el operador >>> que >> >> no haga?
  3. ¿Qué hace la aplicación exactamente? su tipo ni siquiera tiene un (->)
  4. ¿Por qué querríamos utilizar flechas aplicativas sobre mónadas?

El punto de vista A es un poco extraño: en términos generales, una abstracción no será más poderosa y más general que cualquier otra abstracción; los dos están en desacuerdo. Tener "más poder" significa saber más sobre la estructura de lo que está trabajando, lo que significa más restricciones. En un extremo, sabes exactamente con qué tipo estás trabajando. Esto es extremadamente poderoso; puedes aplicarle cualquier función válida. Por otro lado, tampoco es general: el código escrito con esta suposición solo se aplica a ese tipo. En el otro extremo, no puede saber nada sobre su tipo (por ejemplo, tener una variable de tipo a ). Esto es muy general, se aplica a todos los tipos, pero tampoco es poderoso en absoluto, ¡ya que no tienes suficiente información para nada!

Un ejemplo más enraizado en el código real es la diferencia entre Functor y Applicative . Aquí, Functor es más general: estrictamente más tipos son Functor que Applicative , ya que cada Applicative también es un Functor pero no viceversa. Sin embargo, dado que Applicative tiene más estructura, es estrictamente más poderosa. Con Functor , solo puede asignar funciones de argumento único sobre su tipo; con Applicative , puede asignar funciones de cualquier cantidad de argumentos. De nuevo: uno es más general, el otro más poderoso.

Entonces, ¿cuál es? ¿Las flechas son más poderosas o más generales que las mónadas? Esta es una pregunta más difícil que comparar funtores, funcionadoras aplicativas y mónadas porque las flechas son una bestia muy diferente. Incluso tienen un tipo diferente: monads et al tienen kind * -> * donde las flechas tienen kind * -> * -> * . Afortunadamente, resulta que podemos identificar flechas con functors / mónadas aplicativos, por lo que podemos responder a esta pregunta de manera significativa: las flechas son más generales que las mónadas y, en consecuencia, menos poderosas. Dada una mónada, podemos construir una flecha, pero no podemos construir una mónada para cada flecha.

La idea básica es la siguiente:

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

Sin embargo, dado que tenemos una instancia de flecha para a -> b , tenemos que ajustar a -> mb en un newtype en código real. Este newtype se llama Klesli (debido a las categorías de Klesli ).

Sin embargo, no podemos ir por el otro lado: no hay una construcción para obtener una Monad de ninguna Arrow . Esto sucede porque un cálculo de Arrow no puede cambiar su estructura en función de los valores que fluyen a través de él, mientras que las mónadas pueden hacerlo. La única forma de evitar esto es agregar potencia a la abstracción de tu flecha con alguna función primitiva adicional; esto es exactamente lo que hace ArrowApply .

El operador >>> para flechas es una generalización de . para funciones, y también tiene las mismas restricciones generales. >>= , por otro lado, es más como una generalización de la aplicación de función. Tenga en cuenta los tipos: para >>> , ambos lados son flechas; para >>= , el primer argumento es un valor ( ma ) y el segundo una función. Además, el resultado de >>> es otra flecha donde el resultado de >>= es un valor. Como las flechas solo tienen >>> pero ninguna noción equivalente a >>= , no puede "aplicarlas" a argumentos en general; solo puede construir tuberías de flecha. La función de aplicación / ejecución real debería ser específica para cualquier flecha dada. Las mónadas, por otro lado, se definen en términos de >>= y, por lo tanto, vienen con alguna noción de aplicación por defecto.

ArrowApply simplemente extiende flechas con la app , que es una noción general de aplicación. Imaginemos la aplicación de la función normal:

apply :: (b -> c) -> b -> c apply f x = f x

podemos desatar esto para obtener:

apply :: ((b -> c), b) -> c

La manera en que las flechas generalizan las funciones es básicamente reemplazando -> con una variable ( a ). Hagamos esto para apply reemplazando ambas ocurrencias de -> con un infijo a :

apply :: (b `a` c, b) `a` c

Todavía podemos ver la misma estructura que la primera versión de apply , simplemente no ejecutada y con `a` lugar de -> . Ahora si nos deshacemos de los backticks y hacemos a prefijo, obtenemos la firma de la app :

app :: a (a b c, b) c

Entonces, vemos cómo ArrowApply simplemente agrega alguna noción de aplicación a las flechas. Este es un prallel a >>= , que es una noción de aplicación para mónadas (o, en particular, funciones de la forma a -> mb ). Esta es suficiente estructura adicional para construir una mónada desde una flecha, por lo que ArrowApply es isomorfo para Monad .

¿Por qué querríamos usar estos? Honestamente, no creo que lo hagamos. Las flechas están bastante sobrevaloradas, así que mantente en las mónadas y los funtores aplicativos.