How do you create an F# workflow that enables something like single-stepping?

Question

I'd like to create a builder that builds expressions that returns something like a continuation after each step.

Something like this:

module TwoSteps = 
  let x = stepwise {
    let! y = "foo"
    printfn "got: %A" y
    let! z = y + "bar"
    printfn "got: %A" z
    return z
  }

  printfn "two steps"
  let a = x()
  printfn "something inbetween"
  let b = a()

Where the 'let a' line returns something containing the rest of the expressions to be evaluated later on.

Doing this with a separate type for each number of steps is straightforward but of course not particularly useful:

type Stepwise() =
  let bnd (v: 'a) rest = fun () -> rest v
  let rtn v = fun () -> Some v
  member x.Bind(v, rest) = 
    bnd v rest
  member x.Return v = rtn v

let stepwise = Stepwise()

module TwoSteps = 
  let x = stepwise {
    let! y = "foo"
    printfn "got: %A" y
    let! z = y + "bar"
    printfn "got: %A" z
    return z
  }

  printfn "two steps"
  let a = x()
  printfn "something inbetween"
  let b = a()

module ThreeSteps = 
  let x = stepwise {
    let! y = "foo"
    printfn "got: %A" y
    let! z = y + "bar"
    printfn "got: %A" z
    let! z' = z + "third"
    printfn "got: %A" z'
    return z
  }

  printfn "three steps"
  let a = x()
  printfn "something inbetween"
  let b = a()
  printfn "something inbetween"
  let c = b()

And the results are what I'm looking for:

two steps
got: "foo"
something inbetween
got: "foobar"
three steps
got: "foo"
something inbetween
got: "foobar"
something inbetween
got: "foobarthird"

But I can't figure out what the general case of this would be.

What I'd like is to be able to feed events into this workflow, so you could write something like:

let someHandler = Stepwise<someMergedEventStream>() {
  let! touchLocation = swallowEverythingUntilYouGetATouch()
  startSomeSound()
  let! nextTouchLocation = swallowEverythingUntilYouGetATouch()
  stopSomeSound()
}

And have events trigger a move to the next step in the workflow. (In particular, I want to play with this sort of thing in MonoTouch - F# on the iPhone. Passing around objc selectors drives me insane.)

Answer 1

Monads and computation builders confuse the hell out of me, but I've adapted something I've made in an earlier SO post. Maybe some bits and pieces can be of use.

The code below contains an action queue, and a form where the Click event listens to the next action available in the action queue. The code below is an example with 4 actions in succession. Execute it in FSI and start clicking the form.

open System.Collections.Generic
open System.Windows.Forms

type ActionQueue(actions: (System.EventArgs -> unit) list) =
    let actions = new Queue<System.EventArgs -> unit>(actions) //'a contains event properties
    with
        member hq.Add(action: System.EventArgs -> unit) = 
           actions.Enqueue(action)
        member hq.NextAction = 
            if actions.Count=0 
                then fun _ -> ()
                else actions.Dequeue()

//test code
let frm = new System.Windows.Forms.Form()

let myActions = [
    fun (e:System.EventArgs) -> printfn "You clicked with %A" (e :?> MouseEventArgs).Button
    fun _ -> printfn "Stop clicking me!!"
    fun _ -> printfn "I mean it!"
    fun _ -> printfn "I'll stop talking to you now."
    ]

let aq = new ActionQueue(myActions)

frm.Click.Add(fun e -> aq.NextAction e)

//frm.Click now executes the 4 actions in myActions in order and then does nothing on further clicks
frm.Show()

You can click the form 4 times and then nothing happens with further clicks. Now execute the following code, and the form will respond two more times:

let moreActions = [
    fun _ -> printfn "Ok, I'll talk to you again. Just don't click anymore, ever!"
    fun _ -> printfn "That's it. I'm done with you."
    ]

moreActions |> List.iter (aq.Add)

Answer 2

Hi James,

the problem with your implementation is that it returns "unit -> 'a" for each call to Bind, so you'll get a different type of result for different number of steps (in general, this is a suspicious definition of monad/computation expression).

A correct solution should be to use some other type, which can represent a computation with arbitrary number of steps. You'll also need to distinguish between two types of steps - some steps just evaluate next step of the computation and some steps return a result (via the return keyword). I'll use a type seq<option<'a>>. This is a lazy sequence, so reading the next element will evaluate the next step of the computation. The sequence will contain None values with the exception of the last value, which will be Some(value), representing the result returned using return.

Another suspicious thing in your implementation is a non-standard type of Bind member. The fact that your bind takes a value as the first parameter means that your code looks a bit simpler (you can write let! a = 1) however, you cannot compose stepwise computation. You may want to be able to write:

let foo() = stepwise { 
  return 1; }
let bar() = stepwise { 
  let! a = foo()
  return a + 10 }

The type I described above will allow you to write this as well. Once you have the type, you just need to follow the type signature of Bind and Return in the implementation and you'll get this:

type Stepwise() = 
  member x.Bind(v:seq<option<_>>, rest:(_ -> seq<option<_>>)) = seq {
    let en = v.GetEnumerator()
    let nextVal() = 
      if en.MoveNext() then en.Current
      else failwith "Unexpected end!" 
    let last = ref (nextVal())
    while Option.isNone !last do
      // yield None for each step of the source 'stepwise' computation
      yield None
      last := next()
    // yield one more None for this step
    yield None      
    // run the rest of the computation
    yield! rest (Option.get !last) }
  member x.Return v = seq { 
    // single-step computation that yields the result
    yield Some(v) }

let stepwise = Stepwise() 
// simple function for creating single-step computations
let one v = stepwise.Return(v)

Now, let's look at using the type:

let oneStep = stepwise {
  // NOTE: we need to explicitly create single-step 
  // computations when we call the let! binder
  let! y = one( "foo" ) 
  printfn "got: %A" y 
  return y + "bar" } 

let threeSteps = stepwise { 
  let! x = oneStep // compose computations :-)
  printfn "got: %A" x 
  let! y = one( x + "third" )
  printfn "got: %A" y
  return "returning " + y } 

If you want to run the computation step-by-step, you can simply iterate over the returned sequence, for example using the F# for keyword. The following also prints the index of the step:

for step, idx in Seq.zip threeSteps [ 1 .. 10] do
  printf "STEP %d: " idx
  match step with
  | None _ -> ()
  | Some(v) -> printfn "Final result: %s" v

Hope this helps!

PS: I found this problem very interesting! Would you mind if I addapted my answer into a blog post for my blog (http://tomasp.net/blog)? Thanks!