scalaz Free Monad control break and pause for a chain of computations

Question

I have a chain of computations which changes the state of Context:

case class Context(...)
type Step = (Context => Context)
val step1: Step = ctx => { ctx.copy(...) }
val step2: Step
val step3: Step
// ...
val stepN: Step
val chain = List(step1, step2, step3, ..., stepN).toStream

And I would like to introduce the return value of computation to control the flow of that chain:

trait Cont
case class Break[Context](ctx: Context) extends Cont
case class Pause[Context](ctx: Context) extends Cont
case class Continue[Context](ctx: Context) extends Cont

Break - means cancelling chain after executing current step,

Pause - means suspending computation on current step after executing it, with ability to resume the next step later (and check if it's resumable?)

Continue - means normal continuation of the flow.

Each step should return the current value of context wrapped in Cont.

Currently I'm doing that by unfolding the stream of steps (val chain: Stream[Cont[Step]]) and checking the chain.isEmpty and chain.head to check if there's some computation left.

How can I do that using Free monads in scalaz?

Matthias Matthias · Accepted Answer · 2017-01-18T13:53:16

You can achieve this by using the continuation monad of scalaz, scalaz.Cont.

Sadly there is no documentation and there are no examples on how to use scalaz.Cont. So, to get a basic understanding of continuations and what they are for, have a look at

wiki.haskell.org/All_About_Monads#The_Continuation_monad and at
en.wikibooks.org/wiki/Haskell/Continuation_passing_style.
For using the Free monad, a recommended reading is Functional and Reactive Domain Modelling by Debasish Ghosh.

The essence of using continuations is, that we will not return values from our computations but pass the control to a continuation (often the variable k is used) and the continuation specifies what happens next.

This said, let us look at how this would look like in your concrete example:

first some type definitions ; notice that a Continuation, a "next step", is a function which takes a Context and returns something of type Return
```
case class Context(i: Int)
type Continuation = Context => Return
```

then define some types to control the flow within our computation chain ; note that Pause also returns a Continuation since we want to be able to continue the computation later

trait Return
case class Break(context: Context) extends Return
case class Pause(context: Context, continuation: Continuation) extends Return
case class Done(context: Context) extends Return

next we define our steps as classes in order to be able to use them with the Free monad ...

trait Step[A]
case class Step1(c: Context) extends Step[Context]
case class Step2(c: Context) extends Step[Context]
case class Step3(c: Context) extends Step[Context]

... and lift them into the context of the Free monad

type Command[A] = Free[Step, A]
protected implicit def liftStep[A](step: Step[A]): Command[A] =
    Free.liftF(step)

def step1(c: Context): Command[Context] = Free.liftF(Step1(c))
def step2(c: Context): Command[Context] = Free.liftF(Step2(c))
def step3(c: Context): Command[Context] = Free.liftF(Step3(c))

now we build our chain of computations ; note that we pass the result of the previous computation (e.g. c1) into the next (e.g. step2(c1)) ; if this should happen more implicitly, maybe the state monad should be considered for passing state from continuation to continuation
```
val script = for {
  c0 <- Free.point(Context(0))
  c1 <- step1(c0)
  c2 <- step2(c1)
  c3 <- step3(c2)
} yield c3
```

and define an interpreter (i.e. step) which evaluates the single steps ; see the comments for an explanation of how the single steps can control the flow of the computation

type Process[A] = Cont[Return, A]
val step: Step ~> Process = new (Step ~> Process) {
  override def apply[A](action: Step[A]): Process[A] = action match {
    case Step1(c) =>
      Cont { k: Continuation =>
        // call next computation with context value set to 1
        k(c.copy(i = 1))
      }
    case Step2(c) =>
      Cont { k: Continuation =>
        // pause computation ; to be able to resume, continuation k is returned
        Pause(c.copy(i = 2), k)
      }
    case Step3(c) =>
      Cont { k: Continuation =>
        // after the pause, the computation is resumed here
        k(c.copy(i = 3))
        // alternatively: break computation (i.e. not resumable)
        //Break(c.copy(i = 3))
      }
  }
}

run the script with the interpreter step to get the continuation
```
val process: Cont[Return, Context] = script.foldMap(step)
```
run the continuation process ; note that the run method expects a Continuation which will be the continuation of the last computation step (i.e. c will be Context(3) from Step3)
```
var result = process.run(c => Done(c))
```

at last, write some code to execute the complete chain and continue if the computation was just paused or stop if Break or Done is the result

var continue = true
do {
  continue = result match {
    case Pause(c, continuation) =>
      println(s"Pause: $c")
      result = continuation(c)
      true
    case Break(c) =>
      println(s"Break: $c")
     false
    case Done(c) =>
      println(s"Done: $c")
     false
   }
} while(continue)

The result is:

Pause: Context(2)
Done: Context(3)

scalaz Free Monad control break and pause for a chain of computations

1 Answers