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




leibniz educatina (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?


Answers

¿Por qué necesitamos mónadas?

  1. Queremos programar solo utilizando 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 va a ejecutar primero ? ¿Cómo podemos formar una secuencia ordenada de funciones (es decir, un programa ) usando nada más que funciones ?

    Solución: componer funciones . Si quieres primero g luego f , simplemente 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 a real), permitamos que g : Real,Real -> Real | Nothing g : Real,Real -> Real | Nothing (función de dos reales en (real o nada)).

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

    Solución: vamos a crear un nuevo tipo de datos para devolver, un " tipo de boxeo " que encierra tal vez un real o simplemente 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" / "enlace" . De esa manera, podemos, detrás de las escenas, adaptar la salida de una función para alimentar a la siguiente.

    En nuestro caso: g >>= f (conectar / componer g a f ). Queremos >>= obtener la salida de g , inspeccionarla y, en caso de que sea Nothing simplemente no llame f y devuelva Nothing ; o por el contrario, extrae la caja Real y alimenta f con ella. (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" (caja diferente, algoritmo de adaptación diferente).

  6. Surgen muchos otros problemas que pueden resolverse utilizando este mismo patrón: 1. Use una "caja" para codificar / almacenar diferentes significados / valores, y tenga funciones como g que devuelven esos "valores en caja". 2. Tener un compositor / vinculador g >>= f para ayudar a conectar la salida de f la entrada de f , por lo que no tenemos 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 resultados diferentes para la misma entrada. Por lo tanto, vamos a marcar esas funciones, haciendo que devuelvan un valor etiquetado / en caja: Mónada IO .

Felicidad total!


Benjamin Pierce dijo en TAPL

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

Es por eso que un lenguaje equipado con un sistema de tipo poderoso 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 tener que 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 sencilla es utilizar la función de filter : filter (> 3) [1..10] , que es igual 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 , tal 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 dejar la lista de la mónada, por lo que todo el cálculo se mantiene puro ( notElem no usa >>= realidad, pero podría). Sin embargo, no es posible dejar la Mónada de E / S de forma segura (es decir, no puede ejecutar una acción de E / S y devolver un valor puro; el valor siempre se incluirá en la Mónada de E / S). Otro ejemplo son las matrices mutables: después de haber abandonado la mónada ST, donde una matriz mutable está activa, ya no se puede actualizar la matriz en un tiempo constante. Así que necesitamos un filtrado monádico desde el 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]

