recursion.scala

object Recursion {

  case class Nat(n: Int) extends Ordered[Nat] {
    require(n >= 0)

    def toInt = n

    def +(that: Nat): Nat = Nat(n + that.n)
    def -(that: Nat): Nat = Nat(n - that.n)
    def *(that: Nat): Nat = Nat(n * that.n)
    override def compare(that: Nat) = n.compare(that.n)
  }

  object Nat {
    import scala.language.implicitConversions

    implicit def intToNat(n: Int): Nat = Nat(n)
    def Zero = Nat(0)
    def One = Nat(1)
  }

  import Nat.{Zero, One}

  /**
   * Type for a recursive function roughly like `type F[A, B] = F[A, B] => A => B` (if that were legal Scala).
   * This can represent something like ((((...(A => B) => A => B)...) => A => B) => A => B).
   */
  case class RecFun[A, B](f: RecFun[A, B] => A => B) extends (RecFun[A, B] => A => B) {
    override def apply(g: RecFun[A, B]) = f(g)
  }

  /**
   * The Z-combinator is a fixed-point combinator, identical to the Y-combinator but adapted for strict evaluation
   * by adding the extra function parameter `(a: A)`. I.e. the Y-combinator would be the same but with 
   * `def h = RecFun { (g: RecFun[A, B]) => f(g(g)) }`.
   */
  def Z[A, B](f: (A => B) => A => B): A => B = {
    def h = RecFun { (g: RecFun[A, B]) => (a: A) => f(g(g))(a) }
    h(h)
  }

  val pfact = {
    (f: Nat => Nat) =>
      (n: Nat) =>
        if (n == Zero) One
        else n * f(n - 1)
  }

  def fact = Z(pfact)

  val pfib = {
    (f: Nat => Nat) =>
      (n: Nat) =>
        if (n <= 1) n
        else f(n - 1) + f(n - 2)
  }

  def fib = Z(pfib)

}

import Recursion._
import Nat.intToNat