Implement Bind in a Custom Computation Expression

9
votes

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?

2
.netf#computation-expression
What does that workflow represent? I can tell you now that the types of your bind and return are off the mark, at least as far as monadic bind and return goes, but I have no idea what I'm looking at. – scrwtp
@scrwtp The idea is to create a sort of stack-oriented DSL. e.g. op { push 2; dup; add } [] → [4]. – p.s.w.g
What you call bind is not a bind, but just function application. To make it a monadic bind, the second parameter should be op<'b>, not 'b. – Fyodor Soikin
@FyodorSoikin Okay point taken. The ultimate goal was to implement something along the lines of let swap = op { let! x = pop; let! y = pop; push x; push y } and I figured starting with constant values (let! x = 4) would be easier. pop is a kind of op<'a> since it modifies the "stack" but I had no clue how to retrieve the popped value as a variable. – p.s.w.g
@p.s.w.g: What you're really want to arrive at is state monad - it's the piece you're missing to be able to implement pop - as its type would correspond to 'a list -> 'a * 'a list, the lone 'a being the popped value. I can give you an answer along these lines, but I wouldn't want to spoil the fun for you. – scrwtp

2 Answers

6
votes

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.

6
votes

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