preestablecida monadas monada leibniz espiritual educatina armonia haskell monads

haskell - monadas - ¿Por qué necesitamos mónadas?



monada espiritual (7)

En mi humilde opinión, las respuestas a la famosa pregunta "¿Qué es una mónada?" , especialmente los más votados, trate de explicar qué es una mónada sin explicar claramente por qué las mónadas son realmente necesarias . ¿Pueden explicarse como la solución a un problema?

¿Por qué necesitamos mónadas?

  1. Queremos programar solo usando funciones . ("programación funcional (FP)" después de todo).

  2. Entonces, tenemos un primer gran problema. Este es un programa:

    f(x) = 2 * x

    g(x,y) = x / y

    ¿Cómo podemos decir qué se debe ejecutar primero ? ¿Cómo podemos formar una secuencia ordenada de funciones (es decir, un programa ) usando no más que funciones ?

    Solución: componer funciones . Si quieres primero g luego f , solo escribe f(g(x,y)) . De esta manera, "el programa" también es una función: main = f(g(x,y)) . Bien pero ...

  3. Más problemas: algunas funciones pueden fallar (es decir, g(2,0) , dividir por 0). No tenemos "excepciones" en FP (una excepción no es una función). ¿Como lo resolvemos?

    Solución: permitamos que las funciones devuelvan dos tipos de cosas : en lugar de tener g : Real,Real -> Real (función de dos reales en un real), permitamos que g : Real,Real -> Real | Nothing g : Real,Real -> Real | Nothing (funciona de dos reales a (real o nada)).

  4. Pero las funciones deberían (para ser más simples) devolver solo una cosa .

    Solución: creemos un nuevo tipo de datos para devolver, un " tipo de boxeo " que encierra quizás un real o simplemente no es nada. Por lo tanto, podemos tener g : Real,Real -> Maybe Real . Bien pero ...

  5. ¿Qué pasa ahora con f(g(x,y)) ? f no está listo para consumir un Maybe Real . Y no queremos cambiar todas las funciones que podríamos conectar con g para consumir un Maybe Real .

    Solución: tengamos una función especial para "conectar" / "componer" / "vincular" funciones . De esa manera, podemos, detrás de escena, adaptar la salida de una función para alimentar la siguiente.

    En nuestro caso: g >>= f (conectar / componer g a f ). Queremos >>= para obtener la salida de g , inspeccionarla y, en caso de que sea Nothing simplemente no llame a f y no devuelva Nothing ; o por el contrario, extraiga el Real caja y alimente con él. (Este algoritmo es solo la implementación de >>= para el tipo Maybe ). También tenga en cuenta que >>= debe escribirse solo una vez por "tipo de boxeo" (cuadro diferente, algoritmo de adaptación diferente).

  6. Surgen muchos otros problemas que pueden resolverse usando este mismo patrón: 1. Use una "caja" para codificar / almacenar diferentes significados / valores, y tener funciones como g que devuelvan esos "valores en caja". 2. Tenga un compositor / enlazador g >>= f para ayudar a conectar la salida de f la entrada de f , para que no tengamos que cambiar ninguna f en absoluto.

  7. Los problemas notables que se pueden resolver con esta técnica son:

    • teniendo un estado global que cada función en la secuencia de funciones ("el programa") puede compartir: solución StateMonad .

    • No nos gustan las "funciones impuras": funciones que producen diferentes resultados para la misma entrada. Por lo tanto, marquemos esas funciones, haciendo que devuelvan un valor etiquetado / encajonado: IO monad.

Felicidad total!

Benjamin Pierce dijo en TAPL

Se puede considerar que un sistema de tipos calcula un tipo de aproximación estática a los comportamientos de tiempo de ejecución de los términos en un programa.

Es por eso que un lenguaje equipado con un poderoso sistema de tipos es estrictamente más expresivo que un lenguaje mal escrito. Puedes pensar en las mónadas de la misma manera.

Como @Carl y blog.sigfpe.com/2006/08/you-could-have-invented-monads-and.html point, puede equipar un tipo de datos con todas las operaciones que desee sin recurrir a mónadas, clases de tipos o cualquier otra cosa abstracta. Sin embargo, las mónadas le permiten no solo escribir código reutilizable, sino también abstraer todos los detalles redundantes.

Como ejemplo, digamos que queremos filtrar una lista. La forma más simple es utilizar la función de filter : filter (> 3) [1..10] , que equivale a [4,5,6,7,8,9,10] .

Una versión un poco más complicada del filter , que también pasa un acumulador de izquierda a derecha, es

