Mónada (programación funcional)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En la programación funcional , una mónada (monad en inglés), es una estructura que representa cálculos definidos como una secuencia de pasos. Un tipo de dato con una estructura mónada define lo que simboliza en un bloque de código, o anida funciones del mismo tipo. Esto le permite al programador crear tuberías informáticas que procesen datos en pasos, en los cuales cada acción es ajustada a un Decorator (patrón de diseño) junto con reglas de proceso adicionales provistas por la mónada.[1] Por lo tanto, las mónadas han sido descritas como un “punto y coma programable”; un punto y coma, siendo el operador usado para unir varias declaraciones en la programación imperativa,[1] en consecuencia la expresión implica que código extra será ejecutado entre las declaraciones de una tubería. Las mónadas también han sido explicadas con un metáfora física, donde se comportan como una línea de ensamblaje, en las que un objeto transporta datos entre unidades funcionales que la van transformando un paso a la vez.[2] También se les puede ver como un patrón de diseño funcional para construir tipos genéricos.[3]

Los programas puramente funcionales pueden usar las mónadas para estructurar procedimientos que incluyan operaciones en secuencia como aquellos encontrados en la programación estructurada.[4] [5] Muchos conceptos de programación comunes pueden ser descritos en términos de estructuras de mónadas, incluyendo los efectos secundarios, la Entrada/salida, asignación de variables, el manejo de excepciones, el analizador sintáctico, la programación no determinística, concurrencia y continuaciones. Esto permite que tales conceptos sean definidos en maneras puramente funcionales sin el uso de extensiones a la semántica del lenguaje. Los lenguajes como Haskell proveen mónadas en el núcleo estándar, permitiendo a los programadores reusar largas partes de su definición formal y aplicar en diversas librerias las mismas interfaces para combinar funciones.[6]

Formalmente , una mónada consiste de un constructor de tipo M y dos operaciones , unir y retorno (donde retorno es a veces conocido como unidad). Las operaciones deben cumplir con ciertas propiedades para permitir la composición correcta de funciones mónadicas (es decir, funciones que usen valores de la mónada como sus argumentos o valores de retorno). La operación retorno toma una valor de un tipo plano y lo pone en un contenedor mónadico usando el constructor, creando así un valor mónadico. La operación unir realiza el proceso inverso, extrayendo el valor original del contenedor y pasándolo a la siguiente función asociada en la tubería, posiblemente con chequeos adicionales y transformaciones. Dado que una mónada puede insertar operaciones adicionales en el dominio lógico del programa, se les puede considerar como un tipo de programación orientada a aspectos.[7] La lógica de negocio puede ser definida por la programación de aplicaciones en la tubería, mientras que las operaciones a ser repetidas muchas veces pueden ser operadas por una mónada predefinida construida previamente .

El nombre y concepto viene del epónimo (mónada) en la teoría de categorías, donde las mónadas son un tipo de funtor, o sea un mapeo entre categorías; aunque el término mónada en el contexto de la programación funcional es usualmente tomado como correspondiente al término mónada fuerte en la teoría de categorías.[8]

Historia[editar]

El concepto de mónada en la programación apareció en los 80 en el lenguaje Opal, aunque se le llamaban “comandos” y nunca fueron formalmente especificados. Eugenio Moggi fue el que por primera vez describió el uso general de las mónadas para estructurar programas en 1991.[8] Mucha gente continuó su trabajo, incluyendo investigadores de lenguajes de programación como Philip Wandler y Simon Peyton Jones (los cuales estuvieron involucrados en la especificación de Haskell) Versiones tempranas de Haskell usaron una problemática “lista perezosa” para I/O, y Haskell 1.3 introdujo mónadas de una manera más flexible al combinar I/O con evaluación perezosa.

En adición al I/O, los investigadores de los lenguajes de programación y diseñadores de librerías de Haskell han exitosamente aplicado las mónadas a evaluadores sintácticos y a intérpretes de lenguajes de programación. El concepto de las mónadas junto con el de la notación do- de Hakell ha sido generalizada para formar funtores aplicativos y flechas.

Por un largo tiempo, Haskell y sus derivados han sido los únicos usuarios mayores de mónadas en la programación. También existen formulaciones en Scheme, Perl, Python, Racket, Clojure y Scala, donde las mónadas se han presentado como una opción de diseño de un nuevo lenguaje de programación. Recientemente F# ha incluido la característica de contener expresiones de cómputo o workflows, los cuales son un intento por introducir las construcciones monádicas dentro de una sintaxis más palpable a los programadores con un experiencia en los lenguajes imperativos.[9]

Ejemplos motivantes[editar]

El lenguaje de programación Haskell, es un lenguaje funcional que hace un uso intensivo de mónadas e incluye azúcar sintáctico para hacer la composición de mónadas más conveniente. Todos los ejemplos de código escritos aquí son escritos en Haskell, a menos que se indique lo contrario.

Se demuestran dos ejemplos comunes en la introducción a las mónadas: la mónada Maybe y la mónada I/O. Las mónadas están desde luego, no recluidas al lenguaje Haskell, el segundo ejemplo muestra la mónada Writer en JavaScript.


La mónada Maybe[editar]

