haskell - learn - monad example
Mónadas con Join() en lugar de Bind() (7)
Las mónadas generalmente se explican en turnos de return y bind . Sin embargo, supongo que también puedes implementar bind en términos de join (y fmap ?)
En los lenguajes de programación que carecen de funciones de primera clase, el bind es insoportablemente incómodo de usar. join , por otro lado, parece bastante fácil.
Sin embargo, no estoy completamente seguro de entender cómo funciona la join . Obviamente, tiene el tipo [Haskell]
join :: Monad m => m (m x) -> m x
Para la lista de mónadas, esto es trivial y obviamente concat . Pero para una mónada general, ¿qué operacionalmente hace este método? Veo lo que significa para las firmas de tipos, pero estoy tratando de descubrir cómo escribiría algo como esto en, por ejemplo, Java o similar.
(En realidad, eso es fácil: no lo haría. Porque los genéricos están rotos; ;-) Pero, en principio, la pregunta sigue en pie ...)
Oops. Parece que esto se ha preguntado antes:
¿Podría alguien esbozar algunas implementaciones de mónadas comunes usando return , fmap y join ? (Es decir, sin mencionar >>= en absoluto.) Creo que tal vez eso podría ayudar a hundirse en mi tonto cerebro ...
De acuerdo, entonces no es una buena forma responder tu propia pregunta, pero voy a anotar mi pensamiento en caso de que ilumine a alguien más. (Lo dudo...)
Si una mónada se puede considerar como un "contenedor", tanto el return como la join tienen una semántica bastante obvia. return genera un contenedor de 1 elemento y join convierte un contenedor de contenedores en un único contenedor. Nada difícil sobre eso.
Así que centrémonos en las mónadas que se consideran más naturalmente como "acciones". En ese caso, mx es un tipo de acción que produce un valor de tipo x cuando lo "ejecuta". return x no hace nada especial, y luego cede x . fmap f toma una acción que produce una x y construye una acción que calcula x y luego aplica f a ella, y devuelve el resultado. Hasta aquí todo bien.
Es bastante obvio que si f sí genera una acción, entonces con lo que terminas es m (mx) . Es decir, una acción que computa otra acción. En cierto modo, eso es incluso más sencillo de entender que la función >>= que toma una acción y una "función que produce una acción", y así sucesivamente.
Entonces, lógicamente hablando, parece que join ejecutaría la primera acción, tomaría la acción que produce y luego la ejecutaría. (O más bien, join devolvería una acción que hace lo que acabo de describir, si desea dividir pelos).
Esa parece ser la idea central. Para implementar join , desea ejecutar una acción, que luego le da otra acción, y luego ejecutar eso. (Lo que sea que "correr" signifique para esta mónada particular).
Dada esta idea, puedo probar algunas implementaciones de join :
join Nothing = Nothing
join (Just mx) = mx
Si la acción externa es Nothing , devuelve Nothing , de lo contrario regresa la acción interna. Por otra parte, Maybe es más un contenedor que una acción, así que probemos algo más ...
newtype Reader s x = Reader (s -> x)
join (Reader f) = Reader (/ s -> let Reader g = f s in g s)
Eso fue ... sin dolor. Un Reader es en realidad solo una función que toma un estado global y solo luego devuelve su resultado. Entonces, para desapilar, aplica el estado global a la acción externa, que devuelve un nuevo Reader . A continuación, aplica el estado a esta función interna también.
En cierto modo, es quizás más fácil que la forma habitual:
Reader f >>= g = Reader (/ s -> let x = f s in g x)
Ahora, ¿cuál es la función de lector, y cuál es la función que calcula el próximo lector ...?
Ahora probemos la buena vieja mónada State . Aquí cada función toma un estado inicial como entrada pero también devuelve un nuevo estado junto con su salida.
data State s x = State (s -> (s, x))
join (State f) = State (/ s0 -> let (s1, State g) = f s0 in g s1)
Eso no fue muy difícil. Básicamente se ejecuta seguido de ejecución.
Voy a dejar de escribir ahora. Siéntase libre de señalar todos los fallos y errores tipográficos en mis ejemplos ...: - /
Esto es Monad explicado en una imagen. Las 2 funciones en la categoría verde no se pueden componer, cuando se asignan a la categoría azul (estrictamente hablando, son una categoría), se vuelven compostables. Monad se trata de convertir una función de tipo T -> Monad<U> en una función de Monad<T> -> Monad<U> .
He encontrado muchas explicaciones de mónadas que dicen "no tienes que saber nada sobre la teoría de categorías, en realidad, solo piensa en mónadas como burritos / trajes espaciales / lo que sea".
Realmente, el artículo que desmistificó las mónadas solo me decía qué categorías había, describía las mónadas (incluidas las de unión y vinculación) en términos de categorías, y no me molestaba con ninguna metáfora falsa:
Creo que el artículo es muy legible sin mucho conocimiento matemático requerido.
Llamar a fmap (f :: a -> mb) (x :: m a) produce valores (y :: m (mb)) por lo que es una cosa muy natural usar join para recuperar valores (z :: mb) .
Entonces bind se define simplemente como bind ma f = join (fmap f ma) , logrando así la composicionalidad Kleisly de las funciones de la variedad (:: a -> mb) , que es de lo que se trata en realidad:
ma `bind` (f >=> g) = (ma `bind` f) `bind` g -- bind = (>>=)
= (`bind` g) . (`bind` f) $ ma
= join . fmap g . join . fmap f $ ma
Y entonces, con flip bind = (=<<) , tenemos
((g <=< f) =<<) = (g =<<) . (f =<<) = join . (g <$>) . join . (f <$>)
Preguntar qué hace una firma de tipo en Haskell es más bien preguntar qué hace una interfaz en Java.
Es, en cierto sentido literal, "no". (Aunque, por supuesto, normalmente tendrá algún tipo de propósito asociado, eso está más en su mente, y sobre todo no en la implementación).
En ambos casos, usted está declarando secuencias legales de símbolos en el idioma que se usará en definiciones posteriores.
Por supuesto, en Java, supongo que podría decirse que una interfaz corresponde a una firma de tipo que se implementará literalmente en la máquina virtual. Puede obtener un poco de polimorfismo de esta manera: puede definir un nombre que acepte una interfaz y puede proporcionar una definición diferente para el nombre que acepte una interfaz diferente. Algo similar sucede en Haskell, donde puede proporcionar una declaración para un nombre que acepte un tipo y luego otra declaración para ese nombre que trate un tipo diferente.
Sin sondear las profundidades de la metáfora, podría sugerir leer una mónada típica como "estrategia para producir a", por lo que el m value tipo m value es una "estrategia de primera clase para producir un valor". Las diferentes nociones de computación o interacción externa requieren diferentes tipos de estrategia, pero la noción general requiere alguna estructura regular para tener sentido:
- si ya tiene un valor, entonces tiene una estrategia para producir un valor (
return :: v -> mv) que consiste en nada más que producir el valor que tiene; - si tiene una función que transforma un tipo de valor en otro, puede
fmap :: (v -> u) -> mv -> mua estrategias (fmap :: (v -> u) -> mv -> mu) solo esperando a que la estrategia entregue su valor, luego se transforma eso; - si tiene una estrategia para producir una estrategia para producir un valor, entonces puede construir una estrategia para producir un valor (
join :: m (mv) -> mv) que sigue la estrategia externa hasta que produce la estrategia interna, luego sigue esa estrategia interna hasta llegar a un valor.
Veamos un ejemplo: árboles binarios etiquetados con hojas ...
data Tree v = Leaf v | Node (Tree v) (Tree v)
... representan estrategias para producir cosas tirando una moneda. Si la estrategia es Leaf v , está tu v ; si la estrategia es Node ht , arroja una moneda y continúa con la estrategia h si la moneda muestra "cabezas", t si son "colas".
instance Monad Tree where
return = Leaf
Una estrategia que produce estrategias es un árbol con hojas etiquetadas como árboles: en lugar de cada hoja, podemos injertar en el árbol que la etiqueta ...
join (Leaf tree) = tree
join (Node h t) = Node (join h) (join t)
... y, por supuesto, tenemos fmap que simplemente vuelve a etiquetar.
instance Functor Tree where
fmap f (Leaf x) = Leaf (f x)
fmap f (Node h t) = Node (fmap f h) (fmap f t)
Aquí hay una estrategia para producir una estrategia para producir un Int .
Lanza una moneda: si es "cara", tira otra moneda para decidir entre dos estrategias (producir, respectivamente, "lanzar una moneda para producir 0 o producir 1" o "producir 2"); si es "colas", produzca una tercera ("arroje una moneda por producir 3 o arroje una moneda por 4 o 5").
Eso se join claramente para hacer que una estrategia produzca un Int .
Lo que estamos utilizando es el hecho de que una "estrategia para producir un valor" puede verse como un valor. En Haskell, la incrustación de estrategias como valores es silenciosa, pero en inglés, uso comillas para distinguir usando una estrategia de solo hablar de ella. El operador de join expresa la estrategia "de alguna manera produce y sigue una estrategia", o "si le dicen una estrategia, puede usarla ".
(Meta. No estoy seguro de si este enfoque de "estrategia" es una manera adecuadamente genérica de pensar sobre las mónadas y la distinción entre valor y computación, o si es simplemente otra metáfora pésima. Encuentro que los tipos de árbol con hojas etiquetados son útiles fuente de intuición, que quizás no sea una sorpresa, ya que son las mónadas libres , con la estructura suficiente para ser mónadas en absoluto, pero no más).
PD El tipo de "enlace"
(>>=) :: m v -> (v -> m w) -> m w
dice "si tienes una estrategia para producir una v , y para cada estrategia de continuación de va para producir una w , entonces tienes una estrategia para producir una w ". ¿Cómo podemos capturar eso en términos de join ?
mv >>= v2mw = join (fmap v2mw mv)
Podemos volver a etiquetar nuestra estrategia de producción de v por v2mw , produciendo en lugar de cada valor de v la estrategia de producción w que sigue, lista para join .
join = concat -- []
join f = /x -> f x x -- (e ->)
join f = /s -> let (f'', s'') = f s in f'' s'' -- State
join (Just (Just a)) = Just a; join _ = Nothing -- Maybe
join (Identity (Identity a)) = Identity a -- Identity
join (Right (Right a)) = Right a; join (Right (Left e)) = Left e;
join (Left e) = Left e -- Either
join ((a, m), m'') = (a, m'' `mappend` m) -- Writer
join f = /k -> f (/f'' -> f'' k) -- Cont