How to implement delay in the maybe computation builder?

Question

Here is what I have so far:

type Maybe<'a> = option<'a>

let succeed x = Some(x)

let fail = None

let bind rest p =
    match p with
        | None -> fail
        | Some r -> rest r

let rec whileLoop cond body =
    if cond() then
        match body() with
        | Some() ->
            whileLoop cond body
        | None ->
            fail
    else
        succeed()

let forLoop (xs : 'T seq) f =
    using (xs.GetEnumerator()) (fun it ->
            whileLoop
                (fun () -> it.MoveNext())
                (fun () -> it.Current |> f)
        )

whileLoop works fine to support for loops, but I don't see how to get while loops supported. Part of the problem is that the translation of while loops uses delay, which I could not figure out in this case. The obvious implementation below is probably wrong, as it does not delay the computation, but runs it instead!

let delay f = f()

Not having delay also hinders try...with and try...finally.

Answer 1

There are actually two different ways of implementing continuation builders in F#. One is to represent delayed computations using the monadic type (if it supports some way of representing delayed computations, like Async<'T> or the unit -> option<'T> type as shown by kkm.

However, you can also use the flexibility of F# computation expressions and use a different type as a return value of Delay. Then you need to modify the Combine operation accordingly and also implement Run member, but it all works out quite nicely:

type OptionBuilder() = 
  member x.Bind(v, f) = Option.bind f v
  member x.Return(v) = Some v
  member x.Zero() = Some ()
  member x.Combine(v, f:unit -> _) = Option.bind f v
  member x.Delay(f : unit -> 'T) = f
  member x.Run(f) = f()
  member x.While(cond, f) =
    if cond() then x.Bind(f(), fun _ -> x.While(cond, f)) 
    else x.Zero()

let maybe = OptionBuilder()

The trick is that F# compiler uses Delay when you have a computation that needs to be delayed - that is: 1) to wrap the whole computation, 2) when you sequentially compose computations, e.g. using if inside the computation and 3) to delay bodies of while or for.

In the above definition, the Delay member returns unit -> M<'a> instead of M<'a>, but that's perfectly fine because Combine and While take unit -> M<'a> as their second argument. Moreover, by adding Run that evaluates the function, the result of maybe { .. } block (a delayed function) is evaluated, because the whole block is passed to Run:

// As usual, the type of 'res' is 'Option<int>'
let res = maybe { 
    // The whole body is passed to `Delay` and then to `Run`
    let! a = Some 3
    let b = ref 0
    while !b < 10 do 
      let! n = Some () // This body will be delayed & passed to While
      incr b
    if a = 3 then printfn "got 3"
    else printfn "got something else"
    // Code following `if` is delayed and passed to Combine
    return a }

This is a way to define computation builder for non-delayed types that is most likely more efficient than wrapping type inside a function (as in kkm's solution) and it does not require defining a special delayed version of the type.

Note that this problem does not happen in e.g. Haskell, because that is a lazy language, so it does not need to delay computations explicitly. I think that the F# translation is quite elegant as it allows dealing with both types that are delayed (using Delay that returns M<'a>) and types that represent just an immediate result (using Delay that returns a function & Run).