Considérese al opción de tipo Maybe a, (talvez un), representando un valor que es o un valor del tipo a , o ninguno. Para distinguirlos, se tienen dos constructores de tipo de dato algebraico: Solo t, conteniendo el valor t, or Nada, sin contenido.

data Maybe t = Solo t | nada

Nos gustaría poder usar este tipo como una simple excepción checada: en cualquier punto del cómputo, éste puede fallar, lo que causa que el resto del proceso sea saltado y que el resultado final sea Nada. Si todos los pasos del cómputo son exitosos, entonces el resultado final es Solo x para un valor x.

En el siguiente ejemplo, suma es una función que toma dos argumentos del tipo Maybe int, y regresa un resultado del mismo tipo. Si ambas mx y my tienen Solo valores, queremos regresar Solot su suma; pero si mx o my son Nada, queremos regresar Nada. Si ilusamente intentamos escribir funciones con este tipo de conducta, terminaremos con una serie de casos "if Nada then Nada else do algo con x en Solo x" que rápidamente se volverán confusos:[1]

suma :: Maybe Int -> Maybe Int -> Maybe Int
suma mx my =
  case mx of
    Nonthing -> Nothing
    Just x  -> case my of
                 Nothin -> Nothing
                 Just y  -> Just (x + y)

Para aliviar esto, podemos definir operaciones para encadenar tales cómputos de manera conjunta. El operador binario bind (unir) (>>=) encadena los resultados de un cómputo que pudiera fallar, a una función que elige otro cómputo que pudiera fallar. Si el argumento es Nothing, (nada), el segundo argumento (la función) es ignorada y la operación entera simplemente falla. Si el argumento es Just x, (Solo x), pasamos x a la función para obtener un nuevo valor Maybe, que puede o no ser el resultado en un valor del tipo Just (Solo).

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing  >>= _  =  Nothing    -- Un cómputo fallido regresa Nada
(Just x) >>= f  =  f x        -- Aplica la función f al valor x

Usando un poco de Azúcar sintáctica , conocida como notación-do, el ejemplo puede ser escrito como:

suma :: Maybe Int -> Maybe Int -> Maybe Int
suma mx my = do
  x <- mx
  y <- my
  return (x + y)

Dado que este tipo de operación es muy común, existe una función estándar en Haskell (liftM2) que toma dos valores mónadicos (aquí: dos Maybes) y combina sus contenidos (dos números) usando otra función (adición), haciendo posible escribir el ejemplo pasado como:

add :: Maybe Int -> Maybe Int -> Maybe Int
add = liftM2 (+)

La mónada escritora[editar]

La mónada escritora permite que un proceso lleve información adicional “al lado” de su valor de cómputo. Esto puede ser útil para el registro de errores o el debugging de la información que no es el resultado primario.[10]

El siguiente ejemplo implementa la mónada escrita en JavaScript:

Primero, una mónada escritora es definida. La función unidad crea un nuevo tipo de valor de un tipo básico, el cual lleva una cadena de registro; y bind aplica la función a un valor viejo, y finalmente regresa el nuevo valor de resultado con un registro expandido. Los corchetes trabajan aquí como el constructor de tipo de la mónada, creando un valor de tipo mónadico para la mónada escritora, hecha de componentes más simples (el valor en la posición 0 del arreglo, y la cadena de registro en la posición 1).

var unit = function(value) { return [value, ''] };
var bind = function( valorMonadico, transformaConRegistro) {
    var value  = valorMonadico0],
        registro = valorMonadico[1],
        result = transformaConRegistro(value);
    return [ result[0], regisrtro+ result[1] ];
};

Tubería es una función auxiliar que concatena una secuencia de binds aplicados a un arreglo de funciones.

var tuberia = function(monadicValue, functions) {
    for (var key in functions) {
        monadicValue = bind(monadicValue, functions[key]);
    }
    return monadicValue;
};

Ejemplos de funciones que regresen valores del tipo esperados por la mónada escritora de arriba:

var squared = function(x) {
    return [x * x, 'al cuadrado.'];
};
 
var halved = function(x) {
    return [x / 2, 'a la mitad.'];
};

Finalmente, un ejemplo del uso de la mónada para crear una tubería de funciones matemáticas, con información de debug al lado.

pipeline(unit(4), [squared, halved]); // [8, "al cuadrado.a la mitad"]
 
