Ricerca…
Comprendere le Monadi deriva dalla pratica
Questo argomento è destinato agli sviluppatori di F # da intermedio ad avanzato
"Cosa sono le Monadi?" è una domanda comune È facile rispondere, ma come nella guida di Hitchhikers alla galassia ci rendiamo conto che non capiamo la risposta perché non sapevamo che cosa stavamo chiedendo.
Molti credono che il modo di comprendere la Monade sia praticarli. Come programmatori di solito non ci interessa il fondamento matematico per il Principio di sostituzione di Liskov, i sottotipi o le sottoclassi. Usando queste idee abbiamo acquisito un'intuizione per ciò che rappresentano. Lo stesso è vero per Monads.
Per aiutarti a iniziare con Monads questo esempio dimostra come costruire una libreria Monadic Parser Combinator . Questo potrebbe aiutarti a iniziare ma la comprensione verrà dalla scrittura della tua libreria Monadic.
Basta prosa, tempo per il codice
Il tipo di parser:
// 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 questa definizione di un parser definiamo alcune funzioni fondamentali del parser
// 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 è una funzione che data una funzione sat produce un parser che ha successo se non abbiamo passato EOS e il carattere nella posizione corrente passa la funzione sat . Usando satisfy creiamo un numero di parser di caratteri utili.
Eseguendo questo in 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)
Abbiamo alcuni parser fondamentali in atto. Li combineremo in parser più potenti usando le funzioni del combinatore di parser
// '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)
I nomi e le firme non sono scelti arbitrariamente, ma non approfondiremo questo argomento, vediamo invece come utilizziamo il bind per combinare il parser in quelli più complessi:
> 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)
Ciò che questo ci mostra è che il bind ci consente di combinare due parser in un parser più complesso. Come risultato del bind è un parser che a sua volta può essere combinato di nuovo.
> 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 sarà il modo fondamentale in cui combiniamo i parser, anche se definiremo le funzioni di supporto per semplificare la sintassi.
Una delle cose che può semplificare la sintassi sono espressioni di calcolo . Sono facili da definire:
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)
Questo è 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)
Un altro combinatore di parser fondamentale che useremo alot è 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
Questo ci permette di definire letterOrDigit questo modo:
> 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 sugli operatori Infix
Una preoccupazione comune su FP è l'uso di operatori inusuali insoliti come >>= , >=> , <- e così via. Tuttavia, la maggior parte non sono interessati all'uso di + , - , * , / e % , questi sono operatori ben noti usati per comporre valori. Tuttavia, una parte importante della FP riguarda la composizione non solo dei valori ma anche delle funzioni. Per uno sviluppatore FP intermedio gli operatori infissi >>= , >=> , <- sono ben noti e dovrebbero avere firme specifiche e semantica.
Per le funzioni che abbiamo definito finora dovremmo definire i seguenti operatori infissi usati per combinare i parser:
let (>>=) t uf = bind t uf
let (<|>) t u = orElse t u
Quindi >>= significa bind e <|> significa orElse .
Questo ci consente di combinare parser più succinti:
let letterOrDigit = letter <|> digit
let p = digit >>= fun v -> digit >>= fun u -> return_ (v,u)
Per definire alcuni combinatori di parser avanzati che ci consentano di analizzare espressioni più complesse, definiamo alcuni più semplici combinatori di parser:
// '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
}
Siamo pronti a definire many e sepBy che sono più avanzati in quanto applicano i parser di input finché non falliscono. Quindi many e sepBy restituiscono il risultato aggregato:
// '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
Creazione di un parser di espressioni semplici
Con gli strumenti che abbiamo creato possiamo ora definire un parser per espressioni semplici come 1+2*3
Iniziamo dal basso definendo un parser per la pint interi
// '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)
}
Cerchiamo di analizzare il maggior numero di cifre possibile, il risultato è una char list . Se la lista è vuota fail , altrimenti pieghiamo i caratteri in un numero intero.
Test di pint in FSI:
> run pint "123";;
val it : int option * int = (Some 123, 3)
Inoltre, è necessario analizzare il diverso tipo di operatori utilizzati per combinare valori interi:
// 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)
Legando tutto insieme:
// '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
}
Eseguendo tutto in FSI:
> run pexpr "2+123*2-3";;
val it : int option * int = (Some 245, 9)
Conclusione
Definendo Parser<'T> , return_ , bind e assicurandosi che obbediscano alle leggi monadiche abbiamo costruito un semplice ma potente framework Monadic Parser Combinator.
Monadi e parser vanno insieme perché i parser vengono eseguiti su uno stato parser. Monade consente di combinare parser nascondendo allo stesso tempo lo stato del parser, riducendo il disordine e migliorando la componibilità.
Il framework che abbiamo creato è lento e non produce messaggi di errore, questo per mantenere il codice succinto. FParsec fornisce sia prestazioni accettabili che eccellenti messaggi di errore.
Tuttavia, un esempio da solo non può dare la comprensione di Monadi. Bisogna praticare le monadi.
Ecco alcuni esempi su Monade che puoi provare ad implementare per raggiungere la tua comprensione vincente:
- Monade di stato: consente lo svolgimento di uno stato di ambiente nascosto implicitamente
- Tracer Monad - Permette di trasportare lo stato della traccia in modo implicito. Una variante della Monade di Stato
- Turtle Monad - A Monad per la creazione di programmi Turtle (Logos). Una variante della Monade di Stato
- Continuazione Monad - A coroutine Monad. Un esempio di questo è
asyncin F #
La cosa migliore per imparare sarebbe trovare un'applicazione per Monade in un dominio con cui ti trovi bene. Per me quello era parser.
Codice sorgente 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
}
Le espressioni di calcolo forniscono una sintassi alternativa per collegare le Monade
Relativi ai Monadi sono le espressioni di calcolo F# ( CE ). Un programmatore di solito implementa un CE per fornire un approccio alternativo al concatenamento delle Monade, ovvero invece di questo:
let v = m >>= fun x -> n >>= fun y -> return_ (x, y)
Puoi scrivere questo:
let v = ce {
let! x = m
let! y = n
return x, y
}
Entrambi gli stili sono equivalenti e spetta alle preferenze degli sviluppatori quali scegliere.
Per dimostrare come implementare una CE immagina che ti piacciano tutte le tracce per includere un id di correlazione. Questo ID di correlazione aiuterà a correlare le tracce che appartengono alla stessa chiamata. Ciò è molto utile quando i file di registro contengono tracce provenienti da chiamate simultanee.
Il problema è che è complicato includere l'id di correlazione come argomento per tutte le funzioni. Poiché Monads consente di trasportare lo stato implicito , definiremo una Log Monad per nascondere il contesto del log (cioè l'id di correlazione).
Iniziamo definendo un contesto di log e il tipo di una funzione che traccia con il contesto del log:
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 ())
Definiamo anche due funzioni di traccia che registreranno con l'ID di correlazione dal contesto del registro:
let trace v : Function<_> = fun ctx -> printfn "CorrelationId: %A - %A" ctx.CorrelationId v
let tracef fmt = kprintf trace fmt
trace è una Function<unit> che significa che verrà passato un contesto di log quando invocato. Dal contesto del registro, prendiamo l'id di correlazione e lo tracciamo insieme a v
Inoltre definiamo bind e return_ e mentre seguono il leggi Monade questa forma il nostro Log Monade.
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
Definiamo infine LogBuilder che ci consentirà di utilizzare la sintassi CE per concatenare le Monade Log .
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 ()
Ora possiamo definire le nostre funzioni che dovrebbero avere il contesto implicito del registro:
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
}
Eseguiamo g con:
printfn "g produced %A" (Log.run g)
Quale stampa:
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
Si noti che CorrelationId viene trasportato implicitamente da run a g to f che ci consente di correlare le voci del log durante la risoluzione dei problemi.
CE ha molte più funzioni ma questo dovrebbe aiutarti a iniziare a definire il tuo CE : s.
Codice 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