在自定义计算表达式中实现绑定

Question

我试图通过实现我自己的一个来学习更多关于F#的计算表达式.但是,我遇到了与该Bind方法有关的绊脚石.这是我到目前为止所得到的:

type public op<'a> = Op of ('a list -> 'a list)

let inline (>>) (Op a) (Op b) = Op (a >> b)

module Op =
    let id = Op id
    let bind (b : 'b -> op<'a>) (v : 'b) = b v
    let call (Op f) = f
    let push v = Op (fun t -> v :: t)
    // .. snip  ..

type OpBuilder() =
    member __.Bind (v, b) = Op.bind b v
    member __.Yield (()) = Op.id
    member __.Return (m) = Op.call m

    [<CustomOperation("push")>]
    member __.Push (m : op<'a>, v : 'a) = m >> Op.push v
    // .. snip  ..

let op = new OpBuilder()

现在,我的理解是以下所有内容应大致相同:

// Use only the Op module methods
let f1 = Op.call(Op.bind (fun x -> Op.push x) 1)

// Use op builder with external closure
let f2 = Op.call(let x = 2 in op { push x })

// Use op builder bind explicitly
let f3 = op.Return(op.Bind(3, fun x -> op.Push(op.Yield(), x)))

// Use op builder with let! binding
let f4 = op { let! x = 4 in push x }

前三个似乎工作正常,但是,f4给出了这个错误:

这个表达式应该有类型
  单位,
但这里有
  int 类型

如果我用let而不是,我会得到同样的错误let!.我读过的所有内容都表明这是正确的实施方式Bind,但显然我错过了一些东西.谁能指出我做错了什么？

Answer 1

如果您尝试实现类似基于堆栈的DSL,那么计算表达式就不是很合适.您可以通过操作列表完美地表示这一点:

 type Op = 
  | Push of int
  | Dup
  | Add

let sample = 
  [ Push 2
    Dup
    Add ]

而且我无法抗拒写一个简单的评估者:

let rec eval stack ops = 
  match ops, stack with
  | (Push n)::ops, stack -> eval (n::stack) ops
  | Dup::ops, s::stack -> eval (s::s::stack) ops
  | Add::ops, s1::s2::stack -> eval ((s1+s2)::stack) ops
  | [], stack -> stack
  | _ -> failwith "Wrong arguments"

eval [] sample

如果你想给普通的语言结构赋予一些特殊的意义,比如变量绑定let!,其他类似的构造for和/ try或返回由yield或捕获的值,计算表达式很有用return.虽然你可以实现一些Haskell monad,但这些在F#中并不是那么有用 - 所以找到一个有用的玩具示例有点棘手.

Answer 2

虽然一个适当的解决方案可以让你有成长的空间,但是如评论中所讨论的那样使用完整的状态monad,你仍然可以按照定义的Op类型获得一些里程数.你需要为它定义一种退化构建器 - 它不是monad,它本质上是一个"函数组合"构建器,但它只是表达足够do!,所以你得到一个漂亮的语法.

所以假设你有一个像这样的Op类型:

type Op<'a> = 'a list -> 'a list

你可以像这样定义你的构建器 - 在绑定和返回时用一个单元取代"正确的"未包装的值 - 将它视为状态monad类型中缺少的部分:

type OpBuilder() =
    member __.Bind (ma, f) = ma >> f ()
    member __.Return (_) = id

let op = new OpBuilder()

那么操作:

[<AutoOpen>]
module Ops =

    let push (x:'a) : Op<'a> =  fun st -> x::st

    let dup: Op<'a> = fun st ->
        match st with
        | h::t -> h::h::t
        | [] -> []  

    let add: Op<int> = fun st ->
        match st with
        | a::b::t -> (a+b)::t
        | _ -> failwith "not enough operands" 

最后:

let comp : Op<_> =
    op {
        do! push 2
        do! dup
        do! add
    }

comp []