haskell - Construcciones de computación(mónadas, flechas, etc.)
monads arrows (3)
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.
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.
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 .
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.