State

case class State[A,S](val run: S => (A,S))

object State {

  implicit def stateMonad[S]: Monad[({ type λ[ɑ] = State[ɑ,S] })#λ] =
    new Monad[({ type λ[ɑ] = State[ɑ,S] })#λ] {

      def pure[A](a: A): State[A,S] =
        State(s => (a, s))

      def flatMap[A,B](ma: State[A,S])(f: A => State[B,S]): State[B,S] =
        State { s =>
          val (a, s2) = ma.run(s)
          f(a).run(s2)
        }
    }
}