Sök…
Att förstå Monader kommer från praxis
Detta ämne är avsett för mellanliggande till avancerade F # -utvecklare
"Vad är monader?" är en vanlig fråga. Detta är lätt att svara men som i Hitchhikers guide till galaxen inser vi att vi inte förstår svaret eftersom vi inte visste vad vi frågade efter.
Många tror att sättet att förstå Monader är genom att öva på dem. Som programmerare bryr vi oss normalt inte om den matematiska grunden för vad Liskovs substitutionsprincip, undertyper eller underklasser är. Genom att använda dessa idéer har vi fått en intuition för vad de representerar. Detsamma gäller för monader.
För att hjälpa dig komma igång med Monader visar detta exempel hur du bygger ett Monadic Parser Combinator- bibliotek. Detta kan hjälpa dig komma igång men förståelse kommer från att skriva ditt eget Monadic-bibliotek.
Tillräckligt med prosa, tid för kod
Parser-typen:
// 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)
Med denna definition av en Parser definierar vi några grundläggande parserfunktioner
// 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 är en funktion som ges en sat funktion som producerar en parser som lyckas om vi inte har gått EOS och karaktären vid den aktuella positionen passerar sat funktionen. Med satisfy skapar vi ett antal användbara teckenuppsättare.
Kör detta i 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)
Vi har några grundläggande tolkare på plats. Vi kommer att kombinera dem till mer kraftfulla analysatorer med hjälp av parser combinator-funktioner
// '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)
Namnen och signaturerna väljs inte godtyckligt men vi kommer inte att gå iväg med detta, låt oss istället se hur vi använder bind att kombinera parser till mer komplexa
> 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)
Vad detta visar oss är att bind tillåter oss att kombinera två tolkare till en mer komplex tolkare. Som resultat av bind är en parser som i sin tur kan kombineras igen.
> 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 kommer att vara det grundläggande sättet vi kombinerar parsers även om vi kommer att definiera hjälpfunktioner för att förenkla syntaxen.
En av de saker som kan förenkla syntax är beräkningsuttryck . De är lätta att definiera:
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)
Detta motsvarar:
> 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)
En annan grundläggande tolkarkombinator som vi kommer att använda många är 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
Detta gör att vi kan definiera letterOrDigit så här:
> 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)
En anteckning om Infix-operatörer
En vanlig oro över FP är användningen av ovanliga infixoperatörer som >>= , >=> , <- och så vidare. De flesta är dock inte bekymrade över användningen av + , - , * , / och % , dessa är välkända operatörer som används för att komponera värden. Men en stor del i FP handlar inte bara om att komponera värden utan också funktioner. För en mellanliggande FP-utvecklare är infixoperatörerna >>= , >=> , <- välkända och bör ha specifika signaturer såväl som semantik.
För de funktioner som vi har definierat hittills skulle vi definiera följande infixoperatörer som används för att kombinera parsers:
let (>>=) t uf = bind t uf
let (<|>) t u = orElse t u
Så >>= betyder bind och <|> betyder orElse .
Detta gör att vi kan kombinera tolkare som är mer kortfattade:
let letterOrDigit = letter <|> digit
let p = digit >>= fun v -> digit >>= fun u -> return_ (v,u)
För att definiera några avancerade parserkombinatorer som gör att vi kan analysera mer komplexa uttryck definierar vi några fler enkla parserkombinatorer:
// '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
}
Vi är redo att definiera many och sepBy som är mer avancerade när de tillämpar input-parsers tills de misslyckas. Sedan returnerar many och sepBy det aggregerade resultatet:
// '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
Skapa en enkel uttrycksdelare
Med verktygen vi skapade kan vi nu definiera en parser för enkla uttryck som 1+2*3
Vi börjar från botten med att definiera en parser för 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)
}
Vi försöker analysera så många siffror som vi kan, resultatet är char list . Om listan är tom fail vi, annars lägger vi tecknen till ett heltal.
Testa pint i FSI:
> run pint "123";;
val it : int option * int = (Some 123, 3)
Dessutom måste vi analysera olika typer av operatörer som används för att kombinera heltal:
// 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)
Binda det hela tillsammans:
// '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
}
Kör allt i FSI:
> run pexpr "2+123*2-3";;
val it : int option * int = (Some 245, 9)
Slutsats
Genom att definiera Parser<'T> , return_ , bind och se till att de följer de monadiska lagarna har vi byggt ett enkelt men kraftfullt Monadic Parser Combinator-ramverk.
Monader och parsare går samman eftersom parsare körs i en parser-tillstånd. Monader tillåter oss att kombinera tolkare medan vi döljer tolkningstillståndet och därmed minskar röran och förbättrar kompositionen.
Ramverket vi har skapat är långsamt och ger inga felmeddelanden, detta för att behålla koden kortfattad. FParsec ger både acceptabla prestanda och utmärkta felmeddelanden.
Men ett exempel ensamt kan inte ge förståelse för monader. Man måste öva monader.
Här är några exempel på monader som du kan försöka genomföra för att nå din vinnande förståelse:
- State Monad - Tillåter att dold miljötillstånd transporteras implicit
- Tracer Monad - Tillåter att spårningstillstånd transporteras implicit. En variant av State Monad
- Turtle Monad - En monad för att skapa Turtle (Logos) -program. En variant av State Monad
- Fortsättning Monad - En koroutin Monad. Ett exempel på detta är
asynci F #
Det bästa för att lära sig skulle vara att komma med en applikation för monader i en domän du är bekväm med. För mig var det parsers.
Full källkod:
// 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
}
Beräkningsuttryck ger en alternativ syntax till kedjemonader
Relaterade till monader är F# beräkningsuttryck ( CE ). En programmerare implementerar vanligtvis en CE att tillhandahålla en alternativ metod för att kedja monader, dvs. istället för detta:
let v = m >>= fun x -> n >>= fun y -> return_ (x, y)
Du kan skriva detta:
let v = ce {
let! x = m
let! y = n
return x, y
}
Båda stilarna är likvärdiga och det är upp till utvecklarens preferenser vilken man ska välja.
För att visa hur man implementerar en CE föreställa dig att du gillar alla spår för att inkludera ett korrelations-ID. Denna korrelations-ID hjälper till att korrelera spår som tillhör samma samtal. Detta är mycket användbart när du har loggfiler som innehåller spår från samtidiga samtal.
Problemet är att det är besvärligt att inkludera korrelations-ID som ett argument för alla funktioner. Eftersom monader tillåter att transportera implicit tillstånd definierar vi en loggmonad för att dölja loggkontexten (dvs. korrelations-id).
Vi börjar med att definiera en loggkontext och typen av en funktion som spårar med loggkontext:
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 ())
Vi definierar också två spårfunktioner som kommer att logga med korrelations-ID från loggkontext:
let trace v : Function<_> = fun ctx -> printfn "CorrelationId: %A - %A" ctx.CorrelationId v
let tracef fmt = kprintf trace fmt
trace är en Function<unit> vilket innebär att den kommer att ges en loggkontext när den åberopas. Från loggkontexten tar vi upp korrelations-ID och spårar den tillsammans med v
Dessutom definierar vi bind och return_ och när de följer Monad-lagarna bildar detta vår 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
Slutligen definierar vi LogBuilder som gör det möjligt för oss att använda CE syntax för att kedja Log monader.
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 ()
Vi kan nu definiera våra funktioner som ska ha implicit log-sammanhang:
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
}
Vi kör g med:
printfn "g produced %A" (Log.run g)
Vilka utskrifter:
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
Observera att CorrelationId implicit transporteras från run till g till f vilket gör att vi kan korrelera loggposterna under felsökning.
CE har mycket fler funktioner men det skulle hjälpa dig att komma igång med att definiera dina egna CE : er.
Fullständig kod:
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