swap (x, y) = (y, x) (.*) = (.) . (.) filterAccum :: (a -> b -> (Bool, a)) -> a -> [b] -> [b] filterAccum f a xs = [x | (x, True) <- zip xs $ snd $ mapAccumL (swap .* f) a xs]

Para obtener todo i , de modo que i <= 10, sum [1..i] > 4, sum [1..i] < 25 , podemos escribir

filterAccum (/a x -> let a'' = a + x in (a'' > 4 && a'' < 25, a'')) 0 [1..10]

que es igual a [3,4,5,6] .

O podemos redefinir la función nub , que elimina elementos duplicados de una lista, en términos de filterAccum :

nub'' = filterAccum (/a x -> (x `notElem` a, x:a)) []

nub'' [1,2,4,5,4,3,1,8,9,4] es igual a [1,2,4,5,3,8,9] . Aquí se pasa una lista como acumulador. El código funciona, porque es posible salir de la mónada de la lista, por lo que todo el cálculo se mantiene puro ( notElem no usa >>= realidad, pero podría). Sin embargo, no es posible abandonar con seguridad la mónada IO (es decir, no puede ejecutar una acción IO y devolver un valor puro; el valor siempre estará envuelto en la mónada IO). Otro ejemplo son las matrices mutables: después de haber dejado la mónada ST, donde vive una matriz mutable, ya no puede actualizar la matriz en tiempo constante. Por lo tanto, necesitamos un filtrado monádico del módulo Control.Monad :

filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a] filterM _ [] = return [] filterM p (x:xs) = do flg <- p x ys <- filterM p xs return (if flg then x:ys else ys)

filterM ejecuta una acción monádica para todos los elementos de una lista, produciendo elementos, para los cuales la acción monádica devuelve True .

Un ejemplo de filtrado con una matriz:

nub'' xs = runST $ do arr <- newArray (1, 9) True :: ST s (STUArray s Int Bool) let p i = readArray arr i <* writeArray arr i False filterM p xs main = print $ nub'' [1,2,4,5,4,3,1,8,9,4]

imprime [1,2,4,5,3,8,9] como se esperaba.

Y una versión con la mónada IO, que pregunta qué elementos devolver:

main = filterM p [1,2,4,5] >>= print where p i = putStrLn ("return " ++ show i ++ "?") *> readLn

P.ej

return 1? -- output True -- input return 2? False return 4? False return 5? True [1,5] -- output

Y como ilustración final, filterAccum se puede definir en términos de filterM :

filterAccum f a xs = evalState (filterM (state . flip f) xs) a

con la mónada StateT , que se usa debajo del capó, siendo solo un tipo de datos ordinario.

Este ejemplo ilustra que las mónadas no solo le permiten abstraer el contexto computacional y escribir código reutilizable limpio (debido a la componibilidad de las mónadas, como explica @Carl), sino también tratar los tipos de datos definidos por el usuario y las primitivas integradas de manera uniforme.

La respuesta es, por supuesto, "No lo hacemos" . Como con todas las abstracciones, no es necesario.

Haskell no necesita una abstracción de mónada. No es necesario para realizar IO en un lenguaje puro. El tipo IO se encarga de eso muy bien por sí mismo. El desugaring monádico existente de los bloques do podría reemplazarse por desugaring a bindIO , returnIO y failIO como se define en el módulo GHC.Base . (No es un módulo documentado sobre piratería, por lo que tendré que señalar su fuente de documentación). Entonces, no, no hay necesidad de la abstracción de mónada.

Entonces, si no es necesario, ¿por qué existe? Porque se descubrió que muchos patrones de cálculo forman estructuras monádicas. La abstracción de una estructura permite escribir código que funciona en todas las instancias de esa estructura. Para decirlo de manera más concisa: reutilización de código.

En lenguajes funcionales, la herramienta más poderosa encontrada para la reutilización de código ha sido la composición de funciones. El viejo operador (.) :: (b -> c) -> (a -> b) -> (a -> c) es extremadamente poderoso. Facilita la escritura de funciones pequeñas y las une con una mínima sobrecarga sintáctica o semántica.

Pero hay casos en que los tipos no funcionan del todo bien. ¿Qué haces cuando tienes foo :: (b -> Maybe c) y bar :: (a -> Maybe b) ? foo . bar foo . bar no escribe, porque b y Maybe b no son del mismo tipo.

Pero ... es casi correcto. Solo quieres un poco de libertad. Desea poder tratar Maybe b como si fuera básicamente b . Sin embargo, es una mala idea simplemente tratarlos como si fueran del mismo tipo. Eso es más o menos lo mismo que los punteros nulos, que Tony Hoare llamó el error de mil millones de dólares . Entonces, si no puede tratarlos como el mismo tipo, tal vez pueda encontrar una manera de extender el mecanismo de composición que proporciona (.) .

