385 votos

Una mónada es sólo un monoid en la categoría de endofunctors, ¿cuál es el problema?

El primero que dijo

Una mónada es sólo un monoid en el categoría de endofunctors, ¿cuál es la problema?

y en menos nota importante es esto cierto y si es así ¿podrías dar una explicación (esperemos que pueda ser entendido por alguien que no tiene mucho haskell experiencia).

445voto

pelotom Puntos 14817

Que en particular fraseo es por James Iry, desde su muy entretenido Breve, Incompleta y, en su Mayoría Mal la Historia de los Lenguajes de Programación, en la que él fictionally atribuye a Felipe Wadler.

La cita original es de Saunders Mac Lane en Categorías para el Trabajo Matemático, uno de los textos fundacionales de la Categoría de Teoría. Aquí está en su contexto, que es probablemente el mejor lugar para aprender exactamente lo que significa.

Pero, voy a tomar una puñalada. La frase original es este:

Todo dicho, una mónada en X es solo un monoid en la categoría de endofunctors de X, con productos × reemplazado por la composición de endofunctors y unidad de conjunto por la identidad endofunctor.

X aquí es una categoría. Endofunctors son functors de una categoría a sí mismo (que es generalmente de todos Functors tan lejos como funcional a los programadores, ya que están tratando principalmente con una categoría; la categoría de tipos, pero estoy divagando). Pero usted se pueda imaginar, otra categoría que es la categoría de "endofunctors en X". Esta es una categoría en la que los objetos son endofunctors y los morfismos son transformaciones naturales.

Y de los endofunctors, algunos de ellos podrían ser mónadas. Cuáles son las mónadas? Exactamente los que son monoidal en un determinado sentido. En lugar de la ortografía de la exacta correspondencia de las mónadas a monoids (desde Mac Lane hace que mucho mejor de lo que yo podría esperar), voy a poner a sus respectivas definiciones de lado a lado y vamos a comparar:

Un monoid es...

  • Un conjunto S
  • Una operación, • : S × S -> S
  • Un elemento de S, e : 1 -> S

...la satisfacción de estas leyes:

  • (a • b) • c = a • (b • c), para todo un, b y c en S
  • e • a = a = a • e, para todos un en S

Una mónada es...

  • Un endofunctor, T : X -> X
  • Una transformación natural, μ : T × T -> T, donde x significa functor composición
  • Una transformación natural, η : I -> T, donde I es la identidad endofunctor en X

...la satisfacción de estas leyes:

  • μ(μ(T × T) × T)) = μ(T × μ(T × T))
  • μ(η(T)) = T = μ(T(η))

Con un poco de estrabismo usted probablemente puede ver que ambas definiciones son instancias del mismo concepto abstracto (creo categoría teóricos diría "monoid" es el término abstracto, y mi definición de "monoid" de arriba es demasiado específica, ya que se menciona a los conjuntos y elementos).

308voto

misterbee Puntos 2523

Intuitivamente, creo que lo que la fantasía de vocabulario de las matemáticas está diciendo es que:

Monoid

Un monoid es un conjunto de objetos, y un método de combinación de ellos. Bien conocido monoids son:

  • números a los que usted puede agregar
  • las listas se pueden concatenar
  • conjuntos puede unión"

    Hay ejemplos más complejos también.

Además, Cada monoid tiene una identidad, que es eso de "no-op" elemento que no tiene ningún efecto cuando se combina con otra cosa:

  • 0 + 7 == 7 + 0 == 7
  • [] ++ [1,2,3] == [1,2,3] ++ [] == [1,2,3]
  • {} de la unión {apple} == {apple} union {} == {apple}

Finalmente, un monoid debe ser asociativa. (usted puede reducir una larga cadena de combinaciones de todos modos usted desea, mientras usted no cambie la izquierda-a-derecha-orden de los objetos), Además es ACEPTAR((5+3)+1 == 5+(3+1)), pero la resta no es ((5-3)-1 != 5-(3-1)).

Mónada

Ahora, vamos a considerar un tipo especial de conjunto y de manera especial de la combinación de objetos.

Objetos

Supongamos que el conjunto contiene objetos de un tipo especial: funciones. Y estas funciones tienen una interesante firma: no llevan números a los números, cadenas o cuerdas. Cada función se lleva un número a una lista de números, en un proceso de dos pasos.

  1. Calcular 0 o más resultados
  2. Combinar los resultados a una sola respuesta alguna manera.

