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

While a proper solution that gives you breathing room to grow involves using a full-fledged state monad as discussed in the comments, you can still get some mileage out of your Op type as defined. You need to define a sort of degenerate builder for it - it's not a monad, it's essentially a "function composition" builder, but it's just expressive enough for do!, so you get a nice looking syntax.

So assuming you have an Op type like this:

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

You define your builder like this - with a unit taking place of a "proper" unwrapped value in bind and return - think of it as the part missing from state monad type:

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

let op = new OpBuilder()

Then the operations:

[<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" 

And finally:

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

comp [] 

Answer 2

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.