En ese caso, es importante examinar realmente la teoría subyacente (.) . Afortunadamente, alguien ya ha hecho esto por nosotros. Resulta que la combinación de (.) id forman una construcción matemática conocida como category . Pero hay otras formas de formar categorías. Una categoría de Kleisli, por ejemplo, permite que los objetos que se componen se aumenten un poco. Una categoría de Kleisli para Maybe consistiría en (.) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c) y id :: a -> Maybe a . Es decir, los objetos en la categoría aumentan el (->) con un Maybe , entonces (a -> b) convierte en (a -> Maybe b) .

Y de repente, hemos extendido el poder de la composición a cosas en las que la operación tradicional (.) No funciona. Esta es una fuente de nuevo poder de abstracción. Las categorías de Kleisli funcionan con más tipos que solo Maybe . Trabajan con todo tipo que pueda ensamblar una categoría adecuada, obedeciendo las leyes de categoría.

  1. Identidad izquierda: id . f id . f = f
  2. Identidad correcta: f . id f . id = f
  3. Asociatividad: f . (g . h) f . (g . h) = (f . g) . h (f . g) . h

Siempre que pueda probar que su tipo obedece esas tres leyes, puede convertirlo en una categoría Kleisli. ¿Y cuál es el problema con eso? Bueno, resulta que las mónadas son exactamente lo mismo que las categorías de Kleisli. El return Monad es el mismo que el de Kleisli. Monad (>>=) no es idéntica a Kleisli (.) , Pero resulta muy fácil escribir cada una en términos de la otra. Y las leyes de categoría son las mismas que las leyes de mónada, cuando las traduces a través de la diferencia entre (>>=) y (.) .

Entonces, ¿por qué pasar por toda esta molestia? ¿Por qué tener una abstracción Monad en el lenguaje? Como mencioné anteriormente, permite la reutilización del código. Incluso permite la reutilización del código a lo largo de dos dimensiones diferentes.

La primera dimensión de la reutilización del código proviene directamente de la presencia de la abstracción. Puede escribir código que funcione en todas las instancias de la abstracción. Existe todo el paquete de bucles monad que consta de bucles que funcionan con cualquier instancia de Monad .

La segunda dimensión es indirecta, pero se sigue de la existencia de la composición. Cuando la composición es fácil, es natural escribir código en fragmentos pequeños y reutilizables. De la misma manera, tener el operador (.) Para funciones fomenta la escritura de funciones pequeñas y reutilizables.

Entonces, ¿por qué existe la abstracción? Porque se ha demostrado que es una herramienta que permite una mayor composición en el código, lo que resulta en la creación de código reutilizable y fomenta la creación de más código reutilizable. La reutilización de código es uno de los santos griales de la programación. La abstracción de la mónada existe porque nos mueve un poco hacia ese santo grial.

Las mónadas sirven básicamente para componer funciones juntas en una cadena. Período.

Ahora, la forma en que se componen difiere entre las mónadas existentes, lo que resulta en diferentes comportamientos (por ejemplo, para simular un estado mutable en la mónada estatal).

La confusión acerca de las mónadas es que, al ser tan generales, es decir, un mecanismo para componer funciones, se pueden usar para muchas cosas, lo que lleva a las personas a creer que las mónadas son sobre el estado, sobre IO, etc., cuando solo se trata de "componer funciones ".

