¿Qué son las mónadas libres?

368

He visto el término libre mónada pop-up cada ahora y entonces durante algún tiempo, pero todo el mundo parece utilizar / discutirlas sin dar una explicación de lo que son. Entonces: ¿qué son las mónadas libres? (Diría que estoy familiarizado con las mónadas y los conceptos básicos de Haskell, pero solo tengo un conocimiento muy aproximado de la teoría de categorías).

David
fuente
12
Una explicación bastante buena está aquí haskellforall.com/2012/06/…
Roger Lindsjö
19
@Roger esa es la página que me trajo aquí. Para mí, ese ejemplo define una instancia de mónada para un tipo llamado "Gratis" y eso es todo.
David

Respuestas:

295

La respuesta de Edward Kmett es obviamente genial. Pero, es un poco técnico. Aquí hay una explicación quizás más accesible.

Las mónadas gratuitas son solo una forma general de convertir a los functores en mónadas. Es decir, dado que cualquier functor f Free fes una mónada. Esto no sería muy útil, excepto que obtienes un par de funciones

liftFree :: Functor f => f a -> Free f a
foldFree :: Functor f => (f r -> r) -> Free f r -> r

el primero de estos le permite "entrar" en su mónada, y el segundo le da una forma de "salir" de él.

En términos más generales, si X es una Y con algunas cosas adicionales P, entonces una "X libre" es una forma de pasar de una Y a una X sin ganar nada extra.

Ejemplos: un monoide (X) es un conjunto (Y) con estructura adicional (P) que básicamente dice que tiene una operación (puede pensar en la suma) y cierta identidad (como cero).

Entonces

class Monoid m where
   mempty  :: m
   mappend :: m -> m -> m

Ahora, todos sabemos listas

data [a] = [] | a : [a]

Bueno, dado cualquier tipo t, sabemos que [t]es un monoide

instance Monoid [t] where
  mempty   = []
  mappend = (++)

y entonces las listas son el "monoide libre" sobre conjuntos (o en tipos Haskell).

Bien, entonces las mónadas gratis son la misma idea. Tomamos un functor y devolvemos una mónada. De hecho, dado que las mónadas se pueden ver como monoides en la categoría de endofunctores, la definición de una lista

data [a] = [] | a : [a]

se parece mucho a la definición de mónadas libres

data Free f a = Pure a | Roll (f (Free f a))

y la Monadinstancia tiene una similitud con la Monoidinstancia para listas

--it needs to be a functor
instance Functor f => Functor (Free f) where
  fmap f (Pure a) = Pure (f a)
  fmap f (Roll x) = Roll (fmap (fmap f) x)

--this is the same thing as (++) basically
concatFree :: Functor f => Free f (Free f a) -> Free f a
concatFree (Pure x) = x
concatFree (Roll y) = Roll (fmap concatFree y)

instance Functor f => Monad (Free f) where
  return = Pure -- just like []
  x >>= f = concatFree (fmap f x)  --this is the standard concatMap definition of bind

ahora tenemos nuestras dos operaciones

-- this is essentially the same as \x -> [x]
liftFree :: Functor f => f a -> Free f a
liftFree x = Roll (fmap Pure x)

-- this is essentially the same as folding a list
foldFree :: Functor f => (f r -> r) -> Free f r -> r
foldFree _ (Pure a) = a
foldFree f (Roll x) = f (fmap (foldFree f) x)
Philip JF
fuente
12
Esta puede ser la mejor explicación accesible de "gratis" que he visto. Especialmente el párrafo que comienza con "Más generalmente".
John L
16
Creo que es interesante mirar Free f a = Pure a | Roll (f (Free f a))como Free f a = a + fa + ffa + ..., es decir, "f aplicado a cualquier cantidad de veces". Luego concatFree(es decir join) toma una "f aplicada cualquier cantidad de veces a (f aplicada cualquier cantidad de veces a a)" y contrae las dos aplicaciones anidadas en una. Y >>=toma "f aplicado cualquier número de veces a a" y "cómo llegar de a a (b con f aplicado cualquier número de veces)", y básicamente aplica el último a a dentro del primero y colapsa el anidamiento. ¡Ahora yo mismo lo entiendo!
jkff
1
es concatFreebásicamente join?
rgrinberg
11
“Aquí hay una explicación quizás más accesible. [...] De hecho, dado que las mónadas se pueden ver como monoides en la categoría de endofuncionadores, ... ”Sin embargo, creo que esta es una muy buena respuesta.
Ruud
2
"mónadas pueden ser vistos como monoides en la categoría de funtores endo" <3 (que debe enlazar a stackoverflow.com/a/3870310/1306877 porque cada haskeller debe saber acerca de que la referencia!)
TLO
418

