RefactoringPuzzle.scala

object RefactorPuzzle {
  import scala.language.higherKinds
  trait Monad[F[_]] {
    def point[A](a: => A): F[A]
    def flatMap[A, B](ma: F[A])(f: A => F[B]): F[B]
    def map[A, B](ma: F[A])(f: A => B): F[B]
  }

  implicit def optionMonad = new Monad[Option] {
    def point[A](a: => A): Option[A] = Some(a)
    def flatMap[A, B](ma: Option[A])(f: A => Option[B]): Option[B] = ma.flatMap(f)
    def map[A, B](ma: Option[A])(f: A => B): Option[B] = ma.map(f)
  }

  implicit def IntRdrMonad = new Monad[IntRdr] {
    def point[A](a: => A): IntRdr[A] = IntRdr(a)
    def flatMap[A, B](ma: IntRdr[A])(f: A => IntRdr[B]): IntRdr[B] = ma.flatMap(f)
    def map[A, B](ma: IntRdr[A])(f: A => B): IntRdr[B] = ma.map(f)
  }

  case class IntRdr[+A](read: Int => A) {
    def map[B](f: A => B): IntRdr[B] =
      IntRdr(f compose read)

    def flatMap[B](f: A => IntRdr[B]): IntRdr[B] =
      IntRdr(n => f(read(n)).read(n))
  }

  object IntRdr {
    def apply[A](a: A): IntRdr[A] =
      IntRdr(_ => a)
  }

  def sequence[M[_]: Monad, A](as: List[M[A]]): M[List[A]] = {
    val m = implicitly[Monad[M]]
    as.foldRight(m.point(List[A]())) { (ma, acc) =>
      m.flatMap(ma) { a: A => m.flatMap(acc) { rest: List[A] => m.point(a :: rest) } }
    }
  }

  def runOptions[A](x: List[Option[A]]): Option[List[A]] = sequence(x)
  def runIntRdrs[A](x: List[IntRdr[A]]): IntRdr[List[A]] = sequence(x)
}