haskell - Construcciones de computación(mónadas, flechas, etc.)

monads arrows

Question

Me he interesado bastante en cómo se modela la computación en Haskell. Varios recursos han descrito las mónadas como "cómputo composable" y las flechas como "vistas abstractas de cómputo". Nunca he visto monoides, funtores o funtores aplicativos descritos de esta manera. Parece que les falta la estructura necesaria.

Encuentro esa idea interesante y me pregunto si hay otras construcciones que hagan algo similar. Si es así, ¿cuáles son algunos recursos que puedo usar para familiarizarme con ellos? ¿Hay algún paquete en Hackage que pueda ser útil?

Nota: esta pregunta es similar a Monads vs. Arrows y https://stackoverflow.com/questions/2395715/resources-for-learning-monads-functors-monoids-arrows-etc , pero estoy buscando construcciones más allá de los funtors, aplicativo Funtores, mónadas y flechas.

Edit: Admito que los funtores aplicativos deben considerarse como "construcciones computacionales", pero realmente estoy buscando algo que no haya encontrado todavía. Esto incluye funtores aplicativos, mónadas y flechas.

Answer 1

En las bibliotecas estas estructuras dan lugar a diferentes tipos de cálculos.

Por ejemplo, los aplicativos se pueden utilizar para implementar efectos estáticos. Con eso me refiero a los efectos, que se definen de antemano. Por ejemplo, al implementar una máquina de estado, rechazar o aceptar un estado de entrada. No se pueden utilizar para manipular su estructura interna en términos de sus aportaciones.

El tipo lo dice todo:

 <*> :: f (a -> b) -> f a -> f b

Es fácil de razonar, la estructura de f no puede depender de la entrada de a. Porque a no se puede llegar f en el nivel de tipo.

Las mónadas se pueden utilizar para efectos dinámicos. Esto también se puede razonar a partir de la firma de tipo:

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

¿Cómo puedes ver esto? Porque a está en el mismo "nivel" que m. Matemáticamente es un proceso de dos etapas. Bind es una composición de dos funciones: fmap y join. Primero usamos fmap junto con la acción monádica para crear una nueva estructura incrustada en la anterior:

fmap :: (a -> b) -> m a -> m b
f :: (a -> m b)
m :: m a
fmap f :: m a -> m (m b)
fmap f m :: m (m b)

Fmap puede crear una nueva estructura, basada en el valor de entrada. Luego colapsamos la estructura con la combinación, por lo que podemos manipular la estructura desde el cómputo monádico de una manera que depende de la entrada:

join :: m (m a) -> m a
join (fmap f m) :: m b

Muchas mónadas son más fáciles de implementar con join:

(>>=) = join . fmap 

Esto es posible con las mónadas:

addCounter :: Int -> m Int () 

Pero no con los aplicativos, pero los aplicativos (y cualquier mónada) pueden hacer cosas como:

addOne :: m Int ()

Las flechas dan más control sobre la entrada y los tipos de salida, pero para mí realmente se sienten similares a los aplicativos. Tal vez estoy equivocado sobre eso.

Answer 2

Todas las mónadas son flechas (la mónada es isomorfa a ArrowApply). De una manera diferente, todas las mónadas son instancias de Applicative , donde <*> es Control.Monad.ap y *> is >> . El aplicativo es más débil porque no garantiza la operación >>= . Por lo tanto, Applicative captura cálculos que no examinan resultados anteriores y se ramifican en valores. En retrospectiva, mucho código monádico es en realidad aplicativo, y con una reescritura limpia, esto sucedería.

Ampliación de mónadas, con tipos de Restricción recientes en GHC 7.4.1 ahora puede haber diseños más agradables para mónadas restringidas . Y también hay personas que miran las mónadas parametrizadas y, por supuesto, incluyo un enlace a algo de Oleg .

Answer 3

Arrows se generalizan por Categorías y, por lo tanto, por la Category typeclass.

 class Category f where
(.) :: f a b -> f b c -> f a c
id :: f a a

La definición de la clase de tipos de Arrow tiene Category como superclase. Las categorías (en el sentido de haskell) generalizan las funciones (puede componerlas pero no aplicarlas) y, por lo tanto, son definitivamente un "modelo de cálculo". Arrow proporciona una Category con estructura adicional para trabajar con tuplas. Entonces, mientras la Category refleja algo sobre el espacio funcional de Haskell, Arrow extiende a algo sobre los tipos de productos.

Cada Monad da lugar a algo llamado "Categoría Kleisli" y esta construcción le da instancias de ArrowApply . Puedes construir una Monad partir de cualquier ArrowApply de ArrowApply manera que ir en un círculo completo no cambie tu comportamiento, por lo que, en un sentido profundo, la Monad y la ArrowApply son lo mismo.

 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))

En realidad, cada Arrow da lugar a un Applicative (cuantificado universalmente para obtener los tipos correctos) además de la Superclase de Category , y creo que la combinación de la Category apropiada y el Applicative es suficiente para reconstruir su Arrow .

Entonces, estas estructuras están profundamente conectadas.

Advertencia: comentario insípido por delante . Una diferencia central entre la forma de pensar de Functor / Applicative / Monad forma de pensar de Category / Arrow es que mientras que Functor y su ilk son generalizaciones en el nivel del objeto (tipos en Haskell), Category / Arrow es una referencia a la noción de morfismo (funciones en haskell). Mi creencia es que pensar al nivel del morfismo generalizado implica un nivel más alto de abstracción que pensar al nivel de los objetos generalizados. A veces eso es algo bueno, otras veces no lo es. Por otro lado, a pesar del hecho de que las Arrows tienen una base categórica, y nadie en matemáticas piensa que el Applicative es interesante, entiendo que el Applicative generalmente se entiende mejor que Arrow .

Básicamente, puede pensar en "Categoría <Flecha <Aplicación de flecha" y "Functor <Aplicativo <Mónada" de tal manera que "Categoría ~ Función", "Flecha ~ Aplicativo" y "Flecha de aplicación ~ Mónada".

Más concreto a continuación: En cuanto a otras estructuras para modelar la computación: a menudo se puede invertir la dirección de las "flechas" (que significa morfismos aquí) en las construcciones categóricas para obtener el "dual" o la "construcción conjunta". Entonces, si una mónada se define como

class Functor m => Monad m where
return :: a -> m a
join :: m (m a) -> m a

(bueno, sé que no es así como Haskell define las cosas, pero ma >>= f = join $ fmap f ma y join x = x >>= id por lo que podría serlo) entonces comonad es

class Functor m => Comonad m where
extract :: m a -> a -- this is co-return
duplicate :: m a -> m (m a) -- this is co-join

Esta cosa resulta ser bastante común también. Resulta que Comonad es la estructura básica subyacente de los autómatas celulares . Para completar, debo señalar que Control.Comonad Edward Kmett coloca el duplicate en una clase entre functor y Comonad para "Functors extensibles" porque también puede definir

 extend :: (m a -> b) -> m a -> m b -- Looks familiar? this is just the dual of >>=
extend f = fmap f . duplicate
--this is enough
duplicate = extend id

Resulta que todas las Monad son también "extensibles"

 monadDuplicate :: Monad m => m a -> m (m a)
monadDuplicate = return

mientras que todos los Comonads son "Joables"

 comonadJoin :: Comonad m => m (m a) -> m a
comonadJoin = extract

Así que estas estructuras están muy juntas.