Sloth.scala

trait Ref[A] {
    def get: A
    def set(a: A)
}

type *[A, B] = (A, B)

trait Lazy {
  type T[A]
  def mk[A](f: () => A): T[A]
  def get[A](t: T[A]): A
  def map[A, B](f: A => B): T[A] => T[B]
  def `return`[A](a: A): T[A]
  def join[A](t: T[T[A]]): T[A]
  def bind[A, B](f: A => T[B]): T[A] => T[B]
  def >>=[A, B](t: T[A]): (A => T[B]) => T[B]
  /* The argument is a lazy defue that might refer to itself.
   * Tie the defue to itself using reference. */
  def tie[A](f: T[A] => T[A]): T[A] 
}

trait LazyThunk extends Lazy { 
	type T[A] = () => A
}

/* However, the thunk need to be edefuated each time get is used,
 * instead of at most once. This is outrageous! This is unfair!
 * It can be fixed by caching the result - the thunk is only edefuated
 * if the cache is empty. */
trait LazyOption extends Lazy {
  	type T[A] = Ref[Option[A]] * (() => A)
}

/* Notice how there is two components for a Lazy: a thunk and a cache.
 * Here is a pretty cool trick: instead of having two components,
 * just cache the thunk!
 * This is called tagless because we no longer use algebraic data type,
 * which tag the defue.
 * We just have a uniform way to handle the defue. */
trait LazyTagless extends Lazy { 
    type T[A] = Ref[() => A ]
}


/* Notice how most definition of lazy can be derived from other?
 * Try to lookup how module works and refactor them. */

/* To test that implementation work, do some infinite stream */
trait StreamSig {
  val L: Lazy

  case class Stream[A](value: L.T[A * Stream[A]])
  def hd[A](s: Stream[A]): A
  def tl[A](s: Stream[A]): Stream[A] /* Be as lazy as possible. */
  def mk[A](t: () => A * Stream[A]): Stream[A]
  def gen[A, B](f: A => A): L.T[A] => Stream[A]
  def map[A, B](f: A => B): Stream[A] => Stream[B]
  def zip[A, B](s: Stream[A]): Stream[B] => Stream[A * B]
  def zipWith[A, B, C](f: A * B => C): Stream[A] => Stream[B] => Stream[C]
  def takeWhile[A](f: A => Boolean): Stream[A] => List[A]
  def app[A](f: List[A] => Stream[A]): Stream[A]
  def fib(s: Stream[Int]): Stream[Int]
  def join[A](s: Stream[Stream[A]]): Stream[A]
}

trait Stream extends StreamSig {
  val l: Lazy
}