Ahora, una cosa interesante sobre las mónadas, es que el resultado de la composición siempre es del tipo "M a", es decir, un valor dentro de un sobre etiquetado con "M". Esta característica resulta realmente agradable de implementar, por ejemplo, una separación clara entre el código puro del impuro: declare todas las acciones impuras como funciones de tipo "IO a" y no proporcione ninguna función, al definir la mónada IO, para eliminar el " un "valor desde dentro del" IO a ". El resultado es que ninguna función puede ser pura y al mismo tiempo extraer un valor de un "IO a", porque no hay forma de tomar dicho valor mientras se mantiene puro (la función debe estar dentro de la mónada "IO" para usar tal valor). (NOTA: bueno, nada es perfecto, por lo que la "camisa de fuerza IO" se puede romper usando "unsafePerformIO: IO a -> a" contaminando así lo que se suponía que era una función pura, pero esto debe usarse con moderación y cuando realmente sepa que no debe introducir ningún código impuro con efectos secundarios.

Necesita mónadas si tiene un constructor de tipos y funciones que devuelven valores de esa familia de tipos . Eventualmente, le gustaría combinar este tipo de funciones juntas . Estos son los tres elementos clave para responder por qué .

Déjame elaborar. Tiene Int , String y Real y funciones de tipo Int -> String , String -> Real y así sucesivamente. Puede combinar estas funciones fácilmente, terminando con Int -> Real . La vida es buena.

Entonces, un día, necesitas crear una nueva familia de tipos . Puede deberse a que debe considerar la posibilidad de no devolver ningún valor ( Maybe ), devolver un error ( Either ), múltiples resultados ( List ), etc.

Tenga en cuenta que Maybe es un constructor de tipos. Toma un tipo, como Int y devuelve un nuevo tipo Maybe Int . Lo primero que debe recordar, sin constructor de tipo, sin mónada.

Por supuesto, desea usar su constructor de tipos en su código, y pronto terminará con funciones como Int -> Maybe String y String -> Maybe Float . Ahora, no puede combinar fácilmente sus funciones. La vida ya no es buena.

Y aquí es cuando las mónadas vienen al rescate. Le permiten combinar ese tipo de funciones nuevamente. Solo necesitas cambiar la composición . para > == .

Las mónadas son solo un marco conveniente para resolver una clase de problemas recurrentes. Primero, las mónadas deben ser functores (es decir, deben admitir el mapeo sin mirar los elementos (o su tipo)), también deben traer una operación de enlace (o encadenamiento) y una forma de crear un valor monádico a partir de un tipo de elemento ( return ). Finalmente, bind y return deben satisfacer dos ecuaciones (identidades izquierda y derecha), también llamadas leyes de mónada. (Alternativamente, uno podría definir mónadas para tener una flattening operation lugar de encuadernación).

La lista mónada se usa comúnmente para tratar el no determinismo. La operación de vinculación selecciona un elemento de la lista (intuitivamente todos en mundos paralelos ), le permite al programador hacer algunos cálculos con ellos y luego combina los resultados en todos los mundos en una sola lista (concatenando o aplanar una lista anidada) ) Así es como se definiría una función de permutación en el marco monádico de Haskell:

perm [e] = [[e]] perm l = do (leader, index) <- zip l [0 :: Int ..] let shortened = take index l ++ drop (index + 1) l trailer <- perm shortened return (leader : trailer)

Aquí hay una sesión de respuesta de ejemplo:

*Main> perm "a" ["a"] *Main> perm "ab" ["ab","ba"] *Main> perm "" [] *Main> perm "abc" ["abc","acb","bac","bca","cab","cba"]

Cabe señalar que la mónada de la lista no es en modo alguno un cómputo de efectos secundarios. Una estructura matemática que es una mónada (es decir, conforme a las interfaces y leyes mencionadas anteriormente) no implica efectos secundarios, aunque los fenómenos de efectos secundarios a menudo encajan muy bien en el marco monádico.

No creo que IO deba verse como una mónada particularmente sobresaliente, pero sin duda es una de las más sorprendentes para principiantes, por lo que la usaré para mi explicación.

Construyendo ingenuamente un sistema IO para Haskell

El sistema IO más simple concebible para un lenguaje puramente funcional (y de hecho con el que Haskell comenzó) es este:

main₀ :: String -> String main₀ _ = "Hello World"

Con pereza, esa simple firma es suficiente para construir programas de terminal interactivos, aunque muy limitada. Lo más frustrante es que solo podemos generar texto. ¿Qué pasa si agregamos algunas posibilidades de salida más emocionantes?

data Output = TxtOutput String | Beep Frequency main₁ :: String -> [Output] main₁ _ = [ TxtOutput "Hello World" -- , Beep 440 -- for debugging ]

lindo, pero por supuesto una "salida alternativa" mucho más realista sería escribir en un archivo . Pero entonces también querrías alguna forma de leer de los archivos. ¿Cualquier oportunidad?

Bueno, cuando tomamos nuestro programa main₁ y simplemente canalizamos un archivo al proceso (usando las instalaciones del sistema operativo), esencialmente hemos implementado la lectura de archivos. Si pudiéramos activar esa lectura de archivos desde el lenguaje Haskell ...

readFile :: Filepath -> (String -> [Output]) -> [Output]

Esto usaría una String->[Output] "programa interactivo" String->[Output] , la alimentaría con una cadena obtenida de un archivo y generaría un programa no interactivo que simplemente ejecuta el dado.

Aquí hay un problema: realmente no tenemos una noción de cuándo se lee el archivo. La lista [Output] ciertamente da un buen orden a las salidas , pero no recibimos un orden de cuándo se realizarán las entradas .

