Szukaj…
Zrozumienie Monad pochodzi z praktyki
Ten temat jest przeznaczony dla średnio zaawansowanych i zaawansowanych programistów F #
„Czym są Monady?” jest częstym pytaniem. Łatwo jest na nie odpowiedzieć, ale podobnie jak w poradniku Autostopowiczów po galaktyce zdajemy sobie sprawę, że nie rozumiemy odpowiedzi, ponieważ nie wiedzieliśmy, o co pytamy.
Wielu uważa, że sposobem na zrozumienie Monad jest ich ćwiczenie. Jako programiści zwykle nie dbamy o matematyczne podstawy, czym jest Zasada Substytucji, podtypy lub podklasy Liskowa. Korzystając z tych pomysłów, uzyskaliśmy intuicję dotyczącą tego, co reprezentują. To samo dotyczy Monad.
W tym przykładzie pokazano, jak zbudować bibliotekę Monadic Parser Combinator . Może to pomóc w rozpoczęciu pracy, ale zrozumienie będzie wynikało z pisania własnej biblioteki Monadic.
Dość prozy, czas na kod
Typ parsera:
// 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)
Stosując tę definicję parsera, definiujemy niektóre podstawowe funkcje parsera
// 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 jest funkcją, która przy danej funkcji sat tworzy analizator składni, który się powiedzie, jeśli nie przejdziemy EOS a znak na bieżącej pozycji przejdzie przez funkcję sat . Korzystając z satisfy tworzymy szereg użytecznych parserów znaków.
Uruchamianie tego w 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)
Mamy kilka podstawowych parserów. Połączymy je w mocniejsze parsery za pomocą funkcji kombinatora parserów
// '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)
Nazwy i podpisy nie są wybierane arbitralnie, ale nie zajmiemy się tym, zamiast tego zobaczmy, jak używamy bind do łączenia parsera w bardziej złożone:
> 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)
To pokazuje nam, że bind pozwala nam połączyć dwa parsery w bardziej złożony parser. W wyniku bind powstaje parser, który z kolei można ponownie połączyć.
> 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 będzie podstawowym sposobem łączenia parserów, chociaż zdefiniujemy funkcje pomocnicze w celu uproszczenia składni.
Jedną z rzeczy, które mogą uprościć składnię, są wyrażenia obliczeniowe . Są łatwe do zdefiniowania:
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)
Jest to równoważne z:
> 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)
Kolejnym podstawowym kombinatorem parsera, którego będziemy używać, jest 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
To pozwala nam zdefiniować letterOrDigit następujący sposób:
> 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)
Uwaga na temat operatorów Infix
Częstym problemem związanym z FP jest stosowanie nietypowych operatorów infix, takich jak >>= , >=> , <- i tak dalej. Jednak większość nie obawia się o użycie + , - , * , / i % , są to dobrze znane operatory używane do tworzenia wartości. Jednak duża część w FP polega na komponowaniu nie tylko wartości, ale także funkcji. Dla pośredniego programisty FP operatory infix >>= , >=> , <- są dobrze znane i powinny mieć określone podpisy oraz semantykę.
Dla funkcji, które do tej pory zdefiniowaliśmy, zdefiniowalibyśmy następujące operatory infix używane do łączenia parserów:
let (>>=) t uf = bind t uf
let (<|>) t u = orElse t u
Więc >>= oznacza bind a <|> oznacza orElse .
Pozwala nam to na bardziej zwięzłe łączenie parserów:
let letterOrDigit = letter <|> digit
let p = digit >>= fun v -> digit >>= fun u -> return_ (v,u)
Aby zdefiniować niektóre zaawansowane kombinatory parsera, które pozwolą nam analizować bardziej złożone wyrażenia, zdefiniujemy kilka prostszych kombinacji parserów:
// '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
}
Jesteśmy gotowi zdefiniować many i sepBy które są bardziej zaawansowane, ponieważ stosują parsery wejściowe, dopóki nie zawiodą. Następnie many i sepBy zwraca zagregowany wynik:
// '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
Tworzenie prostego parsera wyrażeń
Za pomocą narzędzi, które stworzyliśmy, możemy teraz zdefiniować parser dla prostych wyrażeń, takich jak 1+2*3
Zaczynamy od dołu, definiując parser dla liczb całkowitych 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)
}
Próbujemy parsować jak najwięcej cyfr, wynikiem jest char list . Jeśli lista jest pusta, fail , w przeciwnym razie składamy znaki w liczbę całkowitą.
Testowanie pint w FSI:
> run pint "123";;
val it : int option * int = (Some 123, 3)
Ponadto musimy przeanalizować różne rodzaje operatorów używanych do łączenia wartości całkowitych:
// 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)
Wiązanie wszystkiego razem:
// '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
}
Uruchamianie wszystkiego w FSI:
> run pexpr "2+123*2-3";;
val it : int option * int = (Some 245, 9)
Wniosek
Definiując Parser<'T> , return_ , bind i upewniając się, że są one zgodne z prawami monadycznymi , stworzyliśmy prostą, ale potężną strukturę Monadic Parser Combinator.
Monady i parsery idą w parze, ponieważ parsery są wykonywane w stanie analizatora składni. Monady pozwalają nam łączyć parsery, jednocześnie ukrywając stan parsera, zmniejszając tym samym bałagan i poprawiając kompozycję.
Struktura, którą stworzyliśmy, jest powolna i nie wyświetla komunikatów o błędach, aby zachować zwięzłość kodu. FParsec zapewnia zarówno akceptowalną wydajność, jak i doskonałe komunikaty o błędach.
Jednak sam przykład nie może dać zrozumienia Monad. Trzeba ćwiczyć Monady.
Oto kilka przykładów Monad, które możesz spróbować wdrożyć, aby osiągnąć swoje wygrane zrozumienie:
- State Monad - Umożliwia niejawne przenoszenie stanu ukrytego środowiska
- Tracer Monad - Umożliwia niejawne przenoszenie stanu śledzenia. Wariant Monady Stanowej
- Turtle Monad - Monada do tworzenia programów Turtle (Logos). Wariant Monady Stanowej
- Kontynuacja Monada - Coradine Monad. Przykładem tego jest
asyncw języku F #
Najlepszą rzeczą do nauczenia się byłoby wymyślenie aplikacji na Monady w domenie, w której czujesz się komfortowo. Dla mnie to były parsery.
Pełny kod źródłowy:
// 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
}
Wyrażenia obliczeniowe zapewniają alternatywną składnię łańcuchową Monad
Monady są powiązane z wyrażeniami obliczeniowymi F# ( CE ). Programista zwykle implementuje CE aby zapewnić alternatywne podejście do łączenia Monad, tj. Zamiast tego:
let v = m >>= fun x -> n >>= fun y -> return_ (x, y)
Możesz to napisać:
let v = ce {
let! x = m
let! y = n
return x, y
}
Oba style są równoważne i wybór należy do preferencji programisty.
Aby zademonstrować, jak wdrożyć CE wyobraź sobie, że podoba Ci się wszystkie ślady zawierające identyfikator korelacji. Ten identyfikator korelacji pomoże skorelować ślady należące do tego samego wywołania. Jest to bardzo przydatne, gdy pliki dziennika zawierają ślady z jednoczesnych wywołań.
Problem polega na tym, że dołączenie identyfikatora korelacji jako argumentu dla wszystkich funkcji jest uciążliwe. Ponieważ Monady zezwalają na przenoszenie stanu niejawnego , zdefiniujemy Monadę Logu, aby ukryć kontekst dziennika (tj. Identyfikator korelacji).
Zaczynamy od zdefiniowania kontekstu dziennika i typu funkcji, która śledzi kontekst kontekstu dziennika:
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 ())
Definiujemy również dwie funkcje śledzenia, które będą rejestrować z identyfikatorem korelacji z kontekstu dziennika:
let trace v : Function<_> = fun ctx -> printfn "CorrelationId: %A - %A" ctx.CorrelationId v
let tracef fmt = kprintf trace fmt
trace jest Function<unit> co oznacza, że po uruchomieniu zostanie przekazany kontekst dziennika. Z kontekstu dziennika pobieramy identyfikator korelacji i śledzimy go razem z v
Ponadto definiujemy bind i return_ a ponieważ są one zgodne z prawami Monady, tworzy to nasza Log Monada.
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
Wreszcie definiujemy LogBuilder , który pozwoli nam używać składni CE do łączenia Log Monad.
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 ()
Możemy teraz zdefiniować nasze funkcje, które powinny mieć niejawny kontekst dziennika:
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
}
Wykonujemy g z:
printfn "g produced %A" (Log.run g)
Które wydruki:
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
Zauważ, że CorrelationId jest niejawnie przenoszony z run na g do f co pozwala nam skorelować wpisy dziennika podczas rozwiązywania problemów.
CE ma o wiele więcej funkcji, ale powinno to pomóc w rozpoczęciu definiowania własnego CE : s.
Pełny 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