Aquí hay una respuesta aún más simple: una mónada es algo que "computa" cuando se colapsa el contexto monádico join :: m (m a) -> m a(recordando que >>=se puede definir como x >>= y = join (fmap y x)). Así es como las mónadas llevan el contexto a través de una cadena secuencial de cálculos: porque en cada punto de la serie, el contexto de la llamada anterior se contrae con la siguiente.

Una mónada libre satisface todas las leyes de la mónada, pero no colapsa (es decir, el cálculo). Simplemente construye una serie anidada de contextos. El usuario que crea un valor monádico libre es responsable de hacer algo con esos contextos anidados, de modo que el significado de dicha composición pueda diferirse hasta después de que se haya creado el valor monádico.

John Wiegley
fuente
8
Tus párrafos son una gran adición a la publicación de Philip.
David
20
Realmente me gusta esta respuesta.
danidiaz
55
¿Puede la mónada libre reemplazar la clase de tipo Mónada? Es decir, ¿podría escribir un programa utilizando solo el retorno y la vinculación de la mónada libre, y luego unir los resultados usando lo que prefiera de Mwybe o List o lo que sea, o incluso generar múltiples vistas monádicas de una secuencia de llamadas a funciones vinculadas / concatenadas. Ignorando el fondo y la no determinación, eso es.
misterbee
2
Esta respuesta ayudó, pero creo que me habría confundido si no me hubiera reunido para 'unirme' al curso NICTA y haber leído haskellforall.com/2012/06/… . Entonces, para mí, el truco para comprender es leer muchas respuestas hasta que se asimile . (Referencia de la NICTA: github.com/NICTA/course/blob/master/src/Course/Bind.hs )
Martin Capodici
1
esta respuesta es la mejor de todas
Curycu
142

Un foo libre resulta ser lo más simple que satisface todas las leyes de 'foo'. Es decir, satisface exactamente las leyes necesarias para ser un tonto y nada más.

Un functor olvidadizo es aquel que "olvida" parte de la estructura a medida que pasa de una categoría a otra.

Dados functores F : D -> C, y G : C -> D, decimos F -| G, Fse deja adjunto a G, o Ges justo contiguo a Fcada vez que a, b: F a -> bes isomorfo a a -> G b, donde las flechas provienen de las categorías apropiadas.

Formalmente, un functor gratuito se deja adjunto a un functor olvidadizo.

El monoide libre

Comencemos con un ejemplo más simple, el monoide gratuito.

Tome un monoide, que se define por un conjunto de soporte T, una función binaria para triturar un par de elementos juntos f :: T → T → T, y una unit :: T, de manera que usted tiene una ley asociativa, y una ley de identidad: f(unit,x) = x = f(x,unit).

Puede hacer un funtor Ude la categoría de monoides (donde las flechas son homomorfismos monoides, es decir, que aseguran se asignan unita unitpor otro monoide, y que se pueden componer antes o después de la cartografía a la otra monoid sin cambiar el significado) a la categoría de conjuntos (donde las flechas son solo flechas de función) que 'se olvida' de la operación unity solo le da el conjunto de portadores.

Luego, puede definir un functor Fdesde la categoría de conjuntos hasta la categoría de monoides que se adjunta a este functor. Ese functor es el functor que asigna un conjunto aal monoide [a], donde unit = []y mappend = (++).

Entonces, para revisar nuestro ejemplo hasta ahora, en pseudo-Haskell:

U : Mon  Set -- is our forgetful functor
U (a,mappend,mempty) = a

F : Set  Mon -- is our free functor
F a = ([a],(++),[])

Luego, para mostrar Fes gratuito, tenemos que demostrar que se deja adjunto a Uun functor olvidadizo, es decir, como mencionamos anteriormente, tenemos que demostrar que

F a → b es isomorfo a a → U b

Ahora, recuerde que el objetivo de Festá en la categoría Monde monoides, donde las flechas son homomorfismos monoides, por lo que necesitamos un para demostrar que un homomorfismo monoide [a] → bpuede describirse precisamente por una función de a → b.

En Haskell, llamamos al lado de esto que vive en Set(er, Haskla categoría de tipos de Haskell que pretendemos es Set), simplemente foldMap, que cuando se especializa desde Data.Foldablea Listas tiene tipo Monoid m => (a → m) → [a] → m.

Hay consecuencias que se derivan de que esto sea un complemento. Notablemente, si olvidas, entonces construye con gratis, luego vuelve a olvidar, es como lo olvidaste una vez, y podemos usar esto para construir la unión monádica. desde UFUF~ U(FUF)~ UF, y podemos pasar el homomorfismo monoide de identidad de [a]a [a]través del isomorfismo que define nuestro adjunto, hacer que una lista de isomorfismo [a] → [a]sea ​​una función de tipo a -> [a], y esto es solo el retorno para las listas.

