Free.scala

// data Free f a = Pure a | Free (f (Free f a))
//
// instance Functor f => Monad (Free f) where
//     return = Pure
//     Pure a >>= k = k a
//     Free fm >>= k = Free (fmap (>>=k) fm)

sealed trait FreeM[S[+_], +A] {
  private case class FlatMap[S[+_], A, +B](a: FreeM[S, A], f: A => FreeM[S, B]) extends FreeM[S, B]

  def flatMap[B](f: A => FreeM[S, B]): FreeM[S, B] 
  def map[B](f: A => B): FreeM[S, B] = flatMap(a => Pure(f(a)))
}
case class Pure[S[+_], +A](a: A) extends FreeM[S, A] {
  def flatMap[B](f: A => FreeM[S, B]): FreeM[S, B]  = f(a)
}
case class Free[S[+_], +A](k: S[FreeM[S, A]]) extends FreeM[S, A] {
  // Sがmapないのでコンパイル通んないけどこんな感じ
  def flatMap[B](f: A => FreeM[S, B]): FreeM[S, B]  = Free(k.map{ _.flatMap(f)})

}