1. 所在位置
  2. 首页
  3. 经验笔记
  4. 正文

F# 了解Monad来自实践

示例

本主题面向中级到高级F＃开发人员

“什么是单子？” 是一个常见的问题。这很容易回答，但是就像在《旅行者指南》中的银河指南中一样，我们意识到我们不了解答案，因为我们不知道要问什么。

许多人认为了解Monads的方法是练习。作为程序员，我们通常不关心Liskov的替代原理，子类型或子类是什么的数学基础。通过使用这些想法，我们对它们所代表的内容有了直觉。Monads也是如此。

为了帮助您开始使用Monads，本示例演示了如何构建Monadic Parser Combinator库。这可能会帮助您入门，但要理解，将来自编写自己的Monadic库。

足够的散文，编写代码的时间

解析器类型：

// A Parser<'T> is a function that takes a string and position
//  并返回可选的解析值和位置
//  解析值表示位置指向解析值后面的字符
//  没有解析值表示该位置解析失败
type Parser<'T> = Parser of (string*int -> 'T option*int)

使用这个解析器的定义，我们定义了一些基本的解析器功能

// 在输入字符串“ s”上运行解析器“ t”
let run t s =
  let (Parser tps) = t
  tps (s, 0)

// 创建解析器结果的不同方法
let succeedWith v p = Some v, p
let failAt        p = None  , p

// 如果当前位置处的字符，则“满意”解析器将成功 
//  通过“卫星”功能
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”成功。
//  在测试解析器是否消耗了完整字符串时很有用
let eos : Parser<unit> = Parser <| fun (s, p) ->
  if p <s.Lengththen 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)

我们有一些基本的解析器。我们将使用解析器组合器功能将它们组合为功能更强大的解析器

// “失败”是始终失败的解析器
let fail<'T>      = Parser <| fun (s, p) -> failAt p
// 'return_'是始终以'v'值成功的解析器
let return_ v     = Parser <| fun (s, p) -> succeedWith v p

// “绑定”让我们将两个解析器组合成一个更复杂的解析器
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() =
  memberx.Bind      (t, uf) = bind      t   uf
  memberx.Return    v       = return_   v
  memberx.ReturnFromt       = t

// 'parser'使我们能够使用'parser {...}'语法组合解析器
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'创建一个解析器，如果成功，它将首先运行解析器't'
//  返回结果，否则返回解析器“ u”的结果
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显影剂中的中缀运算符>>=，>=>，<-是公知的，并应具有特定的签名以及语义。

对于到目前为止我们定义的函数，我们将定义以下用于组合解析器的中缀运算符：

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'运行解析器't'并使用'm'映射结果
let map m t       = t >>= (m >> return_)
let (>>!) t m     = map m t
let (>>%) t v     = t >>! (fun _ -> v)

// 'opt'接受一个解析器't'并创建一个总是成功的解析器，但是
//  如果解析器“ t”失败，则新的解析器将产生值“ None”
let opt t         = (t >>! Some) <|> (return_ None)

// 'pair'运行解析器't'和'u'并返回一对't'和'u'结果
let pair t u      = 
  parser {
    let! tv = t
    let! tu = u
    return tv, tu
  }

我们已经准备好定义它们many，sepBy并在应用输入解析器失败之前对其进行更高级的定义。然后many和sepBy返回聚合结果：

// 'many'应用解析器't'直到失败并返回所有成功
//  解析器结果作为列表
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'应用解析器't'，以'sep'分隔。 
//  使用函数“ sep”返回可减少值
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'解析一个整数
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)

另外，我们需要解析用于组合整数值的不同类型的运算符：

// 运算符解析器，请注意解析器结果是运算符函数 
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'解析器，由运算符分隔的整数具有与乘法相同的优先级
let pmullike  = sepBy pint (pmultiply <|> pdivide <|> pmodulus)
// 'paddlike'解析器子表达式由运算符分隔，其优先级与添加相同
let paddlike  = sepBy pmullike (padd <|> psubtract)
// 'pexpr'是完整表达
let pexpr     =
  parser {
    let! v = paddlike
    let! _ = eos      // 确保使用完整的字符串
    return v
  }

在FSI中全部运行：

> run pexpr "2+123*2-3";;
val it : int option * int = (Some 245, 9)

结论