Puede componer todo esto más directamente describiendo una lista en estos términos con:

newtype List a = List (forall b. Monoid b => (a -> b) -> b)

La mónada libre

Entonces, ¿qué es una mónada libre ?

Bueno, hacemos lo mismo que hicimos antes, comenzamos con un functor olvidadizo U de la categoría de mónadas donde las flechas son homomorfismos de mónada a una categoría de endofunctores donde las flechas son transformaciones naturales, y buscamos un functor que quede adjunto a ese.

Entonces, ¿cómo se relaciona esto con la noción de una mónada libre como se usa generalmente?

Sabiendo que algo es una mónada libre, Free fte dice que dar un homomorfismo de mónada Free f -> mes lo mismo (isomorfo a) que dar una transformación natural (un homomorfismo functor) f -> m. Recuerde que F a -> bdebe ser isomorfo a -> U bpara que F se quede junto a U. U aquí asigna mónadas a functors.

F es al menos isomorfo al Freetipo que uso en mi freepaquete de piratería.

También podríamos construirlo en una analogía más estricta con el código anterior para la lista gratuita, definiendo

class Algebra f x where
  phi :: f x -> x

newtype Free f a = Free (forall x. Algebra f x => (a -> x) -> x)

Cofree Comonads

Podemos construir algo similar, mirando el adjunto correcto a un functor olvidadizo, suponiendo que exista. Un cofundador es simplemente / justo adjunto / a un olvidadizo, y por simetría, saber que algo es un cofre comonad es lo mismo que saber que dar un comonad homomorfismo w -> Cofree fes lo mismo que dar una transformación natural w -> f.

Edward KMETT
fuente
12
@PauloScardine, esto no es nada que tenga que preocuparse. Mi pregunta surgió del interés por comprender alguna estructura de datos avanzada y tal vez echar un vistazo a lo que está de vanguardia en el desarrollo de Haskell en este momento: de ninguna manera es necesario o representativo de lo que realmente se trata de escribir Haskell hasta ahora. (Y un aviso, mejora una vez que haya pasado la etapa de aprendizaje IO nuevamente)
David
8
@PauloScardine No necesita la respuesta anterior para programar productivamente en Haskell, incluso con mónadas gratuitas. De hecho, no recomendaría atacar a la mónada libre de esta manera a alguien que no tenga experiencia en teoría de categorías. Hay muchas maneras de hablar sobre esto desde una perspectiva operativa y entender cómo usar uno sin sumergirse en la teoría de la categoría. Sin embargo, es imposible para mí responder la pregunta sobre de dónde vienen sin sumergirme en la teoría. Las construcciones gratuitas son una herramienta poderosa en la teoría de categorías, pero no necesita este fondo para usarlas.
Edward KMETT el
18
@PauloScardine: No necesitas exactamente ningún cálculo para utilizar Haskell de manera efectiva e incluso entender lo que estás haciendo. Es un poco extraño quejarse de que "este lenguaje es mathy" cuando el mathyness es simplemente una bondad extra que puedes usar para divertirte y obtener ganancias. No obtienes estas cosas en la mayoría de los idiomas imperativos. ¿Por qué te quejarías de los extras? Simplemente puede elegir NO razonar matemáticamente y abordarlo como lo haría con cualquier otro idioma nuevo.
Sarah
3
@Sarah: Todavía no he visto una pieza de documentación o una conversación del IRC sobre Haskell que no sea pesada en teoría de computadoras y termias de cálculo lambda.
Paulo Scardine el
11
@PauloScardine esto está derivando un poco de OT, pero en defensa de Haskell: cosas técnicas similares se aplican a todos los demás lenguajes de programación, solo que Haskell tiene una compilación tan agradable que la gente realmente puede disfrutar hablando de ellos. Por qué / cómo X es una mónada es interesante para muchas personas, las discusiones sobre el estándar de coma flotante IEEE no lo son; ambos casos no son importantes para la mayoría de las personas, porque solo pueden usar los resultados.
David
72

La mónada libre (estructura de datos) es para la mónada (clase) como la lista (estructura de datos) para el monoide (clase): es la implementación trivial, donde luego puede decidir cómo se combinará el contenido.


Probablemente sepa qué es una mónada y que cada mónada necesita una implementación específica (respetando la ley de mónada) de fmap+ join+ returno bind+ return.