=== La mónada I/O ===
En un lenguaje [[puramente funcional]], como Haskell, las funciones no pueden tener efectos externos visibles como parte de la semántica de la función. Aunque una función no puede directamente causar un efecto, puede contruir un valor ''describiendo'' un efecto deseado, que el llamante puede aplicar a un tiempo conveniente. .<ref>[[Simon Peyton Jones|Peyton Jones, Simon L.]]; Wadler, Philip. [http://citeseer.ist.psu.edu/peytonjones93imperative.html Imperative Functional Programming]. Conference record of the Twentieth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Charleston, South Carolina. 1993</ref> En la notación Haskell, un valor de tipo ''IO a'' representa una acción que, a la hora de ser realizada , produce un valor de tipo ''a'''.
 
Podemos pensar en un valor de tipo <code>IO</code> como una ''acción'' que toma como su argumento el estado actual del mundo, y que regresara un nuevo mundo donde el estado ha sido cambiado de acuerdo al valor de retorno de la función. Por ejemplo, las funciones <code>doesFileExist</code>  (existe el archivo?) y <code>removeFile</code> (remueve el archivo) en la librería estándar de Haskell tienen los siguientes tipos 
 
<source lang="haskell">
doesFileExist :: FilePath -> IO Bool
removeFile :: FilePath -> IO ()

Así que uno puede pensar removeFile como una función que, dado un FilePath, regresa una acción IO ; esta acción se encargará de que el mundo, en este caso el sistema de archivos, no tendrá un archivo nombrado por tal FilePath cuando sea ejecutado. Aquí el valor interno IO es del tipo () que significa que el llamante no está interesado en otros resultados. Por otra parte, en doesFileExist, la función regresa una acción IO que envuelve a un valor booleano True o False; esto conceptualmente representa un nuevo estado del mundo donde el llamante sabe por cierto que un FilePath está presente o no dentro del sistema de archivos en el momento que la acción fue realizada. El estado del mundo manejado de esta manera puede ser pasado de acción a acción, y de tal manera definir una serie de acciones que serán aplicadas en orden de pasos de cambio de estados. Este proceso es similar a como la lógica temporal representa el paso del tiempo usando solo propocisiones declarativas. El siguiente ejemplo clarifica en detalle como este encadenamiento de acciones ocurre en un programa.

Nos gustaría ser capaces de describir todos los tipos básicos de operaciones I/O, por ejemplo, escribir texto a una salida estándar, leer de una entrada estándar, leer y editar archivos, mandar datos sobre redes, etc. En adicipon, necesitamos ser capaces de componer estas primitivas para formar programas más grandes. Por ejemplo, nos gustaría escribir :

main :: IO ()
main = do
  putStrLn "Cual es tu nombre?"
  name <- getLine
  putStrLn ("Gusto en conocerte, " ++ name ++ "!")

¿Cómo formalizar esta notación intuitiva? Para hacerlo, necesitamos ser capaces de realizar operaciones básicas de I/O:

  • Debemos poder secuenciar dos operaciones I/O. En Haskell, esto es escrito como el operador infix >>, de tal manera que putStrLn "abc" >> putStrLn "def" sea un acción I/O que imprima dos líneas de texto hacia la consola. El tipo de >> es IO a → IO b → IO b, significando que el operador toma dos operaciones I/O y regresa una tercera que secualiza las dos y regresa el valor de la segunda.
  • Debemos tener una acción I/O que haga nada. Es decir, regrese un valor pero no tenga efectos. En Haskell, este constructor es llamado return; tiene tipo a → IO a.
  • Más sútilmente, deberíamos poder determinar nuestra próxima acción basado en los resultados de la acción previa. Para hacer esto, Haskell tiene un operador >>= (pronunciado bind) con tipo IO a → (a → IO b) → IO b. Es decir, el operando de la izquierda es una acción I/O que regresa un valor del tipo a; el operando en la derecha es una función que puede tomar un acción I/O basada en el valor producido por la acción de la izquierda. La acción resultante combinada, al ser realizada, hace la primera acción, después evalúa la función con el valor de regreso de la primera y después realiza la segunda acción, finalmente regresa el valor de la segunda acción.
Un ejemplo del uso de este operador en Haskell sería getLine >>= putStrLn, el cual lee una sola línea de texto de una entrada estándar y la manda a la salida estándar. Notar que el primer operador, >>, es solo un caso especial de este operador en el que el valor de regreso de la primera acción es ignorado y la segunda acción seleccionada es siempre la misma.

No es necesariamente obvio que las tres operaciones precedentes, junto con set de operaciones I/O nos ayudan a definir cualquier acción de programa, incluyendo las transformaciones de datos, control de flujo y control de flujo recursivo. Podemos escribir el ejemplo de arriba como una sola expresión.

main =
  putStrLn "Cual es tu nombre?" >> 
  getLine >>= \name ->
  putStrLn ("Gusto en conocerte " ++ name ++ "!")

La estructura de tubería del operador bind se asegura de que 'getLine y putStrLn sean evaluadas una sola vez y en el orden requerido, para que así los efectos de extraer el texto de la entrada y escribir a la salida sean correctamente ejecutadas en la tubería funcional. Esto permanece cierto aún si el lenguaje realiza evaluación de funciones fuera de orden o una evaluación perezosa.

Claramente , existe una estructura común entre las definiciones I/O y las Maybe, aún si son diferentes en muchas maneras. Las mónadas son una abstracción de las estructuras antes descritas, de estructuras similares y de sus semejanzas. El concepto general de mónadas incluye una situación donde el programador quiere llevar a cabo un cómputo puramente funcional mientras que un cómputo relacionado se lleva a cabo al lado.

Definición Formal[editar]

Una mónada es una construcción que, dada un tipo de sistema, embebe uno correspondiente (llamo el tipo de sistema mónadico). Tal tipo de sistema mónadico preserva todos los aspectos significativos del tipo de sistema subyacente, mientras que también le añade características particulares de la mónada.[note 1]

La formulación usual de una mónada para programación es conocida como una Kleisli triple, y tiene los siguientes componentes:

  1. Un tipo de constructor que define, para cada tipo subyacente, el como obtener un correspondiente tipo mónadico. En la notación de Haskell, el nombre de la mónada representa el tipo de constructor.

Si M es el nombre de la mónada y t es un tipo de datom entonces M t' es el correspondiente tipo en la mónada.

  1. Una función unidad que mapeé un valor de un tipo subyacente aun valor en el correspondiente tipo monádico. La función unidad tiene el tipo polimórfico t→M t. El resultado es normalmente el valor más simple en el tipo correspondiente que completamente preserva el valor original. En Haskell, esta función es llamada return debido a la manera en que es usada en la notación-do.
  2. Un operador union de tipo polimórfico (M t)→(t→M u)→(M u), el cual Haskell representa con el operador de notación de infijo >>=. Su primer argumento es un valor de tipo monádico, su segundo argumento es una función que mapea el tipo subyacente del primer argumento a otro tipo monádico. Típicamente, el operador unión puede ser entendido en 4 etapas:
    1. La estructura relacionada a la mónada en el primer argumento es atravesada para exponer cualquier número de valores en el tipo subyacente t.
    2. La función dada es aplicada a todos esos valores para obtener valores de tipo (M u).
    3. La estructura de la mónada en tales valores también es atravesada para revelar valores de tipo u.
    4. Finalmente, la estructura relacionada a la mónada es reensamblada con todos los resultados, dando así un solo valor de tipo (M u).

Dado un constructor de tipo M, en la mayoría de los contextos, un valor de tipo M a puede ser pensado como una acción que regresa un valor de tipo a. La operación de retorno toma un valor del tipo plano a y lo pone en un contenedor mónadico de tipo M a; la operación union encadena el valor mónadico de tipo 'M a con una función de tipo a → M b para crear un valor mónadico de tipo M b.

Leyes Monádicas[editar]

Para que una mónada se comporte de la manera correcta, sus definiciones deben seguir ciertos axiomas, los cuales en su conjunto son llamados leyes mónadicas.[11] El símbolo ≡ indica equivalencia entre dos expresiones de Haskell en el siguiente texto.

  • return actúa aproximadamente como un elemento neutral de >>=, en que:
    • (return x) >>= f   ≡   f x
    • m >>= return   ≡   m
  • El unir dos funciones en sucesión es lo mismo que unir una función que puede ser determinada desde ellas:
    • (m >>= f) >>= g   ≡   m >>= ( \x -> (f x >>= g) )

Los axiomas también pueden ser mostrados usando las expresiones en la notación-do:

  • do { f x }   ≡   do { v <- return x; f v }
  • do { m }   ≡   do { v <- m; return v }
  • do { x <- m; y <- f x; g y }   ≡   do { y <- do { x <- m; f x }; g y }

o usando el operador monádico de composición, (f >=> g) x = (f x) >>= g:

  • return >=> g   ≡   g
  • f >=> return   ≡   f
  • (f >=> g) >=> h   ≡   f >=> (g >=> h)

fmap y join[editar]

Aunque Haskell define a las mónadas en términos de las funciones return y union, también es posible definir una mónada en términos de retorno y otras dos operaciones, join (juntar) y fmap. Esta formulación se encuentra más apegada con la definición de mónadas en la teoría de categorías. La operación fmap, con tipo (tu) → M t→M u,[12] toma una función entre 2 tipos y produce una función que hace la misma cosa a los valores en la mónada. La operación join, con tipo M (M t)→M t, aplana dos capas de información mónadica en una sola.

Las dos formulaciones son mostradas:

fmap f m = m >>= (return . f)
join n = n >>= id
 
m >>= g   ≡   join (fmap g m)

Aquí, m tiene el tipo M t,n tiene el tipo M ( M r), f tiene el tipo tu, y g tiene el tipo t → M v, donde t, r, u y v son tipos subyacentes.

La función retorno caracteriza los funtores apuntados en la misma categoría, usando para esto la habilidad de cargar valores en el funtor. Se debe satisfacer la siguiente ley:

return . f   ≡   fmap f . return

En adición , la función join caracteriza las mónadas:

join . fmap join = join . join
join . fmap return = join . return = id
join . fmap (fmap f) = fmap f . join

Mónadas aditivas[editar]

Una mónada aditiva es una mónada provista con un cero mónadico mzero y un operador binario mplus que satisface las leyes mónadicas, usando el cero mónadico como unidad. El operador mplus tiene el tipo M tM tM t (donde M es el constructor mónadico y t es el tipo de dato subyacente), satisface la ley asociativa y tiene el cero como identidad en la izquierda y la derecha. (Por lo tanto, una mónada aditiva es también un monoide).

El unir el mzero con cualquier función produce el cero para el tipo de resultado, justo como el multiplicar 0 por cualquier numero da 0.

mzero >>= f   ≡   mzero

Similarmente, unir cualquier m con una función que siempre regresa un 0, resulta en un 0.

m >>= (\x -> mzero)   ≡   mzero

Intuitivamente, el cero representa un valor en la mónada que tiene una estructura exclusivamente relacionada a la mónada y que no tiene valores de tipo subyacente. En la mónada Maybe, Nothing (Nada) es un cero. En la mónada Lista, [ ] (la lista vacía) es también un cero.

Azúcar sintáctica notación-do[editar]

Aunque hay ocasiones en las que tiene sentido usar el operador union >>= directamente en un programa, es más típico usar la llamada notación-do (performn-notation en Ocaml, expresiones de computación en F Sharp, que mimetiza la apariencia de los lenguajes imperativos. El compilador traduce la notación-do a expresiones que incluyen >>=. Por ejemplo, el siguiente código:


a = do x <- [3..4]
       [1..2]
       return (x, 42)

es transformado durante la compilación a:

a = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))

