Zoeken…
Het begrijpen van Monaden komt uit de praktijk
Dit onderwerp is bedoeld voor gemiddelde tot gevorderde F # -ontwikkelaars
"Wat zijn monaden?" is een veel voorkomende vraag. Dit is gemakkelijk te beantwoorden, maar zoals in de gids van de lifter voor melkweg , realiseren we ons dat we het antwoord niet begrijpen, omdat we niet wisten waar we naar vroegen.
Velen geloven dat de manier om Monaden te begrijpen is door ze te oefenen. Als programmeurs geven we meestal niet om de wiskundige basis voor wat Liskov's Substitution Principle, subtypen of subklassen zijn. Door deze ideeën te gebruiken, hebben we een intuïtie verworven voor wat ze vertegenwoordigen. Hetzelfde geldt voor Monaden.
Om u te helpen aan de slag te gaan met Monads laat dit voorbeeld zien hoe u een Monadic Parser Combinator- bibliotheek kunt bouwen. Dit kan je op weg helpen, maar begrip komt van het schrijven van je eigen Monadic-bibliotheek.
Genoeg proza, tijd voor code
Het Parser-type:
// 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)
Met behulp van deze definitie van een parser definiëren we enkele fundamentele parserfuncties
// 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 is een functie die bij een sat functie een parser produceert die slaagt als we EOS niet zijn gepasseerd en het teken op de huidige positie de sat functie passeert. Met behulp van satisfy creëren we een aantal nuttige karakter parsers.
Dit uitvoeren 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)
We hebben enkele fundamentele parsers op hun plaats. We zullen ze combineren tot krachtigere parsers met behulp van parser-combinatorfuncties
// '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)
De namen en handtekeningen worden niet willekeurig gekozen, maar we zullen hier niet op ingaan, maar laten we eens kijken hoe we bind gebruiken om parser te combineren in complexere:
> 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)
Dit laat ons zien dat bind ons in staat stelt om twee parsers te combineren tot een meer complexe parser. Het resultaat van bind is een parser die op zijn beurt weer kan worden gecombineerd.
> 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 is de fundamentele manier waarop we parsers combineren, hoewel we helperfuncties definiëren om de syntaxis te vereenvoudigen.
Een van de dingen die de syntaxis kunnen vereenvoudigen, zijn rekenuitdrukkingen . Ze zijn eenvoudig te definiëren:
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)
Dit komt overeen met:
> 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)
Een andere fundamentele parser-combinator die we veel gaan gebruiken is 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
Hiermee kunnen we letterOrDigit als volgt definiëren:
> 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)
Een opmerking over Infix-operators
Een veel voorkomende zorg over FP is het gebruik van ongebruikelijke infix-operatoren zoals >>= , >=> , <- enzovoort. De meesten maken zich echter geen zorgen over het gebruik van + , - , * en / en % , dit zijn bekende operatoren die worden gebruikt om waarden samen te stellen. Een groot deel van FP gaat echter niet alleen over het samenstellen van waarden, maar ook over functies. Voor een intermediaire FP-ontwikkelaar zijn de infix-operatoren >>= , >=> , <- bekend en moeten ze specifieke handtekeningen en semantiek hebben.
Voor de functies die we tot nu toe hebben gedefinieerd, zouden we de volgende infix-operatoren definiëren die worden gebruikt om parsers te combineren:
let (>>=) t uf = bind t uf
let (<|>) t u = orElse t u
Dus >>= betekent bind en <|> betekent orElse .
Hierdoor kunnen we parsers beknopter combineren:
let letterOrDigit = letter <|> digit
let p = digit >>= fun v -> digit >>= fun u -> return_ (v,u)
Om enkele geavanceerde parsercombinators te definiëren waarmee we complexere expressie kunnen parseren, definiëren we een paar eenvoudigere parsercombinators:
// '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
}
We zijn klaar om many en sepBy te definiëren die geavanceerder zijn als ze de input parsers toepassen totdat ze falen. Vervolgens retourneert many en sepBy het geaggregeerde resultaat:
// '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
Een eenvoudige uitdrukkingsparser maken
Met de tools die we hebben gemaakt, kunnen we nu een parser definiëren voor eenvoudige uitdrukkingen zoals 1+2*3
We beginnen vanaf de onderkant door een parser te definiëren voor gehele getallen 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)
}
We proberen zoveel mogelijk cijfers te ontleden, het resultaat is een char list . Als de lijst leeg is, fail we, anders vouwen we de tekens in een geheel getal.
Testen pint in FSI:
> run pint "123";;
val it : int option * int = (Some 123, 3)
Bovendien moeten we de verschillende soorten operatoren ontleden die worden gebruikt om gehele getallen te combineren:
// 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 samenbinden:
// '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 draaien in FSI:
> run pexpr "2+123*2-3";;
val it : int option * int = (Some 245, 9)
Conclusie
Door Parser<'T> , return_ , bind definiëren en ervoor te zorgen dat ze de monadische wetten naleven , hebben we een eenvoudig maar krachtig Monadic Parser Combinator-framework gebouwd.
Monaden en Parsers gaan samen omdat Parsers worden uitgevoerd in een parserstatus. Met Monads kunnen we parsers combineren en de status van de parser verbergen, waardoor rommel wordt verminderd en de composibiliteit wordt verbeterd.
Het framework dat we hebben gemaakt is traag en geeft geen foutmeldingen, dit om de code beknopt te houden. FParsec biedt zowel acceptabele prestaties als uitstekende foutmeldingen.
Een voorbeeld alleen kan echter geen begrip geven voor monaden. Men moet Monaden oefenen.
Hier zijn enkele voorbeelden van Monaden die u kunt proberen uit te voeren om uw verkregen inzicht te bereiken:
- State Monad - Staat toe dat de verborgen omgevingsstatus impliciet wordt uitgevoerd
- Tracer-monade - Hiermee kan de traceerstatus impliciet worden uitgevoerd. Een variant van State Monad
- Turtle Monad - Een monade voor het maken van Turtle-programma's (logo's). Een variant van State Monad
- Vervolg Monad - Een coroutine monade. Een voorbeeld hiervan is
asyncin F #
Het beste om te leren zou zijn om een applicatie voor Monaden te bedenken in een domein waar je vertrouwd mee bent. Voor mij waren dat parsers.
Volledige broncode:
// 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
}
Computatie-expressies bieden een alternatieve syntaxis voor keten-monaden
Gerelateerd aan Monaden zijn F# berekeningsexpressies ( CE ). Een programmeur implementeert meestal een CE om een alternatieve benadering te bieden voor het koppelen van Monaden, dwz in plaats van dit:
let v = m >>= fun x -> n >>= fun y -> return_ (x, y)
Je kunt dit schrijven:
let v = ce {
let! x = m
let! y = n
return x, y
}
Beide stijlen zijn gelijkwaardig en het is aan de ontwikkelaarsvoorkeur welke te kiezen.
Stel je voor dat je wilt dat alle sporen een correlatie-ID bevatten om aan te tonen hoe je een CE implementeert. Deze correlatie-ID helpt bij het correleren van sporen die tot dezelfde oproep behoren. Dit is erg handig als u logbestanden hebt die sporen bevatten van gelijktijdige oproepen.
Het probleem is dat het omslachtig is om de correlatie-ID op te nemen als argument voor alle functies. Omdat Monads impliciete toestanden toestaat , zullen we een logmonade definiëren om de logcontext te verbergen (dwz de correlatie-id).
We beginnen met het definiëren van een logcontext en het type functie dat traceert met logcontext:
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 ())
We definiëren ook twee traceerfuncties die zullen loggen met de correlatie-ID uit de logcontext:
let trace v : Function<_> = fun ctx -> printfn "CorrelationId: %A - %A" ctx.CorrelationId v
let tracef fmt = kprintf trace fmt
trace is een Function<unit> wat betekent dat het een logcontext wordt doorgegeven wanneer het wordt aangeroepen. Uit de log-context halen we de correlatie-ID op en volgen deze samen met v
Daarnaast definiëren we bind en return_ en aangezien zij de Monad Wetten volgen, vormt dit onze 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
Ten slotte definiëren we LogBuilder waarmee we CE syntaxis kunnen gebruiken om 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 ()
We kunnen nu onze functies definiëren die de impliciete logcontext moeten hebben:
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
}
Wij voeren g uit met:
printfn "g produced %A" (Log.run g)
Welke afdrukken:
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
Merk op dat de CorrelationId impliciet wordt overgedragen van run naar g naar f waardoor we de logboekinvoeren kunnen correleren tijdens het oplossen van problemen.
CE heeft nog veel meer functies, maar dit zou je moeten helpen aan de slag te gaan met het definiëren van je eigen CE : s.
Volledige 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