Y stuff

Y.scala

object Y {

  sealed trait List[+T]
  case class Cons[T](head: T, tail: List[T]) extends List[T]
  case object Nil extends List[Nothing]

  def almostLength[T](rec: List[T] => Int): List[T] => Int =
    (list: List[T]) => {
      list match {
        case Nil => 0
        case Cons(_, tail) => 1 + rec(tail)
      }
    }

  // This is a definition for Y in a strict, statically typed language
  // It Is *not* a Y *combinator* because it has free variables
  // "fix" is a free variable within the expression
  def fix[T, R](f: (T => R) => (T => R)): (T => R) =
    f(fix(f)(_))

  def length = fix(almostLength)
}