Es útil ver la implementación de la mónada lista. Y saber que concatMap mapea una función sobre una lista y concatena (aplana) las listas resultantes:

instance Monad [] where
  m >>= f  = concat (map f m)
  return x = [x]
  fail s   = []

Por lo tanto, las siguientes transformaciones se mantienen y todas las expresiones siguientes son equivalentes:


a = [3..4] >>= (\x -> [1..2] >>= (\_ -> return (x, 42)))
a = [3..4] >>= (\x -> concatMap (\_ -> return (x, 42)) [1..2] )
a = [3..4] >>= (\x -> [(x,42),(x,42)] )
a = concatMap (\x -> [(x,42),(x,42)] ) [3..4]
a = [(3,42),(3,42),(4,42),(4,42)]

Nótese que la lista [1..2] no es usada. La falta de flecha apuntando a la izquierda, traducida a una función de unión que ignora su argumento, indica que solo la estructura mónadica es de interés, no los valores dentro de ella. Por ejemplo, para una mónada estado esto puede ser usado para cambiar su estado sin producir más valores. El bloque de notación-do puede ser usado con cualquier mónada ya que solo es azúcar sintáctica para: >>=. Las siguientes definiciones para la división segura de valores en la mónada Maybe también son equivalentes:


x // y = do
  a <- x  -- Extraer los valores de x e y , si es que tienen
  b <- y
  if b == 0 then Nothing else Just (a / b)
 
