How to use cats and State Monad

5.1k views Asked by At

I've used cats for the first time to solve day 1 of advent of code and I'm wondering if it's possible to improve things.

Given a method update with the following signature def update(i: Instruction): PosAndDir => PosAndDir

I've come up with :

val state: State[PosAndDir, List[Unit]] = instructions.map(i => State.modify(update(i))).toList.sequenceU
val finalState = state.runS(PosAndDir(Pos(0, 0), North)).value

And also

  def update2(i: Instruction): State[PosAndDir, Option[Pos]] =
    State.modify(update(i)).inspect(pad => if (i == Walk) Some(pad.pos) else None)
  …
  val state = instructions.map(update2).toList.sequenceU
  val positions = state.runA(PosAndDir(Pos(0, 0), North)).value.flatten

More precisely, questions are :

  1. why do we need to call .value (with scalaz, it's transparent) ?
  2. is there a way to write update2 with a for comprehension to improve readability ?
  3. is there an Applicative instance for Seq in cats (I know there is not in scalaz). ?
  4. any idea to improve the code ?
1

There are 1 answers

1
Odomontois On BEST ANSWER
  1. cats defines State[S, A] as an alias for stack-safe StateT[Eval, S , A] which is StateT[Trampoline, S, A] in scalaz terms, so runS returns Eval[A], where value will be run without stackoverflow even for very long flatMap sequences.
  2. Using some more additional imports

    import cats.data.{State, StateT}
    import cats.MonadState
    import cats.syntax.functorFilter._
    import cats.instances.option._
    

    and some preparations

    type Walk[x] = StateT[Option, PosAndDir, x]
    val stateMonad = MonadState[Walk, PosAndDir]
    
    import stateMonad._
    

    you can make your function look like this

    def update2(i: Instruction): StateT[Option, PosAndDir, Pos] =
      for (pad ← get if i == Walk) yield pad.pos
    

    not that this solution will not work in 2.12 due to this improvement, you can make it work with this workaround

    implicit class FunctorWithFilter[F[_] : FunctorFilter, A](fa: F[A]) {
      def withFilter(f: A ⇒ Boolean) = fa.filter(f)
    }
    
  3. There is no instances for Seq, this answer describes why. While there are some non-orthodox instances in the alleycats project. I'm not really sure if you need for Applicative[Seq], from your code you are rather have need for Traverse[Seq], or if you replace your sequence with sequence_ even Foldable[Seq]. Good news there is Foldable[Iterable] in the alleycats, and here is my attempt to define something lookalike for Seq instance

    implicit val seqInstance = new MonadFilter[Seq] with Traverse[Seq] {
      def traverse[G[_] : Applicative, A, B](fa: Seq[A])(f: (A) ⇒ G[B]): G[Seq[B]] =
        fa match {
          case head +: tail ⇒ f(head).map2(traverse(tail)(f))(_ +: _)
          case _empty ⇒ Seq.empty[B].pure[G]
        }
    
      def foldLeft[A, B](fa: Seq[A], b: B)(f: (B, A) ⇒ B): B = fa.foldLeft(b)(f)
    
      def foldRight[A, B](fa: Seq[A], lb: Eval[B])(f: (A, Eval[B]) ⇒ Eval[B]): Eval[B] =
        fa match {
          case head +: tail ⇒ f(head, foldRight(tail, lb)(f))
          case _empty ⇒ lb
        }
    
      def pure[A](x: A): Seq[A] = Seq(x)
    
      def empty[A]: Seq[A] = Seq.empty[A]
    
      def flatMap[A, B](fa: Seq[A])(f: (A) ⇒ Seq[B]): Seq[B] = fa.flatMap(f)
    
      def tailRecM[A, B](a: A)(f: (A) ⇒ Seq[Either[A, B]]): Seq[B] = {
        @tailrec def go(seq: Seq[Either[A, B]]): Seq[B] =
          if (seq.contains((_: Either[A, B]).isLeft)) 
            go(seq.flatMap {
              case Left(a) ⇒ f(a)
              case b ⇒ Seq(b)
            }) else seq.collect { case Right(b) ⇒ b }
    
        go(Seq(Left(a)))
      }
      override def mapFilter[A, B](fa: Seq[A])(f: (A) ⇒ Option[B]): Seq[B] = 
        fa.flatMap(f(_).toSeq)
    }
    
  4. didn't spent much time but here is my attempt to simplifying some parts via the Monocle library:

    import cats.{MonadState, Foldable, Functor}
    import cats.instances.option._
    import cats.syntax.foldable._
    import cats.syntax.functor._
    import cats.syntax.functorFilter._
    import monocle.macros.Lenses
    
    @Lenses
    case class Pos(x: Int, y: Int)
    
    sealed abstract class Dir(val cmd: Pos ⇒ Pos)
    
    case object South extends Dir(Pos.y.modify(_ - 1))
    case object North extends Dir(Pos.y.modify(_ + 1))
    case object East extends Dir(Pos.x.modify(_ + 1))
    case object West extends Dir(Pos.x.modify(_ - 1))
    
    @Lenses
    case class PosAndDir(pos: Pos, dir: Dir)
    
    val clockwise = Vector(North, East, South, West)
    val right: Map[Dir, Dir] = clockwise.zip(clockwise.tail :+ clockwise.head).toMap
    val left: Map[Dir, Dir] = right.map(_.swap)
    
    sealed abstract class Instruction(val cmd: PosAndDir ⇒ PosAndDir)
    case object TurnLeft extends Instruction(PosAndDir.dir.modify(left))
    case object TurnRight extends Instruction(PosAndDir.dir.modify(right))
    case object Walk extends Instruction(pd ⇒ PosAndDir.pos.modify(pd.dir.cmd)(pd))
    
    def runInstructions[F[_] : Foldable : Functor](instructions: F[Instruction])(start: PosAndDir): PosAndDir =
      instructions.map(i => State.modify(i.cmd)).sequence_.runS(start).value