StateMonadTutorial.scala

import cats.effect._
import cats.implicits._
import cats.data.State
import cats.data.OptionT
import cats.Functor
import cats.data.EitherT
import cats.kernel.Order

object Test extends IOApp {
  def run(args: List[String]): IO[ExitCode] = {
    import Parse._
    val result = combineStates().run(RInput(List(RSymM, RSymD, RSymM, RSymC, RSymL, RSymC, RSymM)))      
    IO {
      println(result.value)
    }.as(ExitCode.Success)
  }
}

object Parse {

  case class RInput(stack:List[ARoman])

  abstract class ARoman(val symbol:Char, val value:Int)
  case object RSymI extends ARoman('I', 1)
  case object RSymV extends ARoman('V', 5)
  case object RSymX extends ARoman('X', 10)
  case object RSymL extends ARoman('L', 50)
  case object RSymC extends ARoman('C', 100)
  case object RSymD extends ARoman('D', 500)
  case object RSymM extends ARoman('M', 1000)

  object ARoman {
    implicit val order:Order[ARoman] = Order.from { (a, b) => a.value.compareTo(b.value)}
  }

  type RState[A] = State[RInput, A]

  sealed trait Expr[A]
  case class ExprLit[A](value:A) extends Expr[A]
  case class ExprBinPlus[A](a:A, b:A) extends Expr[A]
  case class ExprBinMinus[A](a:A, b:A) extends Expr[A]

  def pop():RState[ARoman] = State {
    case RInput(x :: xs) => 
      (RInput(xs), x)
  }
 
  def peek():RState[Option[ARoman]] = State { in =>
    (in, in.stack.headOption)
  }
  
  // combine: state[aroman] + state[option(aroman)] to state[expr]
  def pairwise():RState[Expr[ARoman]] = for {
    a <- pop()
    b <- (OptionT(peek()) *> OptionT(pop().map(Option(_)))).value
    expr = b.fold[Expr[ARoman]](ExprLit(a)) { b => 
      if(a >= b) ExprBinPlus(a, b) else ExprBinMinus(b, a)
    }
  } yield expr

  def combineStates():RState[List[Expr[ARoman]]] = for {
    expr <- pairwise()
    s    <- State.get
    exprList <- if(s.stack.size > 1) combineStates() else pop().map(it => List(ExprLit(it)))
  } yield expr :: exprList

}