Construcciones de cálculo (Mónadas, Flechas, etc.)

Question

Me he interesado bastante en cómo se modela el cálculo en Haskell. Varios recursos han descrito las mónadas como "computación composable" y las flechas como "vistas abstractas de computación". Nunca he visto monoácidos, funtores o funcionadores aplicativos descritos de esta manera. Parece que carecen de la estructura necesaria.

Me parece interesante esta idea 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 en busca de construcciones más allá funtors, funtores aplicativos, mónadas, y las flechas.

Editar: que admiten que los funtores aplicativos deben ser considerados como "construcciones computacionales", pero estoy realmente en busca de algo que no he encontrado todavía. Esto incluye functors aplicativos, mónadas y flechas.

Answer 1

Arrows están generalizados por Categorías, y por lo tanto por la clase de tipo Category.

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

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

Cada Monad da lugar a algo llamado "Categoría Kleisli" y esta construcción le da instancias de ArrowApply. Puede construir un Monad de cualquiera de los ArrowApply de manera que al completar el círculo no cambie su comportamiento, por lo que en un sentido profundo Monad y 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 todos los Arrow da lugar a una Applicative (cuantificada universalmente para obtener el tipo correcto), además de los Category superclase, y creo que la combinación apropiada de la Category y Applicative es suficiente para reconstruir su Arrow.

Por lo tanto, estas estructuras están profundamente conectadas.

Advertencia: comentario quisquilloso delante. Una diferencia central entre el camino Functor/Applicative/Monad de pensar y la forma Category/Arrow de pensar es que mientras Functor y su clase son generalizaciones a nivel de objeto (tipos en Haskell), Category/Arrow son generelazation de la noción de morfismo (funciones en Haskell). Mi creencia es que pensar en el nivel generalizado de morfismo implica un mayor nivel de abstracción que pensar en el 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 Arrows tiene una base categórica, y nadie en matemáticas piensa que Applicative es interesante, entiendo que Applicative se entiende mejor que Applicative generalmente se entiende mejor que Arrow.

Básicamente se puede pensar en "Categoría < Flecha < ArrowApply" y "Functor < Aplicativo < mónada" tal que "Categoría Functor ~", "Flecha ~ Aplicativo" y "ArrowApply ~ mónada".

más concreto continuación: En cuanto a otras estructuras para modelar cálculo: a menudo se puede invertir el sentido de las "flechas" (solo significa morfismos aquí) en las construcciones categóricas para obtener el "doble" o "co-construcción ". Por lo tanto, si una mónada se define como

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

(bien, sé que no es así como Haskell define cosas, pero ma >>= f = join $ fmap f ma y join x = x >>= id por lo que sólo así podía ser) entonces el 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 

Esto también es bastante común. Resulta que Comonad es la estructura subyacente básica de autómata celular. Por completitud, debo señalar que de Edward Kmett Control.Comonad pone duplicate en una clase entre funtor y Comonad para "extensibles Functors" porque también se pueden 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 todos Monad s también son "extensible"

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

mientras que todos Comonads son "acoplable"

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

por lo

estas estructuras están muy juntas.

Answer 2

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

Mónadas extendidas, con clases de Restricción recientes en GHC 7.4.1 ahora puede haber diseños más agradables para restricted monads. Y también hay personas mirando parameterized monads, y por supuesto incluyo un enlace a algo por Oleg.

Answer 3

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

Por ejemplo, los aplicadores se pueden utilizar para implementar efectos estáticos. Con eso me refiero a los efectos, que se definen de antemano. Por ejemplo, cuando se implementa una máquina de estado, se rechaza o acepta un estado de entrada. No se pueden usar para manipular su estructura interna en términos de su entrada.

El tipo dice todo:

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

Es fácil razón, la estructura de f no se puede depender de om la entrada de una. Porque a no puede alcanzar f en el nivel de tipo.

Las mónadas se pueden usar para efectos dinámicos. Esto también se puede razonar con el tipo de firma:

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

¿Cómo se puede 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ádico 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 colapsar la estructura con unirse, por lo tanto somos capaces de manipular la estructura del interior de la computación monádica de una manera que depende de la entrada:

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

Muchos mónadas son más fáciles de implementar con Ingreso:

(>>=) = join . fmap 

Esto es posible con mónadas:

addCounter :: Int -> m Int() 

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

addOne :: m Int() 

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