수색…
모나드를 이해하는 것은 연습에서 비롯됩니다.
이 항목은 중급에서 고급 F # 개발자를 대상으로합니다.
"모나드 란 무엇입니까?" 일반적인 질문입니다. 이것은 대답하기 쉽지만 Hitchhikers의 은하계 가이드 처럼 우리는 우리가 무엇을 요구했는지 알지 못했기 때문에 우리가 대답을 이해하지 못한다는 것을 깨닫습니다.
많은 사람들 은 모나드에 대한 이해가 그들을 연습함으로써 가능하다고 믿습니다. 프로그래머로서 우리는 일반적으로 Liskov의 대체 원칙, 하위 유형 또는 하위 클래스가 무엇인지에 대한 수학적 기반을 고려하지 않습니다. 이 아이디어를 사용함으로써 우리는 그들이 나타내는 것을 직감으로 얻었습니다. Monads에 대해서도 마찬가지입니다.
Monads를 시작하는 데 도움이되도록이 예제는 Monadic Parser Combinator 라이브러리를 작성하는 방법을 보여줍니다. 이것은 시작하는 데 도움이 될 수 있지만 자신의 모나 딕 (Monadic) 도서관을 작성하면 이해할 수 있습니다.
충분한 산문, 코드 시간
파서 타입 :
// 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)
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 는 sat 함수가 주어진 EOS 않고 현재 위치의 문자가 sat 함수를 통과하면 성공한 파서를 생성하는 함수입니다. satisfy 을 사용하여 유용한 문자 파서를 만듭니다.
이것을 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)
우리는 몇 가지 기본적인 파서를 사용합니다. 파서 결합 자 함수를 사용하여 더 강력한 파서로 결합합니다.
// '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)
이름과 서명이되어 임의로 선택하지 하지만 우리는 대신에,이에 대한 탐구의 우리가 사용하는 방법을 볼 수있을 bind 더 복잡한 것들로 파서를 결합 :
> 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)
이것이 우리에게 보여 주듯이 bind 는 두 개의 파서를 더 복잡한 파서로 결합 bind 수있게합니다. bind 결과는 다시 결합 될 수있는 파서입니다.
> 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 는 우리가 구문을 단순화하는 도우미 함수를 정의 할지라도 파서를 결합하는 근본적인 방법이 될 것입니다.
구문을 단순화 할 수있는 방법 중 하나는 계산식 입니다. 그들은 쉽게 정의 할 수 있습니다 :
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)
이것은 다음과 같습니다.
> 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)
우리가 많이 사용할 다른 기본 파서 결합자는 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
이렇게하면 letterOrDigit 를 다음과 같이 정의 할 수 있습니다.
> 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)
중서부 연산자에 대한 참고 사항
FP에 대한 공통 관심사는 >>= , >=> , <- 등등과 같은 특이한 중온 연산자를 사용하는 것입니다. 그러나 대부분은 + , - , * , / 및 % 의 사용에 대해서는 관심이 없으며 값을 구성하는 데 사용되는 잘 알려진 연산자입니다. 그러나 FP에서 중요한 부분은 가치뿐만 아니라 기능도 구성하는 데 있습니다. 중간 FP 개발자에게 >>= , >=> , <- 중온 연산자는 잘 알려져 있으며 의미와 특정 서명이 있어야합니다.
지금까지 정의한 함수들에 대해, 파서를 결합하기 위해 사용 된 다음 중온 연산자를 정의 할 것입니다 :
let (>>=) t uf = bind t uf
let (<|>) t u = orElse t u
그래서 >>= 의미 bind 및 <|> 의미 orElse .
이것은 우리가 더 간결한 파서를 결합 할 수있게 해준다.
let letterOrDigit = letter <|> digit
let p = digit >>= fun v -> digit >>= fun u -> return_ (v,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 및 sepBy 를 정의 할 준비가되었습니다. 그런 다음 many 와 sepBy 는 집계 된 결과를 반환합니다.
// '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
간단한 표현 파서 만들기
우리가 만든 도구를 사용하여 이제 1+2*3 과 같은 간단한 표현식에 대한 파서를 정의 할 수 있습니다.
우리는 정수에 대한 파서 정의하여 바닥에서 시작 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)
}
가능한 한 많은 자릿수를 분석하려고 char list . 결과는 char list 입니다. 목록이 비어 있으면 fail . 그렇지 않으면 문자를 정수로 변환합니다.
FSI의 테스트 pint :
> run pint "123";;
val it : int option * int = (Some 123, 3)
또한 정수 값을 결합하는 데 사용되는 여러 종류의 연산자를 파싱해야합니다.
// 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)
그것을 모두 묶어 라.
// '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
}
FSI에서 모두 실행 :
> run pexpr "2+123*2-3";;
val it : int option * int = (Some 245, 9)
결론
Parser<'T> , return_ , bind 를 정의하고 그들이 모나드 법칙 을 따르는 지 확인함으로써 우리는 간단하지만 강력한 모나드 파서 결합 자 프레임 워크를 구축했습니다.
파서는 파서 (parser) 상태에서 실행되므로 모나드와 파서는 함께 사용됩니다. Monads를 사용하면 파서를 결합 할 수 있으며 파서 상태를 숨기므로 혼란을 줄이고 구성 가능성을 향상시킬 수 있습니다.
우리가 만든 프레임 워크는 느리고 코드를 간결하게하기 위해 오류 메시지를 생성하지 않습니다. FParsec 은 우수한 오류 메시지뿐만 아니라 수용 가능한 성능을 제공합니다.
그러나 모나드를 이해할 수는 없습니다. 하나는 모나드를 연습해야합니다.
다음은 Monads에 대한 이해를 돕기 위해 구현할 수있는 모나드 예제입니다.
- 상태 모나드 - 숨겨진 환경 상태를 암시 적으로 전달할 수 있습니다.
- Tracer Monad - 추적 상태를 암시 적으로 전달할 수 있습니다. State Monad의 변형
- Turtle Monad - Turtle (로고) 프로그램을 만들기위한 Monad. State Monad의 변형
- 연속 Monad - 코 루틴 모나드. 이 예제는 F #에서
async입니다.
배울 수있는 가장 좋은 방법은 당신이 편한 도메인에 모나드 신청서를 작성하는 것입니다. 나를 위해 그것이 파서이었다.
전체 소스 코드 :
// 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
}
계산 표현식은 모나드 체인에 대한 대체 구문을 제공합니다.
Monads와 관련된 것은 F# 계산 표현식 ( CE )입니다. 프로그래머는 일반적으로 다음 대신에 Monads를 연결하는 대체 접근법을 제공하기 위해 CE 를 구현합니다.
let v = m >>= fun x -> n >>= fun y -> return_ (x, y)
다음과 같이 작성할 수 있습니다.
let v = ce {
let! x = m
let! y = n
return x, y
}
두 스타일 모두 동등하며 선택할 개발자 우선 순위에 달려 있습니다.
CE 구현 방법을 시연하기 위해 모든 추적에서 상관 ID를 포함하는 것이 좋습니다. 이 상관 ID는 동일한 호출에 속하는 추적을 상관시키는 데 도움이됩니다. 이는 동시 호출의 추적을 포함하는 로그 파일을 가질 때 매우 유용합니다.
문제는 상관 ID를 모든 함수의 인수로 포함시키는 것이 번거롭다는 것입니다. Monads 가 암시 적 상태를 전달할 수 있으므로 Log Monad를 정의하여 로그 컨텍스트 (즉 상관 ID)를 숨길 수 있습니다.
먼저 로그 컨텍스트와 로그 컨텍스트와 함께 추적되는 함수 유형을 정의합니다.
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 ())
또한 로그 컨텍스트에서 상관 ID로 기록 할 두 개의 추적 기능을 정의합니다.
let trace v : Function<_> = fun ctx -> printfn "CorrelationId: %A - %A" ctx.CorrelationId v
let tracef fmt = kprintf trace fmt
trace 는 호출 될 때 로그 컨텍스트를 전달한다는 것을 의미하는 Function<unit> 입니다. 로그 컨텍스트에서 상관 ID를 가져 와서 v 와 함께 추적합니다.
또한 bind 와 return_ 을 정의하고 Monad 법칙에 따라 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
마지막으로 우리는 LogBuilder 를 정의하여 CE 구문을 사용하여 Log Monads를 연결할 수 있습니다.
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
}
우리는 다음과 같이 g를 실행합니다.
printfn "g produced %A" (Log.run g)
어떤 지문 :
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
CorrelationId는 run 에서 g 에서 f 로 암시 적으로 전달되므로 문제 해결 중 로그 항목을 상호 연관시킬 수 있습니다.
CE 에는 더 많은 기능이 있지만 이것은 자신의 CE 정의를 시작할 때 도움이됩니다.
전체 코드 :
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