Solución: haga que los eventos de entrada también sean elementos en la lista de cosas que hacer.

data IO₀ = TxtOut String | TxtIn (String -> [Output]) | FileWrite FilePath String | FileRead FilePath (String -> [Output]) | Beep Double main₂ :: String -> [IO₀] main₂ _ = [ FileRead "/dev/null" $ /_ -> [TxtOutput "Hello World"] ]

Bien, ahora puede detectar un desequilibrio: puede leer un archivo y hacer que la salida dependa de él, pero no puede usar el contenido del archivo para decidir, por ejemplo, también leer otro archivo. Solución obvia: hacer que el resultado de los eventos de entrada también sea de tipo IO , no solo de Output . Eso seguro incluye una salida de texto simple, pero también permite leer archivos adicionales, etc.

data IO₁ = TxtOut String | TxtIn (String -> [IO₁]) | FileWrite FilePath String | FileRead FilePath (String -> [IO₁]) | Beep Double main₃ :: String -> [IO₁] main₃ _ = [ TxtIn $ /_ -> [TxtOut "Hello World"] ]

Eso ahora le permitiría expresar cualquier operación de archivo que desee en un programa (aunque tal vez no con un buen rendimiento), pero es algo complicado:

  • main₃ produce una lista completa de acciones. ¿Por qué no usamos simplemente la firma :: IO₁ , que tiene esto como un caso especial?

  • Las listas ya no dan una descripción confiable del flujo del programa: la mayoría de los cálculos posteriores solo serán "anunciados" como resultado de alguna operación de entrada. Por lo tanto, podríamos deshacernos de la estructura de la lista, y simplemente contrarrestar un "y luego hacer" a cada operación de salida.

data IO₂ = TxtOut String IO₂ | TxtIn (String -> IO₂) | Terminate main₄ :: IO₂ main₄ = TxtIn $ /_ -> TxtOut "Hello World" Terminate

¡No está mal!

Entonces, ¿qué tiene todo esto que ver con las mónadas?

En la práctica, no querrás usar constructores simples para definir todos tus programas. Tendría que haber un buen par de constructores fundamentales, pero para la mayoría de las cosas de nivel superior nos gustaría escribir una función con alguna buena firma de alto nivel. Resulta que la mayoría de estos se verían bastante similares: aceptar algún tipo de valor con tipo significativo y producir una acción IO como resultado.

getTime :: (UTCTime -> IO₂) -> IO₂ randomRIO :: Random r => (r,r) -> (r -> IO₂) -> IO₂ findFile :: RegEx -> (Maybe FilePath -> IO₂) -> IO₂

Evidentemente hay un patrón aquí, y será mejor que lo escribamos como

type IO₃ a = (a -> IO₂) -> IO₂ -- If this reminds you of continuation-passing -- style, you''re right. getTime :: IO₃ UTCTime randomRIO :: Random r => (r,r) -> IO₃ r findFile :: RegEx -> IO₃ (Maybe FilePath)

Ahora, eso comienza a parecer familiar, pero todavía estamos lidiando solo con funciones simples poco disimuladas, y eso es arriesgado: cada "acción de valor" tiene la responsabilidad de transmitir la acción resultante de cualquier función contenida (de lo contrario el flujo de control de todo el programa se ve fácilmente interrumpido por una acción de mal comportamiento en el medio). Será mejor que expliquemos ese requisito. Bueno, resulta que esas son las leyes de mónada , aunque no estoy seguro de que realmente podamos formularlas sin los operadores de enlace / unión estándar.

En cualquier caso, ahora hemos alcanzado una formulación de IO que tiene una instancia de mónada adecuada:

data IO₄ a = TxtOut String (IO₄ a) | TxtIn (String -> IO₄ a) | TerminateWith a txtOut :: String -> IO₄ () txtOut s = TxtOut s $ TerminateWith () txtIn :: IO₄ String txtIn = TxtIn $ TerminateWith instance Functor IO₄ where fmap f (TerminateWith a) = TerminateWith $ f a fmap f (TxtIn g) = TxtIn $ fmap f . g fmap f (TxtOut s c) = TxtOut s $ fmap f c instance Applicative IO₄ where pure = TerminateWith (<*>) = ap instance Monad IO₄ where TerminateWith x >>= f = f x TxtOut s c >>= f = TxtOut s $ c >>= f TxtIn g >>= f = TxtIn $ (>>=f) . g

Obviamente, esta no es una implementación eficiente de IO, pero en principio es utilizable.