impresiones [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 bajo el capó, es solo un tipo de datos común.

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


No creo que IO deba verse como una mónada particularmente sobresaliente, pero ciertamente es una de las más sorprendentes para los principiantes, así que la usaré para mi explicación.

Construyendo ingenuamente un sistema IO para Haskell

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

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

Con la pereza, esa simple firma es suficiente para construir programas de terminal interactivos, aunque muy limitados. Lo más frustrante es que solo podemos enviar texto. ¿Qué pasa si añadimos 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 desde archivos. ¿Cualquier oportunidad?

Bueno, cuando tomamos nuestro programa main₁ and y simplemente main₁ un archivo al proceso (utilizando 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 un "programa interactivo" String->[Output] , alimenta una cadena obtenida de un archivo y produce un programa no interactivo que simplemente ejecuta el que se proporciona.

Hay un problema aquí: realmente no tenemos una idea de cuándo se lee el archivo. La lista [Output] seguramente da un buen orden a las salidas , pero no obtenemos una orden para cuándo se realizarán las entradas .

Solución: hacer que los eventos de entrada también 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: haga que el resultado de los eventos de entrada también sea algo de tipo IO , no solo de Output . Eso seguro que incluye 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 realmente le permitiría expresar cualquier operación de archivo que desee en un programa (aunque quizás no con un buen rendimiento), pero es un poco complicado:

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

  • Las listas realmente ya no brindan una visión general confiable del flujo del programa: la mayoría de los cálculos subsiguientes solo serán "anunciados" como resultado de alguna operación de entrada. Por lo tanto, también podríamos deshacernos de la estructura de la lista, y simplemente considerar 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ía usar constructores simples para definir todos sus programas. Tendría que haber un buen par de tales constructores fundamentales, pero para la mayoría de las cosas de nivel superior nos gustaría escribir una función con alguna firma agradable de alto nivel. Resulta que la mayoría de estos se verían bastante similares: acepte algún tipo de valor escrito de manera significativa y produzca una acción de E / S 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 es 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 aún estamos tratando solo con funciones planas poco disfrazadas debajo del capó, y eso es arriesgado: cada "valor-acción" 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 interrumpe fácilmente por una acción de mal comportamiento en el medio). Será mejor que hagamos explícito ese requisito. Bueno, resulta que esas son las leyes de la mónada , aunque no estoy seguro de que podamos realmente 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.


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 la asignación 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, el bind y el return deben satisfacer dos ecuaciones (identidades izquierda y derecha), también llamadas leyes de la mónada. (Alternativamente, uno podría definir las mónadas para tener una flattening operation lugar de unir)

La lista de la mónada se usa comúnmente para tratar el no determinismo. La operación de enlace selecciona un elemento de la lista (intuitivamente, todos ellos en mundos paralelos ), le permite al programador realizar algunos cálculos con ellos y luego combina los resultados en todos los mundos en una sola lista (concatenando o aplanando, una lista anidada ). Aquí es cómo 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 un ejemplo de sesión de respuesta:

*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 lista de la mónada no es en modo alguno una computación de efecto secundario. Una estructura matemática que es una mónada (es decir, que se ajusta a las interfaces y leyes mencionadas anteriormente) no implica efectos secundarios, aunque los fenómenos de efectos secundarios a menudo encajan bien en el marco monádico.


La respuesta es, por supuesto, "nosotros no" . 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. La desugaring monádica existente de los bloques do podría reemplazarse con desugaring to bindIO , returnIO , y failIO como se define en el módulo GHC.Base . (No es un módulo documentado sobre hackage, así que tendré que señalar su fuente de documentación). Entonces, no, no hay necesidad de la abstracción de la mónada.

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

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

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 teclea, porque b y Maybe b no son del mismo tipo.

Pero ... es casi correcto. Sólo quieres un poco de libertad de acción. Quieres poder tratar a Maybe b como si fuera básicamente b . Sin embargo, es una mala idea 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 . Por lo tanto, si no puede tratarlos como si fueran del 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 lo ha hecho 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 aumentar un poco los objetos que se componen. Una categoría de Kleisli para Maybe consistiría de (.) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c) e id :: a -> Maybe a . Es decir, los objetos en la categoría aumentan el (->) con un Maybe , por lo que (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 simplemente Maybe . Trabajan con todos los tipos que pueden 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

Mientras pueda probar que su tipo obedece a esas tres leyes, puede convertirlo en una categoría de Kleisli. ¿Y cuál es el problema de 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 la 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 de Monad en el lenguaje? Como mencioné anteriormente, permite la reutilización del código. Incluso permite reutilizar el 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 monad-loops que consiste en bucles que funcionan con cualquier instancia de Monad .

La segunda dimensión es indirecta, pero se desprende de la existencia de la composición. Cuando la composición es fácil, es natural escribir código en trozos pequeños y reutilizables. Esta es la misma forma en que 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 da como resultado la creación de un código reutilizable y el fomento de la creación de un código más reutilizable. La reutilización de códigos 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 general, es decir, un mecanismo para componer funciones, se pueden usar para muchas cosas, lo que lleva a la gente a creer que las mónadas son sobre estado, sobre IO, etc., cuando solo se trata de "componer funciones". ".

Ahora, una cosa interesante acerca de 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 muy agradable de implementar, por ejemplo, una clara separación entre el código puro y el 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 tomar un valor de una "IO a", porque no hay manera de tomar dicho valor mientras se mantiene pura (la función debe estar dentro de la mónada "IO" para usarla tal valor). (NOTA: bueno, nada es perfecto, así que la "camisa de fuerza IO" puede romperse usando "unsafePerformIO: IO a -> a" contaminando así lo que se suponía que era una función pura, pero esto debería usarse muy escasamente y cuando realmente Sepa que no está introduciendo ningún código impuro con efectos secundarios.


Una mónada es una serie de funciones.

(Pst: un conjunto de funciones es solo un cálculo).

En realidad, en lugar de una verdadera matriz (una función en una matriz de celdas) tiene esas funciones encadenadas por otra función >> =. El >> = permite adaptar los resultados de la función i a la función i + 1, realizar cálculos entre ellos o, incluso, no llamar a la función i + 1.

Los tipos utilizados aquí son "tipos con contexto". Esto es, un valor con una "etiqueta". Las funciones encadenadas deben tomar un "valor desnudo" y devolver un resultado etiquetado. Uno de los deberes de >> = es extraer un valor desnudo de su contexto. También está la función "return", que toma un valor desnudo y la coloca con una etiqueta.

Un ejemplo con Maybe . Vamos a usarlo para almacenar un entero simple en el que hacer cálculos.

-- a * b
multiply :: Int -> Int -> Maybe Int
multiply a b = return  (a*b)

-- divideBy 5 100 = 100 / 5
divideBy :: Int -> Int -> Maybe Int
divideBy 0 _ = Nothing -- dividing by 0 gives NOTHING
divideBy denom num = return (quot num denom) -- quotient of num / denom

-- tagged value
val1 = Just 160 

-- array of functions feeded with val1
array1 = val1 >>= divideBy 2  >>= multiply 3 >>= divideBy  4 >>= multiply 3

-- array of funcionts created with the do notation
-- equals array1 but for the feeded val1
array2 :: Int -> Maybe Int
array2 n = do
       v <- divideBy 2  n
       v <- multiply 3 v
       v <- divideBy 4 v
       v <- multiply 3 v
       return v

-- array of functions, 
-- the first >>= performs 160 / 0, returning Nothing
-- the second >>= has to perform Nothing >>= multiply 3 ....
-- and simply returns Nothing without calling multiply 3 ....
array3 = val1 >>= divideBy 0  >>= multiply 3 >>= divideBy  4 >>= multiply 3

main = do
     print array1
     print (array2 160)
     print array3

Solo para mostrar que las mónadas son una serie de funciones con operaciones de ayuda, considere el equivalente al ejemplo anterior, simplemente usando una serie real de funciones

type MyMonad = [Int -> Maybe Int] -- my monad as a real array of functions

myArray1 = [divideBy 2, multiply 3, divideBy 4, multiply 3]

-- function for the machinery of executing each function i with the result provided by function i-1
runMyMonad :: Maybe Int -> MyMonad -> Maybe Int
runMyMonad val [] = val
runMyMonad Nothing _ = Nothing
runMyMonad (Just val) (f:fs) = runMyMonad (f val) fs

Y sería usado así:

print (runMyMonad (Just 160) myArray1)




haskell monads