initial.scala

// origial: https://gist.github.com/koropicot/6265729
// NYSL Version 0.9982

trait Functor[F[_]] {
  def fmap[A, B](fa: F[A])(f: A => B): F[B]
}

class Const[A, +B](val value: A)

class Identity[A](val value: A)

object Functor {
  implicit def ConstFunctor[X] = new Functor[({ type F[Y] = Const[X, Y] })#F] {
    type F[Y] = Const[X, Y]
    def fmap[A, B](cf: F[A])(f: A => B) = new Const(cf.value)
  }

  implicit def IdentityFunctor[X] = new Functor[Identity] {
    def fmap[A, B](fa: Identity[A])(f: A => B) = new Identity(f(fa.value))
  }
}

object Initial {
  def c1[Self, F1[_], F2[_]](v1: F1[Self])
  (implicit
   fc1: Functor[F1],
   fc2: Functor[F2],
   inj: Self => Initial[F1, F2]) =
     new Initial(Left(fc1.fmap(v1)(inj)), fc1, fc2)

  def c2[Self, F1[_], F2[_]](v2: F2[Self])
  (implicit
   fc1: Functor[F1],
   fc2: Functor[F2],
   inj: Self => Initial[F1, F2]) =
     new Initial(Right(fc2.fmap(v2)(inj)), fc1, fc2)
}

class Initial[F1[_], F2[_]] private[Initial](value: Either[F1[Initial[F1, F2]],
                                                           F2[Initial[F1, F2]]],
                                             fc1: Functor[F1],
                                             fc2: Functor[F2])
{
  def cata[T](f1: F1[T] => T, f2: F2[T] => T): T =
    this.value match {
      case Left(v1)  => f1(fc1.fmap(v1){ _.cata[T](f1, f2) })
      case Right(v2) => f2(fc2.fmap(v2){ _.cata[T](f1, f2) })
    }
}

object Nat {
  type Z[X] = Const[Unit, X]

  implicit def initialToNat(initial: Initial[Z, Identity]): Nat =
    new Nat(initial)

  implicit def natToInitial(nat: Nat): Initial[Z, Identity] =
    nat.initial

  def Zero: Nat =
    Initial.c1[Nat, Z, Identity](new Const())

  def Succ(n : Nat): Nat =
    Initial.c2[Nat, Z, Identity](new Identity(n.initial))
}

class Nat private[Nat](val initial: Initial[Nat.Z, Identity]) {
  def cata[T](zero: T, succ: T => T): T =
    initial.cata[T](_ => zero, f => succ(f.value))
}

object Main {
  def main(args: Array[String]): Unit = {
    def plusNat(a: Nat, b: Nat) = a.cata(b, Nat.Succ)

    val _10 = intToNat(10)
    val _32 = intToNat(32)

    val _42 = plusNat(_10, _32)

    println(natToInt(_42))
  }

  def intToNat(i: Int): Nat = {
    if (i == 0)
      Nat.Zero
    else
      Nat.Succ(intToNat(i - 1))
  }

  def natToInt(n: Nat): Int =
    n.cata[Int](0, _ + 1)
}