How to make a lazy computational workflow?

Question

I'm trying to write a computational workflow which would allow a computation which can produce side effects like log or sleep and a return value

A usage example would be something like this

let add x y =
    compute {
        do! log (sprintf "add: x = %d, y= %d" x y) 
        do! sleep 1000
        let r = x + y
        do! log (sprintf "add: result= %d" r)
        return r
    }
...
let result = run (add 100 1000)

and I would like the side effects to be produced when executeComputation is called.

My attempt is

type Effect =    
    | Log of string
    | Sleep of int

type Computation<'t> = Computation of Lazy<'t * Effect list>

let private bind (u : 'u, effs : Effect list) 
         (f : 'u -> 'v * Effect list) 
         : ('v * Effect list) =
    let v, newEffs = f u
    let allEffects = List.append effs newEffs
    v, allEffects

type ComputeBuilder() =
    member this.Zero() = lazy ((), [])

    member this.Return(x) = x, []

    member this.ReturnFrom(Computation f) = f.Force()

    member this.Bind(x, f) = bind x f

    member this.Delay(funcToDelay) = funcToDelay

    member this.Run(funcToRun) = Computation (lazy funcToRun())

let compute = new ComputeBuilder()

let log msg = (), [Log msg]
let sleep ms = (), [Sleep ms]

let run (Computation x) = x.Force()

...but the compiler complains about the let! lines in the following code:

let x = 
    compute {
        let! a = add 10 20
        let! b = add 11 2000
        return a + b
        }

Error FS0001: This expression was expected to have type
    'a * Effect list
but here has type
    Computation<'b> (FS0001)

Any suggestions?

F# async workflows already give you a sleep function, and you could implement logging using the Writer or State monads. This should enable you to implement your workflow as a stack of async and one of those two other monads. — Mark Seemann
– Mark Seemann, Commented Nov 21, 2016 at 21:30
I understand that but I want to do it from scratch to figure out how it works. — vidi
– vidi, Commented Nov 21, 2016 at 21:46
It might interest you to look into a Continuation CE as well. That is one way to implement a lazy CE. This is basically how async is implemented. — Just another metaprogrammer
– Just another metaprogrammer, Commented Nov 22, 2016 at 12:20
My intention is to implement a partially functional IO monad in F#. It's obvious that I'm not yet there because my effects are not actually evaluated at the right moment so I will have to add some more laziness. I'll look at the continuation ce as well and see how it works. Thanks for the pointer! — vidi
– vidi, Commented Nov 22, 2016 at 12:40

Tomas Petricek · Accepted Answer · 2016-11-22 10:24:11Z

2

The main thing that is not right with your definition is that some of the members of the computation builder use your Computation<'T> type and some of the other members use directly a pair of value and list of effects.

To make it type check, you need to be consistent. The following version uses Computation<'T> everywhere - have a look at the type signature of Bind, for example:

let private bind (Computation c) f : Computation<_> = 
    Computation(Lazy.Create(fun () ->
      let u, effs = c.Value
      let (Computation(c2)) = f u
      let v, newEffs = c2.Value
      let allEffects = List.append effs newEffs
      v, allEffects))

type ComputeBuilder() =
    member this.Zero() = Computation(lazy ((), []))
    member this.Return(x) = Computation(lazy (x, []))
    member this.ReturnFrom(c) = c
    member this.Bind(x, f) = bind x f
    member this.Delay(funcToDelay:_ -> Computation<_>) = 
      Computation(Lazy.Create(fun () -> 
        let (Computation(r)) = funcToDelay()
        r.Value))

answered Nov 22, 2016 at 10:24

Tomas Petricek

244k22 gold badges397 silver badges563 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

vidi Over a year ago

I was using this fsharpforfunandprofit.com/posts/… as an example and it is not consistent, hence my confusion. Thanks!

Tomas Petricek Over a year ago

@vidi There is a bit of flexibility - the "delayed type" used in second argument of Combine, Run and returned by Delay is a good alternative design - but keeping everything consistent is easier :-)

Collectives™ on Stack Overflow

How to make a lazy computational workflow?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related