free monad

gistfile1.scala

import scalaz._
import Scalaz._

object FreeMonad extends App {
  class FreeMonad[F[_]: Monad] {
    sealed abstract class Free[A]
    case class Val[A](value: A) extends Free[A]
    case class Wrap[A](value: F[Free[A]]) extends Free[A]
    implicit val freeMonad = new Monad[Free] {
      def pure[A](x: => A) = Val(x)
      def bind[A, B](a: Free[A], f: A => Free[B]): Free[B] = {
        a match {
          case Val(value) => f(value)
          case Wrap(value) => Wrap(for (x <- value) yield bind(x, f))
        }
      }
    }
    
    def wrap[A](value: F[Free[A]]): Free[A] = Wrap(value)
  }

  def test() = {
    val free = new FreeMonad[List]
    import free._

    val nums = for {
      x <- wrap(List(1.pure[Free], 2.pure[Free]))
      y <- wrap(List(10.pure[Free], 20.pure[Free]))
      z <- 100.pure[Free]
    } yield x + y + z

    println(nums)
  }

  test()
}