Suche…
Monaden verstehen kommt aus der Praxis
Dieses Thema richtet sich an fortgeschrittene F # -Entwickler
"Was sind Monaden?" ist eine häufig gestellte Frage. Dies ist leicht zu beantworten, aber wie in Hitchhikers 'Leitfaden zur Galaxie ist uns klar, dass wir die Antwort nicht verstehen, weil wir nicht wussten, wonach wir gefragt haben.
Viele glauben, dass der Weg zum Verständnis der Monaden darin besteht, sie zu praktizieren. Als Programmierer interessieren wir uns normalerweise nicht für die mathematische Grundlage für das Substitutionsprinzip, die Untertypen oder Unterklassen von Liskov. Durch die Verwendung dieser Ideen haben wir eine Intuition für das, was sie repräsentieren, erworben. Gleiches gilt für Monaden.
Um Ihnen den Einstieg in Monaden zu erleichtern, zeigt dieses Beispiel, wie Sie eine Monadic Parser Combinator- Bibliothek erstellen . Dies kann Ihnen zwar beim Einstieg helfen, das Verständnis wird jedoch dadurch entstehen, dass Sie Ihre eigene Monadic-Bibliothek schreiben.
Genug Prosa, Zeit für Code
Der Parser-Typ:
// 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)
Mit dieser Definition eines Parsers definieren wir einige grundlegende Parserfunktionen
// 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 , ist eine Funktion , die eine gegebene sat Funktion erzeugt einen Parser, wenn wir nicht bestanden erfolgreich EOS und das Zeichen an der gegenwärtigen Position die Pässe sat Funktion. Mit satisfy wir eine Reihe von nützlichen Charakter Parser erstellen.
Ausführen 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)
Wir haben einige grundlegende Parser installiert. Wir werden sie mit Parser-Kombinatorfunktionen zu leistungsfähigeren Parsern kombinieren
// '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)
Die Namen und Signaturen werden nicht willkürlich ausgewählt, aber wir werden darauf nicht näher eingehen. Stattdessen wollen wir sehen, wie wir mit bind Parser zu komplexeren kombinieren:
> 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)
Das zeigt uns, dass bind es uns erlaubt, zwei Parser zu einem komplexeren Parser zu kombinieren. Als Ergebnis von bind entsteht ein Parser, der wiederum wieder kombiniert werden kann.
> 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 wird die grundlegende Möglichkeit sein, Parser zu kombinieren, obwohl wir Hilfsfunktionen definieren werden, um die Syntax zu vereinfachen.
Eine der Dinge, die die Syntax vereinfachen können, sind Berechnungsausdrücke . Sie sind leicht zu definieren:
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)
Das ist äquivalent zu:
> 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)
Ein weiterer grundlegender Parser-Kombinator, den wir alot verwenden werden, ist 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
Dadurch können wir letterOrDigit definieren:
> 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)
Ein Hinweis zu Infix-Operatoren
Ein häufiges Problem bei FP ist die Verwendung ungewöhnlicher Infix-Operatoren wie >>= , >=> , <- und so weiter. Die meisten machen sich jedoch keine Gedanken über die Verwendung von + , - , * , / und % . Dies sind bekannte Operatoren, die zum Zusammenstellen von Werten verwendet werden. Ein großer Teil von FP besteht jedoch darin, nicht nur Werte zu erstellen, sondern auch zu funktionieren. Für einen fortgeschrittenen FP-Entwickler sind die Infix-Operatoren >>= , >=> , <- bekannt und sollten über spezifische Signaturen sowie Semantik verfügen.
Für die bisher definierten Funktionen definieren wir die folgenden Infix-Operatoren, die zum Kombinieren von Parsern verwendet werden:
let (>>=) t uf = bind t uf
let (<|>) t u = orElse t u
Also bedeutet >>= bind und <|> orElse .
Dadurch können wir Parser prägnant kombinieren:
let letterOrDigit = letter <|> digit
let p = digit >>= fun v -> digit >>= fun u -> return_ (v,u)
Um einige erweiterte Parser-Kombinatoren zu definieren, die es uns ermöglichen, komplexere Ausdrücke zu parsen, definieren wir einige einfachere Parser-Kombinatoren:
// '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
}
Wir sind bereit, many und sepBy zu definieren, die fortgeschrittener sind, wenn sie die Eingabeparser anwenden, bis sie fehlschlagen. Dann geben many und sepBy das aggregierte Ergebnis zurück:
// '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
Einen einfachen Ausdrucksparser erstellen
Mit den von uns erstellten Tools können wir nun einen Parser für einfache Ausdrücke wie 1+2*3
Wir beginnen von unten, indem wir einen Parser für Ganzzahlen 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)
}
Wir versuchen, so viele Ziffern wie möglich zu analysieren, das Ergebnis ist eine char list . Wenn die Liste leer ist, schlagen wir fail , andernfalls falten wir die Zeichen in eine Ganzzahl.
Test pint in FSI:
> run pint "123";;
val it : int option * int = (Some 123, 3)
Außerdem müssen wir die verschiedenen Arten von Operatoren analysieren, die zum Kombinieren von Ganzzahlen verwendet werden:
// 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)
Alles zusammenbinden:
// '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
}
Alles in FSI ausführen:
> run pexpr "2+123*2-3";;
val it : int option * int = (Some 245, 9)
Fazit
Durch die Definition von Parser<'T> , return_ , bind und sicherstellen , dass sie gehorchen den monadischen Gesetze wir eine einfache , aber leistungsfähige Monadic Parser Combinator Rahmen gebaut haben.
Monaden und Parser gehören zusammen, weil Parser in einem Parserzustand ausgeführt werden. Monaden ermöglicht es uns, Parser zu kombinieren, während der Parserzustand ausgeblendet wird. Dadurch werden Unordnung reduziert und die Komposierbarkeit verbessert.
Das von uns erstellte Framework ist langsam und erzeugt keine Fehlermeldungen, um den Code übersichtlich zu halten. FParsec bietet sowohl eine akzeptable Leistung als auch hervorragende Fehlermeldungen.
Ein Beispiel allein kann Monaden jedoch nicht verstehen. Man muss Monaden üben.
Hier einige Beispiele für Monaden, die Sie implementieren können, um Ihr Verständnis zu erreichen:
- State Monad - Ermöglicht das implizite Tragen eines versteckten Umgebungsstatus
- Tracer Monad - Ermöglicht das implizite Tragen des Trace-Status. Eine Variante von State Monad
- Turtle Monad - Eine Monade zum Erstellen von Turtle (Logos) -Programmen. Eine Variante von State Monad
- Fortsetzung Monade - Eine Coroutine-Monade. Ein Beispiel dafür ist
asyncin F #
Das Beste, um zu lernen, wäre, eine Anwendung für Monaden in einer Domäne zu finden, mit der Sie sich wohl fühlen. Für mich waren das Parser.
Vollständiger Quellcode:
// 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
}
Berechnungsausdrücke bieten eine alternative Syntax zur Verkettung von Monaden
Mit Monaden verwandt sind F# -Berechnungsausdrücke ( CE ). Ein Programmierer implementiert normalerweise ein CE , um einen alternativen Ansatz zur Verkettung von Monaden bereitzustellen, dh stattdessen:
let v = m >>= fun x -> n >>= fun y -> return_ (x, y)
Sie können dies schreiben:
let v = ce {
let! x = m
let! y = n
return x, y
}
Beide Stile sind gleichwertig und es liegt an den von den Entwicklern bevorzugten, welchen Sie wählen.
Um zu zeigen, wie ein CE implementiert wird, stellen Sie sich vor, dass alle Spuren eine Korrelations-ID enthalten. Diese Korrelations-ID hilft bei der Korrelation von Spuren, die zu demselben Anruf gehören. Dies ist sehr nützlich, wenn Protokolldateien mit Ablaufverfolgungen von gleichzeitigen Aufrufen vorhanden sind.
Das Problem ist, dass es mühsam ist, die Korrelations-ID als Argument für alle Funktionen anzugeben. Da Monaden den impliziten Zustand zulassen, definieren wir eine Log-Monade, um den Log-Kontext (dh die Korrelations-ID) auszublenden.
Wir definieren zunächst einen Protokollkontext und den Typ einer Funktion, die mit dem Protokollkontext verfolgt:
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 ())
Wir definieren auch zwei Trace-Funktionen, die mit der Korrelations-ID aus dem Protokollkontext protokolliert werden:
let trace v : Function<_> = fun ctx -> printfn "CorrelationId: %A - %A" ctx.CorrelationId v
let tracef fmt = kprintf trace fmt
trace ist eine Function<unit> was bedeutet, dass beim Aufruf ein Protokollkontext übergeben wird. Aus dem Log-Kontext nehmen wir die Korrelations-ID auf und verfolgen sie zusammen mit v
Zusätzlich definieren wir bind und return_ und da sie den Monad-Gesetzen folgen, bildet dies unsere Log Monad.
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
Schließlich definieren wir LogBuilder , mit dem wir die CE Syntax verwenden können, um Log LogBuilder .
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 ()
Wir können jetzt unsere Funktionen definieren, die den impliziten Protokollkontext haben sollten:
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
}
Wir führen g aus mit:
printfn "g produced %A" (Log.run g)
Welche drucke:
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
Beachten Sie, dass die CorrelationId implizit von run nach g bis f , wodurch wir die Protokolleinträge während der Fehlersuche korrelieren können.
CE hat viel mehr Funktionen, aber dies sollte Ihnen helfen, Ihre eigenen CE definieren.
Vollständiger Code:
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