How to stop state transition when state satisfies some condition?

Question

I'm quite new to scalaz/cats and have a question about State monad (cats or scalaz does not matter). Consider the following well-known example with Stack:

object StateTest {

  type Stack = List[Int]

  def main(args: Array[String]) = {
    println(transition.run(List(1, 2, 3, 4)).value) //(List(4),Some(3))
    println(transition.run(List(1, 2)).value) //(List(),None)

  }

  def transition: State[Stack, Option[Int]] = for {
    _ <- pop
    _ <- pop
    a <- pop
  } yield a

  def pop: State[Stack, Option[Int]] = State {
    case x::xs => (xs, Some(x))
    case Nil => (Nil, None)
  }
}

The problem is that I want to perform state transition (pop) till the state (List[Int]) satisfies some condition (I want to check List[Int]::isEmpty) and after that immediately stop.

In the current implementation I can only know if the state satisfies the condition after I invoke run.

Is it possible to do so in cats/scalaz with State monad or I need something else?

Answer 1

You would use the state monad parameterized by another monad representing the termination.

In general, such parameterized monads are called monad transformers. In this specific case, you would use the StateT monad transformer. Modulo some implementation details, StateT is equivalent to

type StateT[F[_], S, A] = S => F[(S, A)]

Now you can choose F to be Option, representing immediate termination.

import scalaz.StateT
import scalaz.std.option._

object StateTest {

  type Stack = List[Int]

  def main(args: Array[String]) = {
    println(transition.run(List(1, 2, 3, 4))) // Some((List(4), 3))
    println(transition.run(List(1, 2)))       // None
  }

  def transition: StateT[Option, Stack, Int] = for {
    _ <- pop
    _ <- pop
    a <- pop
  } yield a

  def pop: StateT[Option, Stack, Int] = StateT {
    case x::xs => Some((xs, x))
    case Nil   => None
  }
}

If you want to return some value of type B even in the case of early termination, you can use Either[B, ?] instead of Option to parameterize StateT:

type ErrorOr[A] = Either[String, A]

def pop1: StateT[ErrorOr, Stack, Int] = StateT {
  case x::xs => Right((xs, x))
  case Nil   => Left("Cannot pop from an empty stack.")
}