Partially deferred computation builder

Question

I'm trying to work out how to use a computation builder to represent a deferred, nested set of steps.

I've got the following so far:

type Entry =
    | Leaf of string * (unit -> unit)
    | Node of string * Entry list * (unit -> unit)

type StepBuilder(desc:string) =
    member this.Zero() = Leaf(desc,id)
    member this.Bind(v:string, f:unit->string) =
        Node(f(), [Leaf(v,id)], id)
    member this.Bind(v:Entry, f:unit->Entry) =
        match f() with
        | Node(label,children,a) -> Node(label, v :: children, a)
        | Leaf(label,a) -> Node(label, [v], a)


let step desc = StepBuilder(desc)

let a = step "a" {
    do! step "b" {
        do! step "c" {
            do! step "c.1" {
                // todo: this still evals as it goes; need to find a way to defer
                // the inner contents...
                printfn "TEST"
            }
        }
    }
    do! step "d" {
        printfn "d"
    }
}

This produces the desired structure:

A(B(C(c.1)), D)

My issue is that in building the structure up, the printfn calls are made.

Ideally what I want is to be able to retrieve the tree structure, but be able to call some returned function/s that will then execute the inner blocks.

I realise this means that if you have two nested steps with some "normal" code between them, it would need to be able to read the step declarations, and then invoke over it (if that makes sense?).

I know that Delay and Run are things that are used in deferred execution for computation expressions, but I'm not sure if they help me here, as they unfortunately evaluate for everything.

I'm most likely missing something glaringly obvious and very "functional-y" but I just can't seem to make it do what I want.

---

Clarification

I'm using id for demonstration, they're part of the puzzle, and I imagine how I might surface the "invokable" parts of my expression that I want.

Answer 1

As mentioned in the other answer, free monads provide a useful theoretical framework for thinking about this kind of problems - however, I think you do not necessarily need them to get an answer to the specific question you are asking here.

First, I had to add Return to your computation builder to make your code compile. As you never return anything, I just added an overload taking unit which is equivalent to Zero:

member this.Return( () ) = this.Zero()

Now, to answer your question - I think you need to modify your discriminated union to allow delaying of computations that produce Entry - you do have functions unit -> unit in the domain model, but that's not quite enough to delay a computation that will produce a new entry. So, I think you need to extend the type:

type Entry =
  | Leaf of string * (unit -> unit)
  | Node of string * Entry list * (unit -> unit)
  | Delayed of (unit -> Entry)

When you are evaluating Entry, you will now need to handle the Delayed case - which contains a function that might perform side-effect such as printing "TEST".

Now you can add Delay to your computation builder and also implement the missing case for Delayed in Bind like this:

member this.Delay(f) = Delayed(f)
member this.Bind(v:Entry, f:unit->Entry) = Delayed(fun () ->
    let rec loop = function
      | Delayed f -> loop (f())
      | Node(label,children,a) -> Node(label, v :: children, a)
      | Leaf(label,a) -> Node(label, [v], a)
    loop (f()) )

Essentially, Bind will create a new delayed computation that, when called, evaluates the entry v until it finds a node or a leaf (collapsing all other delayed nodes) and then does the same thing as what your code did before.

I think this answers your question - but I'd be a bit careful here. I think computation expressions are useful as a syntactic sugar, but they are very harmful if you think about them more than you think about the domain of the problem that you are actually solving - in the question, you did not say much about your actual problem. If you did, the answer might be very different.