Fib.scala

import scalaz._
import Scalaz._

object monads {

  def fix[A](f: (=> A) => A): A = f(fix(f))       //> fix: [A](f: => A => A)A
  
  type Gen[A] = (=> A) => A
  
  def gFib: Gen[Int => Int] = (self) => n =>
    if(n == 0 || n == 1) n
  	else {
  	  val s = self
  		s(n - 2) + s(n - 1)
    }                                             //> gFib: => => Int => Int => (Int => Int)
    
  def fibg = fix(gFib)                            //> fibg: => Int => Int
  
  fibg(10)                                        //> res0: Int = 55
  
  def gmFib[M[_]](implicit m: Monad[M]): Gen[Int => M[Int]] = self => n =>
  	if(n == 0 || n == 1) m pure n
  	else {
  		val s = self
  		for {
  			a <- s(n - 2)
  			b <- s(n - 1)
  	  } yield a + b
    }                                             //> gmFib: [M[_]](implicit m: scalaz.Monad[M])=> Int => M[Int] => (Int => M[Int]
                                                  //| )
    
  def fibgm = (n: Int) => fix(gmFib[Identity])(n).value
                                                  //> fibgm: => Int => Int
  
  fibgm(10)                                       //> res1: Int = 55
 
  type Dict[A, B, M[_]] = (A => M[Option[B]], (A, B) => M[Unit])
  
  def memo[A,B,M[_]](dict: Dict[A, B, M])(supe: => (A => M[B]))(implicit m: Monad[M]): A => M[B] = {
		val (check, store) = dict
		a => for {
			b <- check(a)
			value <- b match {
				case Some(b) => m pure b
				case None => {
					val sups = supe
					for {
						b <- sups(a)
						_ <- store(a, b)
					} yield b
				}
			}
		} yield value
  }                                               //> memo: [A, B, M[_]](dict: (A => M[Option[B]], (A, B) => M[Unit]))(supe: => A
                                                  //|  => M[B])(implicit m: scalaz.Monad[M])A => M[B]
  
  def memoCompose[A, B, M[_]: Monad](dict: Dict[A,B,M], gen: Gen[A => M[B]]): Gen[A => M[B]] =
  	{ self => memo(dict)(gen(self)) }         //> memoCompose: [A, B, M[_]](dict: (A => M[Option[B]], (A, B) => M[Unit]), gen
                                                  //| : => A => M[B] => (A => M[B]))(implicit evidence$1: scalaz.Monad[M])=> A =>
                                                  //|  M[B] => (A => M[B])

  def memoFib[M[_]: Monad](dict: Dict[Int, Int, M])(n: Int): M[Int] =
  	fix (memoCompose(dict, gmFib)) (n)        //> memoFib: [M[_]](dict: (Int => M[Option[Int]], (Int, Int) => M[Unit]))(n: In
                                                  //| t)(implicit evidence$2: scalaz.Monad[M])M[Int]

	type MapState[X] = State[Map[Int, Int], X]
 
  val mapDict: Dict[Int, Int, MapState] =
  	(a => gets(_.get(a)),(a, b) => modify(_ + (a -> b)))
                                                  //> mapDict  : (Int => monads.MapState[Option[Int]], (Int, Int) => monads.MapSt
                                                  //| ate[Unit]) = (<function1>,<function2>)

  def memoMapFib(n: Int): State[Map[Int, Int], Int] = memoFib(mapDict)(n)
                                                  //> memoMapFib: (n: Int)scalaz.State[Map[Int,Int],Int]
  	  
  def runMemoMapFib(n: Int) = memoMapFib(n) ! Map()
                                                  //> runMemoMapFib: (n: Int)Int
  	  
  runMemoMapFib(10)                               //> res2: Int = 55
}