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

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给这个错误：

This expression was expected to have type
  unit
but here has type
  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单子，但这些在F＃中并不是那么有用 - 所以找到一个有用的玩具例子有点棘手。

Answer 2

虽然一个适当的解决方案为您提供呼吸空间，但需要使用完整的状态monad，如评论中所讨论的，您仍然可以根据您的操作类型定义一些里程。你需要为它定义一种退化的构建器 - 它不是一个monad，它基本上是一个“函数构成”构建器，但它只是表达了足够的do!，所以你得到一个很好看的语法。

因此，假如你有一个运算类型如下：

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

定义你的建设者这样的 - 与单位发生了“适当”展开值的绑定并返回 - 把它作为部分来自国家单子类型丢失：

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" 

和FIN盟友：

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

comp []