Supongamos que tiene un Functor (una implementación de fmap), pero el resto depende de los valores y las elecciones realizadas en tiempo de ejecución, lo que significa que desea poder utilizar las propiedades de Monad pero luego desea elegir las funciones de Monad.

Eso se puede hacer usando la Mónada Libre (estructura de datos), que envuelve el Functor (tipo) de tal manera que joines más bien un apilamiento de esos functores que una reducción.

Lo real returny lo joinque quiere usar ahora se puede dar como parámetros para la función de reducción foldFree:

foldFree :: Functor f => (a -> b) -> (f b -> b) -> Free f a -> b
foldFree return join :: Monad m => Free m a -> m a

Para explicar los tipos, podemos reemplazar Functor fcon Monad my bcon (m a):

foldFree :: Monad m => (a -> (m a)) -> (m (m a) -> (m a)) -> Free m a -> (m a)
comonad
fuente
8
Esta respuesta me dio la impresión de que entiendo para qué podrían ser útiles.
David
59

Una mónada libre de Haskell es una lista de functors. Comparar:

data List a   = Nil    | Cons  a (List a  )

data Free f r = Pure r | Free (f (Free f r))

Purees análogo a Nily Freees análogo a Cons. Una mónada gratuita almacena una lista de functores en lugar de una lista de valores. Técnicamente, podría implementar mónadas libres utilizando un tipo de datos diferente, pero cualquier implementación debería ser isomorfa a la anterior.

Utiliza mónadas gratis siempre que necesites un árbol de sintaxis abstracta. El functor base de la mónada libre es la forma de cada paso del árbol de sintaxis.

Mi publicación , que alguien ya ha vinculado, ofrece varios ejemplos de cómo construir árboles de sintaxis abstracta con mónadas gratuitas

Gabriel Gonzalez
fuente
66
Sé que estabas dibujando una analogía en lugar de hacer una definición, pero una mónada libre ciertamente no es análoga a una lista de functores en ningún sentido. Está mucho más cerca de un árbol de functors.
Tom Ellis
66
Mantengo mi terminología. Por ejemplo, usando mi paquete index-core puede definir "comprensiones de mónada libre", que se comportan igual que la mónada de la lista, excepto que vincula los functores en lugar de los valores. Una mónada libre es una lista de functores en el sentido de que si traduce todos los conceptos de Haskell en la categoría de functores, las listas se convertirán en mónadas libres. Un verdadero árbol de functors se convierte en algo completamente diferente.
Gabriel Gonzalez el
44
Tienes razón en que la mónada es la categorización, en cierto sentido, del concepto de monoide, por lo que las mónadas libres son análogas a los monoides libres, es decir, las listas. Hasta ese punto, ciertamente tienes razón. Sin embargo, la estructura de un valor de una mónada libre no es una lista. Es un árbol, como detallo a continuación .
Tom Ellis
2
@TomEllis Técnicamente, es solo un árbol si su functor base es un functor de producto. Cuando tiene un functor de suma como el functor base, se parece más a una máquina apiladora.
Gabriel Gonzalez
21

Creo que un simple ejemplo concreto ayudará. Supongamos que tenemos un functor

data F a = One a | Two a a | Two' a a | Three Int a a a

con lo obvio fmap. A continuación, Free F aes el tipo de árboles cuyas hojas tienen el tipo ay cuyos nodos están etiquetados con One, Two, Two'y Three. One-nodes tienen un hijo, Two- y Two'-nodes tienen dos hijos y Three-nodes tienen tres y también están etiquetados con un Int.

Free FEs una mónada. returnasigna xal árbol que es solo una hoja con valor x. t >>= fmira cada una de las hojas y las reemplaza con árboles. Cuando la hoja tiene valor y, reemplaza esa hoja con el árbol f y.

¡Un diagrama lo aclara, pero no tengo las facilidades para dibujarlo fácilmente!

Tom Ellis
fuente
14
Lo que ustedes están diciendo es que la mónada libre toma la forma del propio functor. Entonces, si el functor es similar a un árbol (productos), la mónada libre es similar a un árbol; si es como una lista (sumas), mónada libre es como una lista; si es funcional, la mónada libre es funcional; etc. Esto tiene sentido para mí. Entonces, al igual que en un monoide gratuito, sigue tratando cada aplicación de mappend como la creación de un elemento completamente nuevo; en mónada libre, trata cada aplicación del functor como un elemento completamente nuevo.
Bartosz Milewski
44
Incluso si el functor es un "sum functor", la mónada libre resultante sigue siendo un árbol. Termina con más de un tipo de nodo en su árbol: uno para cada componente de su suma. Si su "sumador" es X -> 1 + X, entonces obtendrá una lista, que es solo una especie de árbol degenerado.
Tom Ellis