通过定义Parser<'T>，return_，bind并确保他们遵守我们已经建立了一个简单但功能强大的单子解析器组合框架的单子法律。

Monad和解析器一起使用是因为解析器是在解析器状态下执行的。Monads允许我们在隐藏解析器状态的同时合并解析器，从而减少混乱并提高可组合性。

我们创建的框架很慢并且不会产生任何错误消息，这是为了使代码简洁。FParsec提供了可接受的性能以及出色的错误消息。

但是，仅凭一个例子并不能使人们理解Monads。一个人必须练习单子。

以下是有关Monad的一些示例，您可以尝试实现这些示例，以达到您的深厚理解：

  1. State Monad-允许隐式携带隐藏环境状态

  2. Tracer Monad-允许隐式地携带跟踪状态。State Monad的变体

  3. Turtle Monad-用于创建Turtle（徽标）程序的Monad。State Monad的变体

  4. Continuation Monad-协程Monad。asyncF＃中的一个示例

为了学习，最好的办法是为您熟悉的域中的Monad提供一个应用程序。对我来说，这是解析器。

完整的源代码：

// A Parser<'T> is a function that takes a string and position
//  并返回可选的解析值和位置
//  解析值表示位置指向解析值后面的字符
//  没有解析值表示该位置解析失败
type Parser<'T> = Parser of (string*int -> 'T option*int)

// 在输入字符串“ s”上运行解析器“ t”
let run t s =
  let (Parser tps) = t
  tps (s, 0)

// 创建解析器结果的不同方法
let succeedWith v p = Some v, p
let failAt        p = None  , p

// 如果当前位置处的字符，则“满意”解析器将成功 
//  通过“卫星”功能
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”成功。
//  在测试解析器是否消耗了完整字符串时很有用
let eos : Parser<unit> = Parser <| fun (s, p) ->
  if p <s.Lengththen 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

// “失败”是始终失败的解析器
let fail<'T>      = Parser <| fun (s, p) -> failAt p
// 'return_'是始终以'v'值成功的解析器
let return_ v     = Parser <| fun (s, p) -> succeedWith v p

// “绑定”让我们将两个解析器组合成一个更复杂的解析器
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() =
  memberx.Bind      (t, uf) = bind      t   uf
  memberx.Return    v       = return_   v
  memberx.ReturnFromt       = t

// 'parser'使我们能够使用'parser {...}'语法组合解析器
let parser = ParserBuilder()

// 'orElse'创建一个解析器，如果成功，它将首先运行解析器't'
//  返回结果，否则返回解析器“ u”的结果
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'运行解析器't'并使用'm'映射结果
let map m t       = t >>= (m >> return_)
let (>>!) t m     = map m t
let (>>%) t v     = t >>! (fun _ -> v)

// 'opt'接受一个解析器't'并创建一个总是成功的解析器，但是
//  如果解析器“ t”失败，则新的解析器将产生值“ None”
let opt t         = (t >>! Some) <|> (return_ None)

// 'pair'运行解析器't'和'u'并返回一对't'和'u'结果
let pair t u      = 
  parser {
    let! tv = t
    let! tu = u
    return tv, tu
  }

// 'many'应用解析器't'直到失败并返回所有成功
//  解析器结果作为列表
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'应用解析器't'，以'sep'分隔。 
//  使用函数“ sep”返回可减少值
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

// 一个简单的整数表达式解析器

// 'pint'解析一个整数
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)
  }

// 运算符解析器，请注意解析器结果是运算符函数 
let padd      = char '+' >>% (+)
let psubtract = char '-' >>% (-)
let pmultiply = char '*' >>% (*)
let pdivide   = char '/' >>% (/)
let pmodulus  = char '%' >>% (%)

// 'pmullike'解析器，由运算符分隔的整数具有与乘法相同的优先级
let pmullike  = sepBy pint (pmultiply <|> pdivide <|> pmodulus)
// 'paddlike'解析器子表达式由运算符分隔，其优先级与添加相同
let paddlike  = sepBy pmullike (padd <|> psubtract)
// 'pexpr'是完整表达
let pexpr     =
  parser {
    let! v = paddlike
    let! _ = eos      // 确保使用完整的字符串
    return v
  }
           

基础教程
猜你喜欢

友情链接： json在线解析 通晓查询 糯晒黄历 姓名打分 123培训网 币安app官网下载