How do I write a computation expression builder that accumulates a value and also allows standard language constructs?

Question

I have a computation expression builder that builds up a value as you go, and has many custom operations. However, it does not allow for standard F# language constructs, and I'm having a lot of trouble figuring out how to add this support.

To give a stand-alone example, here's a dead-simple and fairly pointless computation expression that builds F# lists:

type Items<'a> = Items of 'a list

type ListBuilder() =
    member x.Yield(()) = Items []

    [<CustomOperation("add")>]
    member x.Add(Items current, item:'a) =
        Items [ yield! current; yield item ]

    [<CustomOperation("addMany")>]
    member x.AddMany(Items current, items: seq<'a>) =
        Items [ yield! current; yield! items ]

let listBuilder = ListBuilder()

let build (Items items) = items

I can use this to build lists just fine:

let stuff =
    listBuilder {
        add 1
        add 5
        add 7
        addMany [ 1..10 ]
        add 42
    } 
    |> build

However, this is a compiler error:

listBuilder {
    let x = 5 * 39
    add x
}

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

And so is this:

listBuilder {
    for x = 1 to 50 do
        add x
}

// This control construct may only be used if the computation expression builder
// defines a For method.

I've read all the documentation and examples I can find, but there's something I'm just not getting. Every .Bind() or .For() method signature I try just leads to more and more confusing compiler errors. Most of the examples I can find either build up a value as you go along, or allow for regular F# language constructs, but I haven't been able to find one that does both.

If someone could point me in the right direction by showing me how to take this example and add support in the builder for let bindings and for loops (at minimum - using, while and try/catch would be great, but I can probably figure those out if someone gets me started) then I'll be able to gratefully apply the lesson to my actual problem.

Answer 1

The best place to look is the spec. For example,

b {
    let x = e
    op x
}

gets translated to

   T(let x = e in op x, [], fun v -> v, true)
=> T(op x, {x}, fun v -> let x = e in v, true)
=> [| op x, let x = e in b.Yield(x) |]{x}
=> b.Op(let x = e in in b.Yield(x), x)

So this shows where things have gone wrong, though it doesn't present an obvious solution. Clearly, Yield needs to be generalized since it needs to take arbitrary tuples (based on how many variables are in scope). Perhaps more subtly, it also shows that x is not in scope in the call to add (see that unbound x as the second argument to b.Op?). To allow your custom operators to use bound variables, their arguments need to have the [<ProjectionParameter>] attribute (and take functions from arbitrary variables as arguments), and you'll also need to set MaintainsVariableSpace to true if you want bound variables to be available to later operators. This will change the final translation to:

b.Op(let x = e in b.Yield(x), fun x -> x)

Building up from this, it seems that there's no way to avoid passing the set of bound values along to and from each operation (though I'd love to be proven wrong) - this will require you to add a Run method to strip those values back off at the end. Putting it all together, you'll get a builder which looks like this:

type ListBuilder() =
    member x.Yield(vars) = Items [],vars

    [<CustomOperation("add",MaintainsVariableSpace=true)>]
    member x.Add((Items current,vars), [<ProjectionParameter>]f) =
        Items (current @ [f vars]),vars

    [<CustomOperation("addMany",MaintainsVariableSpace=true)>]
    member x.AddMany((Items current, vars), [<ProjectionParameter>]f) =
        Items (current @ f vars),vars

    member x.Run(l,_) = l

Answer 2

The most complete examples I've seen are in §6.3.10 of the spec, especially this one:

/// Computations that can cooperatively yield by returning a continuation
type Eventually<'T> =
    | Done of 'T
    | NotYetDone of (unit -> Eventually<'T>)

[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module Eventually =

    /// The bind for the computations. Stitch 'k' on to the end of the computation.
    /// Note combinators like this are usually written in the reverse way,
    /// for example,
    ///     e |> bind k
    let rec bind k e =
        match e with
        | Done x -> NotYetDone (fun () -> k x)
        | NotYetDone work -> NotYetDone (fun () -> bind k (work()))

    /// The return for the computations.
    let result x = Done x

    type OkOrException<'T> =
        | Ok of 'T
        | Exception of System.Exception                    

    /// The catch for the computations. Stitch try/with throughout
    /// the computation and return the overall result as an OkOrException.
    let rec catch e =
        match e with
        | Done x -> result (Ok x)
        | NotYetDone work ->
            NotYetDone (fun () ->
                let res = try Ok(work()) with | e -> Exception e
                match res with
                | Ok cont -> catch cont // note, a tailcall
                | Exception e -> result (Exception e))

    /// The delay operator.
    let delay f = NotYetDone (fun () -> f())

    /// The stepping action for the computations.
    let step c =
        match c with
        | Done _ -> c
        | NotYetDone f -> f ()

    // The rest of the operations are boilerplate.

    /// The tryFinally operator.
    /// This is boilerplate in terms of "result", "catch" and "bind".
    let tryFinally e compensation =   
        catch (e)
        |> bind (fun res ->  compensation();
                             match res with
                             | Ok v -> result v
                             | Exception e -> raise e)

    /// The tryWith operator.
    /// This is boilerplate in terms of "result", "catch" and "bind".
    let tryWith e handler =   
        catch e
        |> bind (function Ok v -> result v | Exception e -> handler e)

    /// The whileLoop operator.
    /// This is boilerplate in terms of "result" and "bind".
    let rec whileLoop gd body =   
        if gd() then body |> bind (fun v -> whileLoop gd body)
        else result ()

    /// The sequential composition operator
    /// This is boilerplate in terms of "result" and "bind".
    let combine e1 e2 =   
        e1 |> bind (fun () -> e2)

    /// The using operator.
    let using (resource: #System.IDisposable) f =
        tryFinally (f resource) (fun () -> resource.Dispose())

    /// The forLoop operator.
    /// This is boilerplate in terms of "catch", "result" and "bind".
    let forLoop (e:seq<_>) f =
        let ie = e.GetEnumerator()
        tryFinally (whileLoop (fun () -> ie.MoveNext())
                              (delay (fun () -> let v = ie.Current in f v)))
                   (fun () -> ie.Dispose())


// Give the mapping for F# computation expressions.
type EventuallyBuilder() =
    member x.Bind(e,k)                  = Eventually.bind k e
    member x.Return(v)                  = Eventually.result v   
    member x.ReturnFrom(v)              = v   
    member x.Combine(e1,e2)             = Eventually.combine e1 e2
    member x.Delay(f)                   = Eventually.delay f
    member x.Zero()                     = Eventually.result ()
    member x.TryWith(e,handler)         = Eventually.tryWith e handler
    member x.TryFinally(e,compensation) = Eventually.tryFinally e compensation
    member x.For(e:seq<_>,f)            = Eventually.forLoop e f
    member x.Using(resource,e)          = Eventually.using resource e

Answer 3

The tutorial at "F# for fun and profit" is first class in this regard.

http://fsharpforfunandprofit.com/posts/computation-expressions-intro/

Answer 4

Following a similar struggle to Joel's (and not finding §6.3.10 of the spec that helpful) my issue with getting the For construct to generate a list came down to getting types to line up properly (no special attributes required). In particular I was slow to realise that For would build a list of lists, and therefore need flattening, despite the best efforts of the compiler to put me right. Examples that I found on the web were always wrappers around seq{}, using the yield keyword, repeated use of which invokes a call to Combine, which does the flattening. In case a concrete example helps, the following excerpt uses for to build a list of integers - my ultimate aim being to create lists of components for rendering in a GUI (with some additional laziness thrown in). Also In depth talk on CE here which elaborates on kvb's points above.

module scratch

    type Dispatcher = unit -> unit
    type viewElement = int
    type lazyViews = Lazy<list<viewElement>>

    type ViewElementsBuilder() =                
        member x.Return(views: lazyViews) : list<viewElement> = views.Value        
        member x.Yield(v: viewElement) : list<viewElement> = [v]
        member x.ReturnFrom(viewElements: list<viewElement>) = viewElements        
        member x.Zero() = list<viewElement>.Empty
        member x.Combine(listA:list<viewElement>, listB: list<viewElement>) =  List.concat [listA; listB]
        member x.Delay(f) = f()
        member x.For(coll:seq<'a>, forBody: 'a -> list<viewElement>) : list<viewElement>  =         
            // seq {for v in coll do yield! f v} |> List.ofSeq                       
            Seq.map forBody coll |> Seq.collect id  |> List.ofSeq

    let ve = new ViewElementsBuilder()
    let makeComponent(m: int, dispatch: Dispatcher) : viewElement = m
    let makeComponents() : list<viewElement> = [77; 33]

    let makeViewElements() : list<viewElement> =         
        let model = {| Scores = [33;23;22;43;] |> Seq.ofList; Trainer = "John" |}
        let d:Dispatcher = fun() -> () // Does nothing here, but will be used to raise messages from UI
        ve {                        
            for score in model.Scores do
                yield makeComponent (score, d)
                yield makeComponent (score * 100 / 50 , d)

            if model.Trainer = "John" then
                return lazy 
                [ makeComponent (12, d)
                  makeComponent (13, d)
                ]
            else 
                return lazy 
                [ makeComponent (14, d)
                  makeComponent (15, d)
                ]

            yield makeComponent (33, d)        
            return! makeComponents()            
        }