Поиск…
Понимание Монад происходит из практики
Эта тема предназначена для разработчиков с промежуточными и продвинутыми F #
«Что такое Монады?» это общий вопрос. Это легко ответить, но, как и в путеводителях автостопом по галактике, мы понимаем, что не понимаем ответа, потому что мы не знали, о чем мы просим.
Многие считают, что путь к пониманию Монад - это практиковать их. Как программисты, мы, как правило, не заботимся о математической основе того, что такое Принцип замещения Лискова, подтипы или подклассы. Используя эти идеи, мы приобрели интуицию для того, что они представляют. То же самое верно для Монад.
Чтобы помочь вам начать работу с Monads, этот пример демонстрирует, как создать библиотеку Monadic Parser Combinator . Это может помочь вам начать работу, но понимание придет от написания вашей собственной библиотеки Monadic.
Достаточно проза, время для кода
Тип Parser:
// 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
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 является парсером, который, в свою очередь, может быть объединен снова.
> 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)
Другим фундаментальным комбинатором парсеров, который мы будем использовать alot, является 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)
Замечание об операциях Infix
Общей проблемой FP является использование необычных инфиксных операторов, таких как >>= , >=> , <- и т. Д. Однако большинство из них не обеспокоено использованием + , - , * , / и % , это хорошо известные операторы, используемые для создания значений. Однако большая часть в FP заключается в составлении не только значений, но и функций. Для промежуточного разработчика FP операторы infix >>= , >=> , <- хорошо известны и должны иметь определенные подписи, а также семантику.
Для тех функций, которые мы определили до сих пор, мы определяли бы следующие инфиксные операторы, используемые для объединения парсеров:
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 которые являются более продвинутыми, поскольку они применяют входные парсеры, пока они не 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 . Если список пуст, мы fail , иначе мы сбрасываем символы в целое число.
Тестирование pint в FSI:
> 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 и убедившись, что они подчиняются монадическим законам, мы создали простую, но мощную структуру Monadic Parser Combinator.
Монады и парсеры идут вместе, потому что парсеры исполняются в состоянии парсера. Монады позволяют комбинировать парсеры, скрывая состояние парсера, тем самым уменьшая беспорядок и улучшая композиционную способность.
Созданная нами структура медленна и не вызывает сообщений об ошибках, чтобы сохранить код коротким. FParsec обеспечивает как приемлемую производительность, так и отличные сообщения об ошибках.
Однако один пример не может дать понимания Монадам. Нужно практиковать Монады.
Вот несколько примеров на Monads, которые вы можете попытаться реализовать, чтобы достичь достигнутого понимания:
- State Monad - разрешает скрытое состояние окружающей среды неявно
- Tracer Monad - позволяет отслеживать состояние неявно. Вариант государственной монады
- Черепаха Монада - Монада для создания программ черепахи (Логосов). Вариант государственной монады
- Продолжение Монада - сопрограмма Монады. Примером этого является
asyncв F #
Лучше всего научиться придумывать приложение для Monads в домене, с которым вам удобно. Для меня это были парсеры.
Полный исходный код:
// 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
К Monads относятся выражения вычисления F# ( CE ). Программист обычно реализует CE чтобы обеспечить альтернативный подход к цепочке Monads, т. Е. Вместо этого:
let v = m >>= fun x -> n >>= fun y -> return_ (x, y)
Вы можете написать это:
let v = ce {
let! x = m
let! y = n
return x, y
}
Оба стиля эквивалентны, и предпочтение разработчика зависит от выбора.
Чтобы продемонстрировать, как реализовать CE вам нравится, чтобы все следы включали идентификатор корреляции. Этот идентификатор корреляции поможет сопоставить трассировки, относящиеся к одному и тому же вызову. Это очень полезно, когда есть файлы журналов, содержащие следы от одновременных вызовов.
Проблема заключается в том, что в качестве аргумента ко всем функциям сложно включить идентификатор корреляции. Поскольку Monads позволяет переносить неявное состояние, мы определим Log Monad, чтобы скрыть контекст журнала (т.е. идентификатор корреляции).
Начнем с определения контекста журнала и типа функции, которая отслеживает контекст журнала:
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
trace - это Function<unit> которая означает, что при вызове будет передан контекст журнала. Из контекста журнала мы получаем идентификатор корреляции и отслеживаем его вместе с v
Кроме того, мы определяем bind и return_ и поскольку они следуют Законам Монады, это формирует нашу 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 для LogBuilder 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 to g в f что позволяет нам сопоставлять записи журнала во время устранения проблем.
CE имеет намного больше возможностей, но это должно помочь вам приступить к разработке собственного CE : s.
Полный код:
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