FreeMonad.scala

  // コンテナ型Fに対してmapを持つ
  trait Functor[F[_]] {
    def map[A, B](fa: F[A])(f: A => B): F[B]
  }

  implicit def functorOps[F[_]: Functor, A](self: F[A]) = new {
    def map[B](f: A => B): F[B] = implicitly[Functor[F]].map(self)(f)
  }

  // Functor(F)と、計算値(A)を型パラメータでとる
  // mapとflatMapを持ち、Pureなら関数適用、InpureならFunctorを使ってFの計算値(A)にfを適用する
  sealed abstract class Free[F[_], A] {

    import Free._

    def map[B](f: A => B)(implicit F: Functor[F]): Free[F, B] =
      flatMap(a => Free.Pure(f(a)))

    def flatMap[B](f: A => Free[F, B])(implicit F: Functor[F]): Free[F, B] =
      this match {
        case Free.Pure(a)    => f(a)
        case Free.Impure(ff) => Free.Impure(F.map(ff)(_.flatMap(f)))
      }

  }

  object Free {

    // Freeの状態クラス
    // scalazのFreeはユーザーの入力待時などに一時計算を止めるsuspend,resumeを
    // 考慮した作りになっていて便利だが煩雑なのでresumeを考慮しないサンプルを書く
    case class Pure[F[_], A](a: A) extends Free[F, A]

    case class Impure[F[_], A](ff: F[Free[F, A]]) extends Free[F, A]

    def lift[F[_], A](fa: F[A])(implicit F: Functor[F]): Free[F, A] =
      Impure(F.map(fa)(a => Pure(a)))

    //関数を適用して、`implicit F: Functor[F]`を明示的に渡している。※FreeはFunctorを持っているのでここではFreeをわたす
  }

  trait Maybe[+A] extends Functor[Maybe] {
    def isEmpty: Boolean
    def get: A
    def map[A, B](fa: Maybe[A])(f: A => B): Maybe[B] =
      if (fa.isEmpty) Empty else Just(f(fa.get))
  }
  final case class Just[+A](x: A) extends Maybe[A] {
    def isEmpty = false
    def get = x
  }
  case object Empty extends Maybe[Nothing] {
    def isEmpty = true
    def get = throw new NoSuchElementException("Empty.get")
  }

  implicit val MaybeFunctor: Functor[Maybe] =
    new Functor[Maybe] {
      def map[A, B](fa: Maybe[A])(f: A => B): Maybe[B] =
        if (fa.isEmpty) Empty else Just(f(fa.get))
    }

  type MaybeM[A] = Free[Maybe, A]
  object MaybeM {
    def just[A](a: A): MaybeM[A] = Free.Pure(a)
    def empty[A]: MaybeM[A] = Free.lift[Maybe, A](Empty)
  }

  val r = for {
    x <- MaybeM.just(1)
    y <- MaybeM.just(2)
    z <- MaybeM.empty[Int]
  } yield x + y + z