Cats a List of State Monads "fail fast" on <...>.sequence method?

user_5615112 0
Viewed 90

let's say we have a list of states and we want to sequence them:

import cats.data.State
import cats.instances.list._
import cats.syntax.traverse._


trait MachineState
case object ContinueRunning extends MachineState
case object StopRunning extends MachineState

case class Machine(candy: Int)

val addCandy: Int => State[Machine, MachineState] = amount =>
  State[Machine, MachineState] { machine =>
    val newCandyAmount = machine.candy + amount
    if(newCandyAmount > 10)
      (machine, StopRunning)
    else
      (machine.copy(newCandyAmount), ContinueRunning)
  }


List(addCandy(1),
     addCandy(2),
     addCandy(5),
     addCandy(10),
     addCandy(20),
     addCandy(50)).sequence.run(Machine(0)).value

Result would be

(Machine(10),List(ContinueRunning, ContinueRunning, ContinueRunning, StopRunning, StopRunning, StopRunning))

It's obvious that 3 last steps are redundant. Is there a way to make this sequence stop early? Here when StopRunning gets returned I would like to stop. For example a list of Either's would fail fast and stop sequence early if needed (because it acts like a monad).

For the record - I do know that it is possible to simply write a tail recursion that checks each state that is being runned and if some condition is satisfied - stop the recursion. I just want to know if there is a more elegant way of doing this? The recursion solution seems like a lot of boilerplate to me, am I wrong or not?

Thank you!:))

state sequence scala monads
1 Answers

There are 2 things here needed to be done.

The first is understanding what is actually happening:

  • State takes some state value, threads in between many composed calls and in the process produces some output value as well
  • in your case Machine is the state threaded between calls, while MachineState is the output of a single operation
  • sequence (usually) takes a collection (here List) of some parametric stuff here State[Machine, _] and turns nesting on the left side (here: List[State[Machine, _]] -> State[Machine, List[_]]) (_ is the gap that you'll be filling with your type)
  • the result is that you'll thread state (Machine(0)) through all the functions, while you combine the output of each of them (MachineState) into list of outputs
// ammonite

// to better see how many times things are being run
@ {
  val addCandy: Int => State[Machine, MachineState] = amount =>
    State[Machine, MachineState] { machine =>
      val newCandyAmount = machine.candy + amount
      println("new attempt with " + machine + " and " + amount)
      if(newCandyAmount > 10)
        (machine, StopRunning)
      else
        (machine.copy(newCandyAmount), ContinueRunning)
    }
  }
addCandy: Int => State[Machine, MachineState] = ammonite.$sess.cmd24$$$Lambda$2669/1733815710@25c887ca

@ List(addCandy(1),
       addCandy(2),
       addCandy(5),
       addCandy(10),
       addCandy(20),
       addCandy(50)).sequence.run(Machine(0)).value
new attempt with Machine(0) and 1
new attempt with Machine(1) and 2
new attempt with Machine(3) and 5
new attempt with Machine(8) and 10
new attempt with Machine(8) and 20
new attempt with Machine(8) and 50
res25: (Machine, List[MachineState]) = (Machine(8), List(ContinueRunning, ContinueRunning, ContinueRunning, StopRunning, StopRunning, StopRunning))

In other words, what you want is circuit breaking then .sequence might not be what you want.

As a matter of the fact, you probably want something else - combine a list of A => (A, B) functions into one function which stops next computation if the result of a computation is StopRunning (in your code nothing tells the code what is the condition of circuit break and how it should be performed). I would suggest doing it explicitly with some other function, e.g.:

@ {
  List(addCandy(1),
       addCandy(2),
       addCandy(5),
       addCandy(10),
       addCandy(20),
       addCandy(50))
    .reduce { (a, b) =>
      a.flatMap {
        // flatMap and map uses MachineState
        // - the second parameter is the result after all!
        // we are pattern matching on it to decide if we want to
        // proceed with computation or stop it

        case ContinueRunning => b // runs next computation
        case StopRunning     => State.pure(StopRunning) // returns current result without modifying it
      }
    }
    .run(Machine(0))
    .value
  }
new attempt with Machine(0) and 1
new attempt with Machine(1) and 2
new attempt with Machine(3) and 5
new attempt with Machine(8) and 10
res23: (Machine, MachineState) = (Machine(8), StopRunning)

This will eliminate the need for running code within addCandy - but you cannot really get rid of code that combines states together, so this reduce logic will be applied on runtime n-1 times (where n is the size of your list) and that cannot be helped.

BTW If you take a closer look at Either you will find that it also computes n results and only then combines them so that it looks like it's circuit breaking, but in fact isn't. Sequence is combining a result of "parallel" computations but won't interrupt them if any of them failed.

user_13051210
Related