Buscar..
La comprensión de las mónadas viene de la práctica
Este tema está dirigido a desarrolladores de F # intermedios a avanzados
"¿Qué son las mónadas?" Es una pregunta común. Esto es fácil de responder, pero al igual que en la guía Hitchhikers a galaxia, nos damos cuenta de que no entendemos la respuesta porque no sabíamos qué era lo que preguntábamos.
Muchos creen que la forma de entender las Mónadas es practicándolas. Como programadores, normalmente no nos importa la base matemática de lo que son los Principios de Substitución de Liskov, los subtipos o subclases. Al usar estas ideas hemos adquirido una intuición de lo que representan. Lo mismo es cierto para las mónadas.
Para ayudarlo a comenzar con Monads, este ejemplo muestra cómo construir una biblioteca de Combinator de Parser Parser . Esto podría ayudarlo a comenzar, pero la comprensión vendrá de la escritura de su propia biblioteca Monadic.
Suficiente prosa, tiempo para codificar.
El tipo de analizador:
// A Parser<'T> is a function that takes a string and position
// and returns an optionally parsed value and a position
// A parsed value means the position points to the character following the parsed value
// No parsed value indicates a parse failure at the position
type Parser<'T> = Parser of (string*int -> 'T option*int)
Usando esta definición de un analizador definimos algunas funciones fundamentales del analizador
// Runs a parser 't' on the input string 's'
let run t s =
let (Parser tps) = t
tps (s, 0)
// Different ways to create parser result
let succeedWith v p = Some v, p
let failAt p = None , p
// The 'satisfy' parser succeeds if the character at the current position
// passes the 'sat' function
let satisfy sat : Parser<char> = Parser <| fun (s, p) ->
if p < s.Length && sat s.[p] then succeedWith s.[p] (p + 1)
else failAt p
// 'eos' succeeds if the position is beyond the last character.
// Useful when testing if the parser have consumed the full string
let eos : Parser<unit> = Parser <| fun (s, p) ->
if p < s.Length then failAt p
else succeedWith () p
let anyChar = satisfy (fun _ -> true)
let char ch = satisfy ((=) ch)
let digit = satisfy System.Char.IsDigit
let letter = satisfy System.Char.IsLetter
satisfy es una función que, dada una función sat , produce un analizador que tiene éxito si no hemos superado la EOS y el carácter en la posición actual pasa la función sat . Con el uso de satisfy creamos una serie de analizadores de caracteres útiles.
Ejecutando esto en FSI:
> run digit "";;
val it : char option * int = (null, 0)
> run digit "123";;
val it : char option * int = (Some '1', 1)
> run digit "hello";;
val it : char option * int = (null, 0)
Tenemos algunos analizadores fundamentales en su lugar. Los combinaremos en analizadores más potentes utilizando las funciones del combinador de analizador
// 'fail' is a parser that always fails
let fail<'T> = Parser <| fun (s, p) -> failAt p
// 'return_' is a parser that always succeed with value 'v'
let return_ v = Parser <| fun (s, p) -> succeedWith v p
// 'bind' let us combine two parser into a more complex parser
let bind t uf = Parser <| fun (s, p) ->
let (Parser tps) = t
let tov, tp = tps (s, p)
match tov with
| None -> None, tp
| Some tv ->
let u = uf tv
let (Parser ups) = u
ups (s, tp)
Los nombres y las firmas no se eligen de forma arbitraria, pero no profundizaremos en esto, en cambio, veamos cómo usamos bind para combinar el analizador en otros más complejos:
> run (bind digit (fun v -> digit)) "123";;
val it : char option * int = (Some '2', 2)
> run (bind digit (fun v -> bind digit (fun u -> return_ (v,u)))) "123";;
val it : (char * char) option * int = (Some ('1', '2'), 2)
> run (bind digit (fun v -> bind digit (fun u -> return_ (v,u)))) "1";;
val it : (char * char) option * int = (null, 1)
Lo que esto nos muestra es que bind nos permite combinar dos analizadores en un analizador más complejo. Como el resultado de bind es un analizador que a su vez se puede combinar de nuevo.
> run (bind digit (fun v -> bind digit (fun w -> bind digit (fun u -> return_ (v,w,u))))) "123";;
val it : (char * char * char) option * int = (Some ('1', '2', '3'), 3)
bind será la forma fundamental en que combinamos los analizadores aunque definiremos funciones de ayuda para simplificar la sintaxis.
Una de las cosas que puede simplificar la sintaxis son las expresiones de cálculo . Son fáciles de definir:
type ParserBuilder() =
member x.Bind (t, uf) = bind t uf
member x.Return v = return_ v
member x.ReturnFrom t = t
// 'parser' enables us to combine parsers using 'parser { ... }' syntax
let parser = ParserBuilder()
FSI
let p = parser {
let! v = digit
let! u = digit
return v,u
}
run p "123"
val p : Parser<char * char> = Parser <fun:bind@49-1>
val it : (char * char) option * int = (Some ('1', '2'), 2)
Esto es equivalente a:
> let p = bind digit (fun v -> bind digit (fun u -> return_ (v,u)))
run p "123";;
val p : Parser<char * char> = Parser <fun:bind@49-1>
val it : (char * char) option * int = (Some ('1', '2'), 2)
Otro combinador de analizador fundamental que vamos a utilizar mucho es orElse :
// 'orElse' creates a parser that runs parser 't' first, if that is successful
// the result is returned otherwise the result of parser 'u' is returned
let orElse t u = Parser <| fun (s, p) ->
let (Parser tps) = t
let tov, tp = tps (s, p)
match tov with
| None ->
let (Parser ups) = u
ups (s, p)
| Some tv -> succeedWith tv tp
Esto nos permite definir letterOrDigit así:
> let letterOrDigit = orElse letter digit;;
val letterOrDigit : Parser<char> = Parser <fun:orElse@70-1>
> run letterOrDigit "123";;
val it : char option * int = (Some '1', 1)
> run letterOrDigit "hello";;
val it : char option * int = (Some 'h', 1)
> run letterOrDigit "!!!";;
val it : char option * int = (null, 0)
Una nota sobre los operadores Infix.
Una preocupación común sobre FP es el uso de operadores infijos inusuales como >>= , >=> , <- y así sucesivamente. Sin embargo, la mayoría no están preocupados por el uso de + , - , * , / y % , estos son los operadores bien conocidos usados para componer los valores. Sin embargo, una gran parte en la FP es la composición no solo de los valores sino también de las funciones. Para un desarrollador de FP intermedio, los operadores de infijo >>= , >=> , <- son conocidos y deben tener firmas específicas, así como semántica.
Para las funciones que hemos definido hasta ahora, definiríamos los siguientes operadores de infijo utilizados para combinar analizadores:
let (>>=) t uf = bind t uf
let (<|>) t u = orElse t u
Entonces >>= significa bind y <|> significa orElse .
Esto nos permite combinar parsers más sucintos:
let letterOrDigit = letter <|> digit
let p = digit >>= fun v -> digit >>= fun u -> return_ (v,u)
Para definir algunos combinadores de analizador avanzados que nos permitirán analizar expresiones más complejas, definimos algunos combinadores de analizador más simples:
// 'map' runs parser 't' and maps the result using 'm'
let map m t = t >>= (m >> return_)
let (>>!) t m = map m t
let (>>%) t v = t >>! (fun _ -> v)
// 'opt' takes a parser 't' and creates a parser that always succeed but
// if parser 't' fails the new parser will produce the value 'None'
let opt t = (t >>! Some) <|> (return_ None)
// 'pair' runs parser 't' and 'u' and returns a pair of 't' and 'u' results
let pair t u =
parser {
let! tv = t
let! tu = u
return tv, tu
}
Estamos listos para definir many y sepBy cuáles son más avanzados, ya que aplican los analizadores de entrada hasta que fallan. Luego many y sepBy devuelve el resultado agregado:
// 'many' applies parser 't' until it fails and returns all successful
// parser results as a list
let many t =
let ot = opt t
let rec loop vs = ot >>= function Some v -> loop (v::vs) | None -> return_ (List.rev vs)
loop []
// 'sepBy' applies parser 't' separated by 'sep'.
// The values are reduced with the function 'sep' returns
let sepBy t sep =
let ots = opt (pair sep t)
let rec loop v = ots >>= function Some (s, n) -> loop (s v n) | None -> return_ v
t >>= loop
Creación de un analizador de expresión simple
Con las herramientas que creamos ahora podemos definir un analizador para expresiones simples como 1+2*3
Partimos de la parte inferior mediante la definición de un programa de análisis de números enteros pint
// 'pint' parses an integer
let pint =
let f s v = 10*s + int v - int '0'
parser {
let! digits = many digit
return!
match digits with
| [] -> fail
| vs -> return_ (List.fold f 0 vs)
}
Intentamos analizar tantos dígitos como podamos, el resultado es una char list . Si la lista está vacía, fail , de lo contrario, plegaremos los caracteres en un entero.
Prueba de pint en FSI:
> run pint "123";;
val it : int option * int = (Some 123, 3)
Además, necesitamos analizar los diferentes tipos de operadores utilizados para combinar valores enteros:
// operator parsers, note that the parser result is the operator function
let padd = char '+' >>% (+)
let psubtract = char '-' >>% (-)
let pmultiply = char '*' >>% (*)
let pdivide = char '/' >>% (/)
let pmodulus = char '%' >>% (%)
FSI:
> run padd "+";;
val it : (int -> int -> int) option * int = (Some <fun:padd@121-1>, 1)
Atando todo junto:
// 'pmullike' parsers integers separated by operators with same precedence as multiply
let pmullike = sepBy pint (pmultiply <|> pdivide <|> pmodulus)
// 'paddlike' parsers sub expressions separated by operators with same precedence as add
let paddlike = sepBy pmullike (padd <|> psubtract)
// 'pexpr' is the full expression
let pexpr =
parser {
let! v = paddlike
let! _ = eos // To make sure the full string is consumed
return v
}
Ejecutándolo todo en FSI:
> run pexpr "2+123*2-3";;
val it : int option * int = (Some 245, 9)
Conclusión
Al definir Parser<'T> , return_ , bind y asegurándose de que obedecen las leyes monádicas, hemos creado un sencillo pero poderoso marco Combinator de Parser Parser.
Las mónadas y los analizadores se juntan porque los analizadores se ejecutan en un estado de analizador. Las mónadas nos permiten combinar analizadores mientras ocultamos el estado del analizador, lo que reduce el desorden y mejora la composibilidad.
El marco que hemos creado es lento y no produce mensajes de error, esto para mantener el código sucinto. FParsec proporciona tanto un rendimiento aceptable como excelentes mensajes de error.
Sin embargo, un solo ejemplo no puede dar a entender las mónadas. Uno tiene que practicar mónadas.
Aquí hay algunos ejemplos de Mónadas que puede intentar implementar para alcanzar su comprensión ganada:
- Mónada estatal: permite que el estado del entorno oculto se lleve implícitamente
- Tracer Monad: permite que el estado de rastreo se lleve de forma implícita. Una variante de la mónada estatal.
- Turtle Monad: una mónada para crear programas Turtle (Logos). Una variante de la mónada estatal.
- Mónada De Continuación - Una Mónada De Coroutine. Un ejemplo de esto es
asyncen F #
Lo mejor para aprender sería crear una aplicación para Monads en un dominio con el que te sientas cómodo. Para mí eso fue parsers.
Código fuente completo:
// A Parser<'T> is a function that takes a string and position
// and returns an optionally parsed value and a position
// A parsed value means the position points to the character following the parsed value
// No parsed value indicates a parse failure at the position
type Parser<'T> = Parser of (string*int -> 'T option*int)
// Runs a parser 't' on the input string 's'
let run t s =
let (Parser tps) = t
tps (s, 0)
// Different ways to create parser result
let succeedWith v p = Some v, p
let failAt p = None , p
// The 'satisfy' parser succeeds if the character at the current position
// passes the 'sat' function
let satisfy sat : Parser<char> = Parser <| fun (s, p) ->
if p < s.Length && sat s.[p] then succeedWith s.[p] (p + 1)
else failAt p
// 'eos' succeeds if the position is beyond the last character.
// Useful when testing if the parser have consumed the full string
let eos : Parser<unit> = Parser <| fun (s, p) ->
if p < s.Length then failAt p
else succeedWith () p
let anyChar = satisfy (fun _ -> true)
let char ch = satisfy ((=) ch)
let digit = satisfy System.Char.IsDigit
let letter = satisfy System.Char.IsLetter
// 'fail' is a parser that always fails
let fail<'T> = Parser <| fun (s, p) -> failAt p
// 'return_' is a parser that always succeed with value 'v'
let return_ v = Parser <| fun (s, p) -> succeedWith v p
// 'bind' let us combine two parser into a more complex parser
let bind t uf = Parser <| fun (s, p) ->
let (Parser tps) = t
let tov, tp = tps (s, p)
match tov with
| None -> None, tp
| Some tv ->
let u = uf tv
let (Parser ups) = u
ups (s, tp)
type ParserBuilder() =
member x.Bind (t, uf) = bind t uf
member x.Return v = return_ v
member x.ReturnFrom t = t
// 'parser' enables us to combine parsers using 'parser { ... }' syntax
let parser = ParserBuilder()
// 'orElse' creates a parser that runs parser 't' first, if that is successful
// the result is returned otherwise the result of parser 'u' is returned
let orElse t u = Parser <| fun (s, p) ->
let (Parser tps) = t
let tov, tp = tps (s, p)
match tov with
| None ->
let (Parser ups) = u
ups (s, p)
| Some tv -> succeedWith tv tp
let (>>=) t uf = bind t uf
let (<|>) t u = orElse t u
// 'map' runs parser 't' and maps the result using 'm'
let map m t = t >>= (m >> return_)
let (>>!) t m = map m t
let (>>%) t v = t >>! (fun _ -> v)
// 'opt' takes a parser 't' and creates a parser that always succeed but
// if parser 't' fails the new parser will produce the value 'None'
let opt t = (t >>! Some) <|> (return_ None)
// 'pair' runs parser 't' and 'u' and returns a pair of 't' and 'u' results
let pair t u =
parser {
let! tv = t
let! tu = u
return tv, tu
}
// 'many' applies parser 't' until it fails and returns all successful
// parser results as a list
let many t =
let ot = opt t
let rec loop vs = ot >>= function Some v -> loop (v::vs) | None -> return_ (List.rev vs)
loop []
// 'sepBy' applies parser 't' separated by 'sep'.
// The values are reduced with the function 'sep' returns
let sepBy t sep =
let ots = opt (pair sep t)
let rec loop v = ots >>= function Some (s, n) -> loop (s v n) | None -> return_ v
t >>= loop
// A simplistic integer expression parser
// 'pint' parses an integer
let pint =
let f s v = 10*s + int v - int '0'
parser {
let! digits = many digit
return!
match digits with
| [] -> fail
| vs -> return_ (List.fold f 0 vs)
}
// operator parsers, note that the parser result is the operator function
let padd = char '+' >>% (+)
let psubtract = char '-' >>% (-)
let pmultiply = char '*' >>% (*)
let pdivide = char '/' >>% (/)
let pmodulus = char '%' >>% (%)
// 'pmullike' parsers integers separated by operators with same precedence as multiply
let pmullike = sepBy pint (pmultiply <|> pdivide <|> pmodulus)
// 'paddlike' parsers sub expressions separated by operators with same precedence as add
let paddlike = sepBy pmullike (padd <|> psubtract)
// 'pexpr' is the full expression
let pexpr =
parser {
let! v = paddlike
let! _ = eos // To make sure the full string is consumed
return v
}
Las expresiones de computación proporcionan una sintaxis alternativa a las mónadas en cadena.
Relacionadas con las mónadas están las expresiones de cálculo de F# ( CE ). Un programador normalmente implementa un CE para proporcionar un enfoque alternativo para encadenar Mónadas, es decir, en lugar de esto:
let v = m >>= fun x -> n >>= fun y -> return_ (x, y)
Puedes escribir esto:
let v = ce {
let! x = m
let! y = n
return x, y
}
Ambos estilos son equivalentes y depende de la preferencia del desarrollador cuál elegir.
Para demostrar cómo implementar una CE imagine que le gustan todas las trazas para incluir una identificación de correlación. Esta identificación de correlación ayudará a correlacionar las trazas que pertenecen a la misma llamada. Esto es muy útil cuando se tienen archivos de registro que contienen rastros de llamadas concurrentes.
El problema es que es engorroso incluir el ID de correlación como un argumento para todas las funciones. Como Monads permite llevar un estado implícito , definiremos una Log Monad para ocultar el contexto del registro (es decir, el ID de correlación).
Comenzamos por definir un contexto de registro y el tipo de una función que rastrea con el contexto de registro:
type Context =
{
CorrelationId : Guid
}
static member New () : Context = { CorrelationId = Guid.NewGuid () }
type Function<'T> = Context -> 'T
// Runs a Function<'T> with a new log context
let run t = t (Context.New ())
También definimos dos funciones de rastreo que se registrarán con el ID de correlación del contexto de registro:
let trace v : Function<_> = fun ctx -> printfn "CorrelationId: %A - %A" ctx.CorrelationId v
let tracef fmt = kprintf trace fmt
trace es una Function<unit> que significa que se pasará un contexto de registro cuando se invoque. Desde el contexto de registro, recogemos el ID de correlación y lo rastreamos junto con v
Además, definimos bind y return_ y como siguen las Leyes de la Mónada, esto forma nuestra Mónada de Log.
let bind t uf : Function<_> = fun ctx ->
let tv = t ctx // Invoke t with the log context
let u = uf tv // Create u function using result of t
u ctx // Invoke u with the log context
// >>= is the common infix operator for bind
let inline (>>=) (t, uf) = bind t uf
let return_ v : Function<_> = fun ctx -> v
Finalmente, definimos LogBuilder que nos permitirá usar la sintaxis CE para encadenar Log Monads.
type LogBuilder() =
member x.Bind (t, uf) = bind t uf
member x.Return v = return_ v
// This enables us to write function like: let f = log { ... }
let log = Log.LogBuilder ()
Ahora podemos definir nuestras funciones que deberían tener el contexto de registro implícito:
let f x y =
log {
do! Log.tracef "f: called with: x = %d, y = %d" x y
return x + y
}
let g =
log {
do! Log.trace "g: starting..."
let! v = f 1 2
do! Log.tracef "g: f produced %d" v
return v
}
Ejecutamos g con:
printfn "g produced %A" (Log.run g)
Que imprime:
CorrelationId: 33342765-2f96-42da-8b57-6fa9cdaf060f - "g: starting..."
CorrelationId: 33342765-2f96-42da-8b57-6fa9cdaf060f - "f: called with: x = 1, y = 2"
CorrelationId: 33342765-2f96-42da-8b57-6fa9cdaf060f - "g: f produced 3"
g produced 3
Observe que el CorrelationId se realiza implícitamente de run de g a f que nos permite el correlato de las entradas de registro durante la resolución de problemas.
CE tiene muchas más funciones, pero esto debería ayudarlo a comenzar a definir sus propios CE : s.
Código completo:
module Log =
open System
open FSharp.Core.Printf
type Context =
{
CorrelationId : Guid
}
static member New () : Context = { CorrelationId = Guid.NewGuid () }
type Function<'T> = Context -> 'T
// Runs a Function<'T> with a new log context
let run t = t (Context.New ())
let trace v : Function<_> = fun ctx -> printfn "CorrelationId: %A - %A" ctx.CorrelationId v
let tracef fmt = kprintf trace fmt
let bind t uf : Function<_> = fun ctx ->
let tv = t ctx // Invoke t with the log context
let u = uf tv // Create u function using result of t
u ctx // Invoke u with the log context
// >>= is the common infix operator for bind
let inline (>>=) (t, uf) = bind t uf
let return_ v : Function<_> = fun ctx -> v
type LogBuilder() =
member x.Bind (t, uf) = bind t uf
member x.Return v = return_ v
// This enables us to write function like: let f = log { ... }
let log = Log.LogBuilder ()
let f x y =
log {
do! Log.tracef "f: called with: x = %d, y = %d" x y
return x + y
}
let g =
log {
do! Log.trace "g: starting..."
let! v = f 1 2
do! Log.tracef "g: f produced %d" v
return v
}
[<EntryPoint>]
let main argv =
printfn "g produced %A" (Log.run g)
0