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

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 }

前 3 个似乎工作正常，但是，f4给出了此错误：

此表达式应具有类型
单位
但这里有类型
国际

如果我使用 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 monads，但这些在 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 []