x // y = x >>= (\a -> y >>= (\b -> if b == 0 then Nothing else Just (a / b)))

Un ejemplo similar en F# usando una expresión de computación:

let readNum () =
  let s = Console.ReadLine()
  let succ,v = Int32.TryParse(s)
  if (succ) then Some(v) else None
 
let secure_div = 
  maybe { 
    let! x = readNum()
    let! y = readNum()
    if (y = 0) 
    then None
    else return (x / y)
  }

El azúcar sintáctica del bloque maybe sería traducido internamente a la siguiente expresión:

maybe.Delay(fun () ->
  maybe.Bind(readNum(), fun x ->
    maybe.Bind(readNum(), fun y ->
      if (y=0) then None else maybe.Return( x/y ))))

Funciones mónadicas genéricas[editar]

Dados los valores producidos por la división segura, podríamos querer seguir haciendo cálculos sin tener que checar manualmente si son Nothing (es decir el resultado de intentar hace runa división por 0). Podemos hacer lo anterior usando una función levantante , la cual podemos definir no solo para la mónada Maybe sino también para mónadas arbitrarias. En Haskell esto es llamado liftM2:

liftM2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
liftM2 op mx my = do
    x <- mx
    y <- my
    return (op x y)

Recuerde que las flechas en un tipo se asocian a la derecha, así que liftM2 es una función que toma una función binaria como argumento y regresa otra función binaria. El tipo signature dice: Si m es una mónada, podemos levantar cualquier función binaria por encima de ella. Por ejemplo:

(.*.) :: (Monad m, Num a) => m a -> m a -> m a
x .*. y = liftM2 (*) x y

define un operador (.*.) el cual multiplica dos números, a menos que uno de ellos sea Nothing (en cuyo caso regresa Nothing). La ventaja aquí es que no necesitamos adentrarnos en los detalles de la implementación de la mónada; si necesitamos hacer los mismo con otra función, o en otra mónada, el usar liftM2 hace inmediatamente claro lo que se intenta hacer.

Matemáticamente, el operador liftM2 está definido por:

\text{liftM2} \colon \forall M \colon \text{monad}, \; (A_1 \to A_2 \to R) \to M \, A_1 \to M \, A_2 \to M \, R =  op \mapsto m_1 \mapsto m_2 \mapsto \text{bind} \; m_1 \; (a_1 \mapsto \text{bind} \; m_2 \; (a_2 \mapsto \text{return} \; (op \, a_1 \, a_2)))

Otros ejemplos[editar]

Mónada identidad[editar]

La mónada más simple es la mónada identidad, la cual no añade información a los valores.

Id t = t
return x = x
x >>= f = f x

Un bloque-do en esta mónada realiza substitución de variables; do {x <- 2; return 3*x} resulta en 6.

Desde el punto de vista de la teoría de categorías, la mónada identidad deriva de la unión entre funtores identidad.

Colecciones[editar]

Algunos tipos familiares de colección, incluyendo las listas, los sets y multisets, son mónadas. La definición para las listas están dadas aquí.


-- "return" construye una lista de un elemento
return x = [x]
-- "bind" concatena las listas obtenidas al aplicar f a cada elemento en las list xs
xs >>= f = concat (map f xs)
-- El obejto cero es una lista vacía
mzero = []

