haskell - Las flechas son exactamente equivalentes a los funtores aplicativos?

applicative arrows

Question

Según el famoso documento, los modismos son ajenos, las flechas son meticulosas, las mónadas son promiscuas , el poder expresivo de las flechas (sin ninguna clase de tipos adicional) debe estar en algún lugar estrictamente entre funcionadores y mónadas aplicativos: las mónadas son equivalentes a ArrowApply , y Applicative debería ser equivalente a algo que el periódico llama "flechas estáticas". Sin embargo, no me queda claro qué restricción significa esta "estática".

Jugando con las tres clases de tipos en cuestión, pude construir una equivalencia entre functors aplicativos y flechas, que presento a continuación en el contexto de la conocida equivalencia entre ArrowApply y ArrowApply . ¿Es esta construcción correcta? (He probado la mayoría de las leyes de flechas antes de aburrirme de ellas). ¿Eso no significa que Arrow y Applicative son exactamente iguales?

{-# LANGUAGE TupleSections, NoImplicitPrelude #-}
import Prelude (($), const, uncurry)

-- In the red corner, we have arrows, from the land of * -> * -> *
import Control.Category
import Control.Arrow hiding (Kleisli)

-- In the blue corner, we have applicative functors and monads,
-- the pride of * -> *
import Control.Applicative
import Control.Monad

-- Recall the well-known result that every monad yields an ArrowApply:
newtype Kleisli m a b = Kleisli{ runKleisli :: a -> m b}

instance (Monad m) => Category (Kleisli m) where
    id = Kleisli return
    Kleisli g . Kleisli f = Kleisli $ g <=< f

instance (Monad m) => Arrow (Kleisli m) where
    arr = Kleisli . (return .)
    first (Kleisli f) = Kleisli $ /(x, y) -> liftM (,y) (f x)

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

-- Every arrow arr can be turned into an applicative functor
-- for any choice of origin o
newtype Arrplicative arr o a = Arrplicative{ runArrplicative :: arr o a }

instance (Arrow arr) => Functor (Arrplicative arr o) where
    fmap f = Arrplicative . (arr f .) . runArrplicative

instance (Arrow arr) => Applicative (Arrplicative arr o) where
    pure = Arrplicative . arr . const

    Arrplicative af <*> Arrplicative ax = Arrplicative $
        arr (uncurry ($)) . (af &&& ax)

-- Arrplicatives over ArrowApply are monads, even
instance (ArrowApply arr) => Monad (Arrplicative arr o) where
    return = pure
    Arrplicative ax >>= f =
        Arrplicative $ (ax >>> arr (runArrplicative . f)) &&& id >>> app

-- Every applicative functor f can be turned into an arrow??
newtype Applicarrow f a b = Applicarrow{ runApplicarrow :: f (a -> b) }

instance (Applicative f) => Category (Applicarrow f) where
    id = Applicarrow $ pure id
    Applicarrow g . Applicarrow f = Applicarrow $ (.) <$> g <*> f

instance (Applicative f) => Arrow (Applicarrow f) where
    arr = Applicarrow . pure
    first (Applicarrow f) = Applicarrow $ first <$> f

Answer 1

(He publicado lo siguiente en mi blog con una introducción ampliada)

Tom Ellis sugirió que se piense en un ejemplo concreto de E / S de archivos, así que comparemos tres enfoques con las tres clases de tipos. Para simplificar, solo nos importan dos operaciones: leer una cadena de un archivo y escribir una cadena en un archivo. Los archivos se identificarán por su ruta de archivo:

type FilePath = String

E / S monádica

Nuestra primera interfaz de E / S se define de la siguiente manera:

data IOM ∷ ⋆ → ⋆
instance Monad IOM
readFile ∷ FilePath → IOM String
writeFile ∷ FilePath → String → IOM ()

Usando esta interfaz, podemos, por ejemplo, copiar un archivo de una ruta a otra:

copy ∷ FilePath → FilePath → IOM ()
copy from to = readFile from >>= writeFile to

Sin embargo, podemos hacer mucho más que eso: la elección de los archivos que manipulamos puede depender de los efectos en sentido ascendente. Por ejemplo, la función siguiente toma un archivo de índice que contiene un nombre de archivo y lo copia al directorio de destino dado:

copyIndirect ∷ FilePath → FilePath → IOM ()
copyIndirect index target = do
    from ← readFile index
    copy from (target ⟨/⟩ to)

Por otro lado, esto significa que no hay forma de saber por adelantado el conjunto de nombres de archivo que van a ser manipulados por una action ∷ IOM α valor dada action ∷ IOM α . Por "inicial", lo que quiero decir es la capacidad de escribir un fileNames :: IOM α → [FilePath] función fileNames :: IOM α → [FilePath] .

Por supuesto, para mónadas no basadas en IO (como aquellas para las que tenemos algún tipo de función de extractor μ α → α ), esta distinción se vuelve un poco más borrosa, pero aún tiene sentido pensar en intentar extraer información sin evaluar los efectos de la mónada (por ejemplo, podríamos preguntar "¿qué podemos saber sobre un Reader Γ α sin tener un valor de tipo Γ a mano?").

La razón por la que realmente no podemos hacer un análisis estático en este sentido en las mónadas es porque la función en el lado derecho de un enlace está en el espacio de las funciones de Haskell, y como tal, es completamente opaca.

Intentemos restringir nuestra interfaz a solo un funcionador aplicativo.

E / S aplicable

data IOF ∷ ⋆ → ⋆
instance Applicative IOF
readFile ∷ FilePath → IOF String
writeFile ∷ FilePath → String → IOF ()

Dado que IOF no es una mónada, no hay forma de componer readFile y writeFile , por lo que todo lo que podemos hacer con esta interfaz es leer un archivo y luego procesar su contenido puramente o escribir en un archivo; pero no hay forma de escribir el contenido de un archivo en otro.

¿Qué hay de cambiar el tipo de writeFile ?

writeFile′ ∷ FilePath → IOF (String → ())

El principal problema con esta interfaz es que, si bien permitiría escribir algo así como

copy ∷ FilePath → FilePath → IOF ()
copy from to = writeFile′ to ⟨*⟩ readFile from

conduce a todo tipo de problemas desagradables porque String → () es un modelo tan horrible de escribir una cadena en un archivo, ya que rompe la transparencia referencial. Por ejemplo, ¿qué esperas que sea el contenido de out.txt después de ejecutar este programa?

(λ write → [write "foo", write "bar", write "foo"]) ⟨$⟩ writeFile′ "out.txt"

Dos enfoques para I / O flechada

En primer lugar, Applicarrow IOF camino dos interfaces de E / S basadas en flechas que no (de hecho, no pueden) traer algo nuevo a la mesa: Kleisli IOM y Applicarrow IOF .

La Kleisli-arrow de IOM , módulo currying, es:

readFile ∷ Kleisli IOM FilePath String
writeFile ∷ Kleisli IOM (FilePath, String) ()

Como la entrada de writeFile todavía contiene tanto el nombre de archivo como el contenido, aún podemos escribir copyIndirect (usando la notación de flecha para simplificar). Observe cómo la instancia de ArrowApply de Kleisli IOM ni siquiera se usa.

copyIndirect ∷ Kleisli IOM (FilePath, FilePath) ()
copyIndirect = proc (index, target) → do
    from ← readFile ↢ index
    s ← readFile ↢ from
    writeFile ↢ (to, s)

El Applicarrow de IOF sería:

readFile ∷ FilePath → Applicarrow IOF () String
writeFile ∷ FilePath → String → Applicarrow IOF () ()

que, por supuesto, todavía presenta el mismo problema de no poder readFile y writeFile .

Una interfaz de E / S con flecha apropiada

En lugar de transformar IOM o IOF en una flecha, ¿qué IOF si comenzamos desde cero y tratamos de crear algo intermedio, en términos de dónde usamos las funciones de Haskell y dónde hacemos una flecha? Tome la siguiente interfaz:

data IOA ∷ ⋆ → ⋆ → ⋆
instance Arrow IOA
readFile ∷ FilePath → IOA () String
writeFile ∷ FilePath → IOA String ()

Como writeFile toma el contenido del lado de entrada de la flecha, aún podemos implementar copy :

copy ∷ FilePath → FilePath → IOA () ()
copy from to = readFile from >>> writeFile to

Sin embargo, el otro argumento de writeFile es puramente funcional, por lo que no puede depender del resultado de, por ejemplo, readFile ; por lo que copyIndirect no se puede implementar con esta interfaz de flecha.

Si cambiamos este argumento, esto también significa que, si bien no podemos saber de antemano, lo que terminará escribiéndose en un archivo (antes de ejecutar la canalización completa de IOA ), pero podemos determinar de manera estática el conjunto de nombres de archivos que serán modificado.

Conclusión

Las mónadas son opacas al análisis estático, y los funtores aplicativos son pobres para expresar dependencias de datos de tiempo dinámico. Resulta que las flechas pueden proporcionar un punto dulce entre los dos: al elegir las entradas puramente funcionales y las flechas con cuidado, es posible crear una interfaz que permita la interacción correcta del comportamiento dinámico y la susceptibilidad al análisis estático.

Answer 2

Cada aplicativo arroja una flecha y cada flecha produce un aplicativo, pero no son equivalentes. Si tienes una flecha arr y un morphism arr ab , no se sigue que puedas generar un morphism arr o (a /to b) que replique su funcionalidad. Por lo tanto, si realiza un viaje de ida y vuelta a través del aplicativo, perderá algunas características.

Los solicitantes son funtores monoidales. Las flechas son profuntores que también son categorías, o equivalentemente, monoides en la categoría de monstruores. No existe una conexión natural entre estas dos nociones. Si excusas mi ligereza: en Hask resulta que la parte funcionadora del pro-functor en una flecha es un funcionador monoidal, pero esa construcción necesariamente olvida la parte "pro".

Cuando pasa de las flechas a los aplicativos, está ignorando la parte de una flecha que toma la entrada y solo utiliza la parte que trata con la salida. Muchas flechas interesantes usan la parte de entrada de una forma u otra y, por lo tanto, al convertirlas en aplicaciones, estás renunciando a cosas útiles.

Dicho esto, en la práctica encuentro aplicativo la abstracción más agradable para trabajar y una que casi siempre hace lo que quiero. En teoría, las flechas son más potentes, pero no creo que las use en la práctica.

Answer 3

Comparemos el functor aplicativo IO con las flechas Kleisli de la mónada IO.

Puede tener una flecha que imprime un valor leído por una flecha anterior:

runKleisli ((Kleisli $ /() -> getLine) >>> Kleisli putStrLn) ()

Pero no puedes hacer eso con funtores aplicativos. Con los funtores aplicativos, todos los efectos tienen lugar antes de aplicar la función-en-el-functor a los argumentos-en-el-functor. La función-en-el-functor no puede usar el valor dentro de un argumento-en-el-objeto para "modular" su propio efecto, por así decirlo.