Ejemplos:

  • 1 -> [1] (simplemente envuelva la entrada)
  • 1 -> [] (descartar la entrada ,la envoltura de la nada en una lista)
  • 1 -> [2] (agregar 1 a la entrada, y envolver el resultado)
  • 3 -> [4, 6] (agregar 1 a la entrada, y multiplicar entrada por 2, y la envoltura de los múltiples resultados)

La Combinación De Objetos

También, nuestra manera de combinar las funciones especiales. Una forma sencilla de combinar la función es la composición: Vamos a tomar nuestros ejemplos anteriores, y de componer cada una de las funciones con el mismo:

  • 1 -> [1] -> [[1]] (envuelva la entrada, dos veces)
  • 1 -> [] -> [] (deseche la entrada, la envoltura de la nada en una lista, dos veces)
  • 1 -> [2] -> [ UH-OH! ] (no podemos "agregar 1" a una lista!")
  • 3 -> [4, 6] -> [ UH-OH! ] (que no puede añadir 1 una lista!)

Sin llegar a tanto en el tipo de teoría, el punto es que puede combinar dos números enteros para obtener un entero, pero no siempre se pueden componer dos funciones y una función del mismo tipo. (Con la función de tipo a -> van a componer, pero a-> [a] no.)

Así que, vamos a definir una forma diferente de combinar funciones. Cuando combinamos dos de estas funciones, no queremos "doble-wrap" los resultados.

Esto es lo que hacemos. Cuando queremos combinar dos funciones F y G, se sigue este proceso (llamado de unión):

  1. Calcular los "resultados" de F, pero no combinarlos.
  2. Calcular los resultados de la aplicación de G para cada una de las F resultados por separado, produciendo una colección de recogida de los resultados.
  3. Aplanar la 2-nivel colección, y combinar todos los resultados.

De vuelta a nuestros ejemplos, vamos a combinar (bind) una función con la misma, utilizando esta nueva forma de "vinculante" de la función:

  • 1 -> [1] -> [1] (envuelva la entrada, dos veces)
  • 1 -> [] -> [] (deseche la entrada, la envoltura de la nada en una lista, dos veces)
  • 1 -> [2] -> [ 3 ] (añadir 1, a continuación, añadir 1 de nuevo, y envolver el resultado).
  • 3 -> [4,6] -> [ 5,8, 7,12] (agregar 1 a la entrada, y también se multiplican entrada por 2, manteniendo los dos resultados, a continuación, hacerlo todo de nuevo para ambos resultados, y la envoltura de los resultados finales en una lista).

Esta forma más sofisticada de la combinación de funciones es asociativa (después de cómo la función de composición asociativa cuando usted no está haciendo el lujo de envolver cosas).

Atar todo junto,

  • una mónada es una estructura que define una forma de combinar (los resultados de) funciones,
  • de forma análoga a cómo un monoid es una estructura que define una forma de combinar objetos,
  • cuando el método de combinación es asociativa,
  • y donde hay un especial de 'No-op', que puede ser combinado con Algo de resultado en Algo sin cambios.

Notas

Hay un montón de formas para "envolver" los resultados. Usted puede hacer una lista, o un conjunto, o descartar todos, pero el primer resultado, mientras que señalar, si no hay resultados, adjuntar un sidecar de estado, imprimir un mensaje de registro, etc, etc.

He jugado un poco floja con las definiciones, en la esperanza de conseguir la idea esencial de todo de forma intuitiva.

He simplificado un poco las cosas, insistiendo en que nuestra mónada operar sobre las funciones del tipo a -> [a]. De hecho, las mónadas de trabajo sobre las funciones del tipo a -> m b , pero la generalización es un detalle técnico que no es el principal de conocimiento.

39voto

Luis Casillas Puntos 11718

Esta es una vieja pregunta, pero creo que hay una manera de hacer que la respuesta un poco más concreto con el código. Al menos, yo soy mejor en Haskell que estoy en la categoría de teoría, por lo que me resulta más fácil de entender de esta manera :-P.

En primer lugar, las extensiones y las librerías que vamos a utilizar:

{-# LANGUAGE RankNTypes, TypeOperators #-}

import Control.Monad (join)

De estos, RankNTypes es el único que es absolutamente esencial para el siguiente. Una vez escribí una explicación de RankNTypes que algunas personas parecen haber encontrado útil, así que me voy a referir a eso.

Citando pelotom excelente respuesta anterior, tenemos:

Una mónada es...

  • Un endofunctor, T : X -> X
  • Una transformación natural, μ : T × T -> T, donde x significa functor composición
  • Una transformación natural, η : I -> T, donde I es la identidad endofunctor en X

...la satisfacción de estas leyes:

  • μ(μ(T × T) × T)) = μ(T × μ(T × T))
  • μ(η(T)) = T = μ(T(η))

¿Cómo traducimos esto a Haskell código? Bueno, vamos a empezar con la noción de una transformación natural:

-- | A natural transformations between two 'Functor' instances.  Law:
--
-- > fmap f . eta g == eta g . fmap f
--
-- Neat fact: the type system actually guarantees this law.
--
newtype f :-> g = 
    Natural { eta :: forall x. (Functor f, Functor g) => f x -> g x }

Un tipo de la forma f :-> g es análogo a un tipo de función, pero en lugar de pensar en ello como una función entre dos tipos (de tipo *), piensa en ella como una de morfismos entre dos functors (cada uno de tipo * -> *). Ejemplos:

listToMaybe :: [] :-> Maybe
listToMaybe = Natural go
    where go [] = Nothing
          go (x:_) = Just x

maybeToList :: Maybe :-> []
maybeToList = Natural go
    where go Nothing = []
          go (Just x) = [x]

reverse' :: [] :-> []
reverse' = Natural reverse

Básicamente, en Haskell, natural transformaciones son funciones de algún tipo f x a otro tipo g x tal que el x tipo variable es "inaccesible" para la persona que llama. Así, por ejemplo, sort :: Ord a => [a] -> [a] no puede ser hecho en una transformación natural, porque es "exigente" sobre los tipos que podemos crear instancias para a. Una manera intuitiva de que yo uso a menudo para pensar en esto es la siguiente:

  • Un functor es una forma de operar sobre el contenido de algo sin tocar la estructura.
  • Una transformación natural es una forma de operar en la estructura de algo sin tocar o mirar el contenido.

Ahora, con eso fuera del camino, vamos a hacer frente a las cláusulas de la definición.

La primera cláusula es "un endofunctor, T : X -> X." Así, cada Functor en Haskell es un endofunctor en lo que la gente llama "el Hask categoría," cuyos objetos son los tipos de Haskell (de tipo *) y cuyos morfismos son Haskell funciones. Esto suena complicado, pero en realidad es un muy trivial. Todo lo que significa es que un Functor f :: * -> * le da el medio de la construcción de un tipo f a :: * para cualquier a :: *, y una función fmap f :: f a -> f b de cualquier f :: a -> b.

Cláusula segunda: la Identity functor en Haskell (que viene con la Plataforma, de modo que usted puede importar) se define de esta manera:

newtype Identity a = Identity { runIdentity :: a }

instance Functor Identity where
    fmap f (Identity a) = Identity (f a)

Así transformación natural η : I -> T de pelotom la definición puede ser escrito de esta manera para cualquier Monad ejemplo t:

return' :: Monad t => Identity :-> t
return' = Natural (return . runIdentity)

Cláusula tercera: la composición de dos functors en Haskell puede ser definido de esta manera (que también viene con la Plataforma):

newtype Compose f g a = Compose { getCompose :: f (g a) }

-- | The composition of two 'Functor's is also a 'Functor'.
instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose fga) = Compose (fmap (fmap f) fga)

Así que la transformación natural μ : T × T -> T de pelotom la definición puede ser escrita así:

join' :: Monad t => Compose t t :-> t
join' = Natural (join . getCompose)

La afirmación de que este es un monoid en la categoría de endofunctors significa, entonces, que Compose (que se aplica parcialmente a sólo sus dos primeros parámetros) es asociativa, y que Identity es su elemento de identidad. Es decir, que el siguiente isomorphisms espera:

  • Compose f (Compose g h) ~= Compose (Compose f g) h
  • Compose f Identity ~= f
  • Compose Identity g ~= g

Estos son muy fáciles de probar porque Compose y Identity son definidos como newtype, y la de Haskell Informes define la semántica de newtype como un isomorfismo entre el tipo de ser definidas y el tipo de argumento para la newtype's de datos constructor. Así, por ejemplo, vamos a probar Compose f Identity ~= f:

Compose f Identity a
    ~= f (Identity a)                 -- newtype Compose f g a = Compose (f (g a))
    ~= f a                            -- newtype Identity a = Identity a
Q.E.D.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X