Implement Bind in a Custom Computation Expression

Question

I'm trying to learn a bit more about F#'s computation expressions by implementing one of my own. However, I've hit a stumbling block with relation to the Bind method. Here's what I've got so far:

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()

Now, my understanding is that all of the following should be roughly equivalent:

// 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 }

The first 3 seem to work fine, however, f4 gives this error:

This expression was expected to have type
  unit
but here has type
  int

I get the same error if I use let instead of let!. Everything I've read suggests that this is correct way to implement Bind, but apparently I'm missing something. Can anyone point out what I'm doing wrong?

Answer 1

If you are trying to implement something like a stack-based DSL, then computation expressions are not a very good fit. You can perfectly represent this just with a list of operations:

 type Op = 
  | Push of int
  | Dup
  | Add

let sample = 
  [ Push 2
    Dup
    Add ]

And I could not resist writing a simple evaluator too:

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

Computation expressions are useful if you want to give some special meaning to ordinary language constructs such as variable binding let!, other constructs like for and try or returning a value as captured by yield or return. Although you can implement some of the Haskell monads, those are not all that useful in F# - so it is a bit tricky to find a useful toy example to play with.