Las listas de comprensión, son un aplicación especial de la mónada lista. Por ejemplo, la lista comprensión [ 2*x | x <- [1..n], isOkay x] corresponde al cómputo en la mónada lista do {x <- [1..n]; if isOkay x then return (2*x) else mzero;}.


La notación de listas de comprensión es similar a la notación de constructor de set, pero un set no puede ser convertido en una mónada, ya que hay una restricción en el tipo de cómputo a ser comparable por igualdad, mientras que una mónada no pone ninguna restricción en los tipos de cómputo. De hecho, el set es un mónada restringida.[13]

Las mónadas de colecciones representan naturalmente un algoritmo no determinista. La lista (u otra colección) representa todos los posibles resultados de diferentes caminos no determinísticos de cómputo en ese momento. Por ejemplo, cuando uno ejecuta x <- [1,2,3,4,5], uno dice que la variable x puede de manera no determinística tomar cualquiera de los valores de la lista. Si uno regresara x se evaluara con una lista de resultados de cada camino de cómputo. Nótese que el operador unión de arriba sigue tal tema al realizar f en cada uno de los resultados posibles y después concatena las listas resultantes.

Las declaraciones como if condition x y then return () else mzero son usualmente vistas; si la condición es verdad, la opción no determinística se realiza desde un camino dummy de cómputo, el cual regresa un valor que no asignamos a nada; sin embargo, si la condición es falsa, entonces la mónada de valor no determinístico mzero = [] escoge desde 0 valores, terminando así efectivamente tal camino de cómputo. Otros caminos de cómputo pueden todavía tener éxito. Esto sirve como una guarda para asegurar que solo los caminos de cómputo que satisfacen ciertas condiciones puedan continuar. Así que las mónadas colección son muy útiles para resolver puzzles lógicos, Sudoku, y problemas similares.

En un lenguaje con evaluación perezosa, como Haskell, una lista es evaluada solo en el grado en que sus elementos son requeridos: por ejemplo, si uno pide el primer elemento de una lista, solo el primer elemento será computado. Con respecto al uso de la mónada lista para cómputos no determinísticos, esto significa que podemos generar no determinísticamente una lista perezosa de todos los resultados del cómputo, después pedir el primero de ellos, y solo se realizará tanto trabajo sea necesario para obtener el primer resultado. El proceso vagamente corresponde a regresarse: un camino es escogido, después falla en cierto punto ( si es que se evalúa mzero), posteriormente se regresa al último punto de ramificación, y sigue el otro camino, y así hasta terminar. Si el segundo elemento es pedido, se vuelve a hacer solo el trabajo necesario para obtener la segunda solución. De tal manera que la mónada lista es una manera sencilla de implementar un algortimo de regreso en un lenguaje perezoso.

Desde el punto de vista de la teoría de las categorías, las mónadas colección son derivadas una unión de funtores entre uno libre y uno subyacente entre la categoría de conjuntos y la categoría de magma (categoría). Tomando diferentes tipos de magmas, obtenemos diferentes tipos de colecciones, como se muestra en la tabla de abajo:

Tipos de colecciones Tipos de monoides
lista monoide
multiset finito monoide conmutativo
set finito monoide conmutativo idempotencia
permutación finita monoide conmutativo idempotencia

Mónadas estado[editar]

Una mónada estado le permite a un programador añadir información de estado de cualquier tipo de cálculo. Dado cualquier tipo de valor, el tipo correspondiente en la mónada estado es una función la cual acepta estado y después regresa un nuevo estado (de tipo s) junto con un valor de retorno (de tipo t).

type State s t = s -> (t, s)

Nótese que en esta mónada, a comparación de las ya vistas, toma un parámetro tipo, osea el estado de tipo de la información. Las operaciones de la mónada se definen de la siguiente manera:

-- "return" produce el valor dado sin cambiar el estado.
return x = \s -> (x, s)
-- "bind" modifica m para que aplique a f su resultado
m >>= f = \r -> let (x, s) = m r in (f x) s

Operaciones útiles de estado incluyen:

get = \s -> (s, s) – Examina el estado en este punto del cómputo
put s = \_ -> ((), s) – Reemplaza el estado
modify f = \s -> ((), f s) – Actualiza el estado

Otra operacipon aplica una mónada estado a un valor inicial dado:

runState :: State s a -> s -> (a, s)
runState t s = t s

Los bloques-do en una mónada estado son secuencias de operaciones que pueden examinar y actualizar los datos de estado.

Informalmente , una mónada estado de tipo S mapea el tipo de valores de retorno T en funciones de tipo S \rarr T \times S, donde S es el estado subyacente. La función return es simplemente:

\text{return} \colon T \rarr S \rarr T \times S = t \mapsto s \mapsto (t, s)

La función bind (union) es:

\text{bind} \colon (S \rarr T \times S) \rarr (T \rarr S \rarr T' \times S) \rarr S \rarr T' \times S \ = m \mapsto k \mapsto s \mapsto (k \ t \ s') \quad \text{where} \; (t, s') = m \, s.

Desde el punto de vista de la teoría de las categorías, una mónada estado es derivada de la conjunción entre el funtor producto y el funtor exponencial, el cual existe en cualquier categoría cartesiana cerrada por definición.

Mónada ambiente[editar]

La mónada ambiente (también llamada “mónada lectora” y “mónada función”) permite que un computo dependa de los valores de un ambiente compartido . El constructor de tipo de mónada mapea un tipo T a funciones de tipo ET', donde E es el tipo del ambiente compartido. Las funciones mónadas son: \text{return} \colon T \rarr E \rarr T = t \mapsto e \mapsto t

\text{bind} \colon (E \rarr T) \rarr (T \rarr E \rarr T') \rarr E \rarr T' = r \mapsto f \mapsto e \mapsto f \, (r \, e) \, e

Las siguiente operaciones monádicas son las siguientes:

\text{ask} \colon E \rarr E = \text{id}_E
\text{local} \colon (E \rarr E) \rarr (E \rarr T) \rarr E \rarr T = f \mapsto c \mapsto e \mapsto c \, (f \, e)

La operación “ask” es usada para recuperar el contexto actual, mientras que local ejecuta una computación en un subcontexto modificado. Como en la mónada estado, los cómputos en la mónada ambiente pueden ser invocados al simplemente proveer un valor de ambiente y aplocarlo a una instancia de la mónada.

Mónada escritora[editar]

La mónada escritora le permite a un programa hacer computos de varios tipos de salidas auxiliares que pueden ser “compuestas” o “acumuladas” paso a paso, en adición al resultado general de la computación. Es usualmente requerida para capturar información. Dado el tipo subyacente T un valor en la mónada escritora tiene tipo W× T, donde W es un tipo con la operación adjuntada que satisface las leyes monóides. Las funciones mónadas son simplemente:

\text{return} \colon T \rarr W \times T = t \mapsto (\epsilon, t)
\text{bind} \colon (W \times T) \rarr (T \rarr W \times T') \rarr W \times T' = (w, t) \mapsto f \mapsto (w * w',\, t') \quad \text{where} \; (w', t') = f \, t

donde ε y * son los elementos identidad del monoíde W y su operación asociada.

La operación mónadica “tell” está definida por: :\text{tell} \colon W \rarr (W \times 1) = w \mapsto (w, ()) Donde 1 y () denotan el tipo unidad y su elemento trivial. Es usada en combinación con bind para actualizar el valor auxiliar sin afectar el computo principal.

Mónada continuación[editar]

Una mónada continuación con tipo de retorno R mapea el tipo T en funciones de tipo \left( T \rarr R \right) \rarr R. Es usada para modelar el estilo de continuación de paso. Las funcinoes return y bind son las siguientes:

\text{return} \colon T \rarr \left( T \rarr R \right) \rarr R = t \mapsto f \mapsto f \, t
\text{bind} \colon \left( \left( T \rarr R \right) \rarr R \right) \rarr \left( T \rarr \left( T' \rarr R \right) \rarr R \right) \rarr \left( T' \rarr R \right) \rarr R= c \mapsto f \mapsto k \mapsto c \, \left( t \mapsto f \, t \, k \right)

La función llamada con-continuación actual está definida de la siguiente manera:

\text{call/cc} \colon \left( \left( T \rarr \left( T' \rarr R \right) \rarr R \right) \rarr \left( T \rarr R \right) \rarr R \right) \rarr \left( T \rarr R \right) \rarr R = f \mapsto k \mapsto \left( f \left( t \mapsto x \mapsto k \, t \right) \, k \right)

Otros[editar]

Otros conceptos que los investigadores han expresado como mónada incluyen:

Co-mónadas[editar]

Las co-mónadas son el dual categórico de las mónadas. Son definidas por un tipo de constructor W T y dos operaciones: extract (extraer) con tipo W TT para cualquier T, y extend con tipo (W TT' ) → W T → W T' . Las operaciones extract y extend deben satisfacer las leyes:

\text{extend} \,\, \text{extract} = \text{id}
\text{extract} \circ (\text{extend} \, f) = f
(\text{extend} \, f) \circ (\text{extend} \, g) = \text{extend} \, (f \circ (\text{extend} \, g))

Alternativamente las co-mónadas pueden ser definidas en términos de las operacinoes fmap, extract y duplicate. Las operaciones fmap y extract definen W, como el funtor coapuntado. La operación duplicate caracteriza a las co-mónadas: Tiene el tipo W T → W (W T) y sastisface las siguientes leyes:

\text{extract} \circ \text{duplicate} = \text{id}
\text{fmap} \, \text{extract} \circ \text{duplicate} = \text{id}
\text{duplicate} \circ \text{duplicate} = \text{fmap} \, \text{duplicate} \circ \text{duplicate}

Las dos formulaciones son relacionadas de la siguiente manera:

\text{fmap}: (A \rarr B) \rarr \mathrm{W} \, A \rarr \mathrm{W} \, B = f \mapsto \text{extend} \, (f \circ \text{extract})
\text{duplicate}: \mathrm{W} \, A \rarr \mathrm{W} \, \mathrm{W} \, A = \text{extend} \, \text{id}
\text{extend}: (\mathrm{W} \, A \rarr B) \rarr \mathrm{W} \, A \rarr \mathrm{W} \, B = f \mapsto (\text{fmap} \, f) \circ \text{duplicate}

Mientras que las mónadas representan los efectos, una mónada W representa un tipo de contexto. Las funciones extract extraen un válor de éste contexto. Mientras que la función extend puede ser usada para componer una tubería de funciones dependientes del contexto de tipo W AB.

Co-mónada identidad[editar]

La co-mónada identidad es la más simple de las co-mónadas: mapea el tipo T a sí mismo. El operador extract' es la identidad y el operador extend es la función de aplicación.


Co-mónada producto[editar]

El co-mónada producto mapea el tipo T en tuplas de tipo C \times T, donde C es el tipo contexto de la co-mónada. Las operaciones co-mónadas son:

\text{extract}: (C \times T) \rarr T = (c, t) \mapsto t
\text{extend}: ((C \times A) \rarr B) \rarr C \times A \rarr C \times B = f \mapsto (c, a) \mapsto (c, f \, (c, a))
\text{fmap}: (A \rarr B) \rarr (C \times A) \rarr (C \times B) = (c, a) \mapsto (c, f \, a)
\text{duplicate}: (C \times A) \rarr (C \times (C \times A)) = (c, a) \mapsto (c, (c, a))

Función co-mónada[editar]

La función co-mónada mapea tipo T en funciones de tipo M \rarr T, donde M es un tipo de conjunto con estructura monoide. Las operaciones co-mónadas son:

\text{extract}: (M \rarr T) \rarr T = f \mapsto f \, \varepsilon
\text{extend}: ((M \rarr A) \rarr B) \rarr (M \rarr A) \rarr M \rarr B = f \mapsto g \mapsto m \mapsto f \, (m' \mapsto g \, (m * m'))
\text{fmap}: (A \rarr B) \rarr (M \rarr A) \rarr M \rarr B = f \mapsto g \mapsto (f \circ g)
\text{duplicate}: (M \rarr A) \rarr M \rarr (M \rarr A) = f \mapsto m \mapsto m' \mapsto f \, (m * m')

donde ε es el elemento identidad de M y * es la operación asociativa.

Co-mónada co-estado[editar]

La co-mónada co-estado mapea a tipo T en tipo (S \rarr T) \times S, donde S es el tipo base de la tienda. Las opreaciones de la co-mónada son:

\text{extract}: ((S \rarr T) \times S) \rarr T = (f, s) \mapsto f \, s
\text{extend}: (((S \rarr A) \times S) \rarr B) \rarr ((S \rarr A) \times S) \rarr (S \rarr B) \times S \,= f \mapsto (g, s) \mapsto ((s' \mapsto f \, (g, s')), s)
\text{fmap}: (A \rarr B) \rarr ((S \rarr A) \times S) \rarr (S \rarr B) \times S = f \mapsto (f', s) \mapsto (f \circ f', s)
\text{duplicate}: ((S \rarr A) \times S) \rarr (S \rarr ((S \rarr A) \times S)) \times S = (f, s) \mapsto ((s' \mapsto (f, s')), s)

Véase también[editar]

Notas[editar]

  1. Técnicamente, la mónada no es requerida para preservar el tipo subyacente. Por ejemplo, la mónada trivial en la que solo hay un valor polimórfico , el cual es producido por todas las operaciones, satisface todos los axiomas de la monada. De la misma manera, la mónada no es requerida para añadir estructuras adicionales; la mónada identidad, la cual simplemente preserva el tipo original sin cambios, también satisface los axiomas de la mónada y es útil como una base recursiva para los tranformadores mónadicos.

Referencias[editar]

  1. a b c O'Sullivan, Bryan; Goerzen, John; Stewart, Don. Real World Haskell. O'Reilly, 2009. ch. 14.
  2. «A physical analogy for monads». Archivado desde el original el 10 Sep 2010.
  3. Eric Lippert. «Monads, part one». Consultado el 6 de septiembre de 2013.
  4. Wadler, Philip. Comprehending Monads. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990.
  5. Wadler, Philip. The Essence of Functional Programming. Conference Record of the Nineteenth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1992.
  6. Hughes, J. (2005). Programming with arrows. In Advanced Functional Programming (pp. 73-129). Springer Berlin Heidelberg. "
  7. De Meuter, Wolfgang. "Monads as a theoretical foundation for AOP". Workshop on Aspect Oriented Programming, ECOOP 1997.
  8. a b Moggi, Eugenio (1991). «Notions of computation and monads». Information and Computation 93 (1). http://www.disi.unige.it/person/MoggiE/ftp/ic91.pdf. 
  9. «Some Details on F# Computation Expressions». Consultado el 14-12-2007.
  10. «The Writer monad». haskell.cz.
  11. «Monad laws». HaskellWiki. haskell.org. Consultado el 11-12-2011.
  12. «Functors, Applicative Functors and Monoids». learnyouahaskell.com.
  13. How to make Data.Set a monad shows an implementation of the Set restricted monad in Haskell

Enlaces externos[editar]

Wikilibros

Haskell monad tutorials[editar]

Older tutorials[editar]

Other documentation[editar]

Scala monad tutorials[editar]

Mónadas en otros lenguajes[editar]