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

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

虽然为您提供喘息空间的适当解决方案涉及使用评论中讨论的成熟状态 monad，但您仍然可以从定义的 Op 类型中获得一些好处。你需要为它定义一种退化的构建器——它不是 monad，它本质上是一个 "function composition" 构建器，但它的表现力足以满足 do!，所以你得到一个漂亮的语法。

假设您有这样的操作类型：

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

你这样定义你的构建器 - 用一个单元代替绑定中的 "proper" 解包值和 return - 将其视为状态 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 []

Answer 2

如果您正在尝试实现类似于基于堆栈的 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# 中并不是那么有用 - 因此要找到一个有用的玩具示例来玩玩有点棘手。

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

Implement Bind in a Custom Computation Expression

.net

f#

computation-expression