Experiments with type-level foldables

TLFoldable.scala

sealed trait Nat
trait Succ[T <: Nat] <: Nat
trait Zero <: Nat

sealed trait Bool { type Not <: Bool }
trait True <: Bool { type Not = False }
trait False <: Bool { type Not = True }

trait Foldable[Base] {

  // \forall R
  type R <: AnyRef

  trait Fun[I <: Base] {
    type Out <: R
  }
  type ~>[I <: Base, O <: R] = Apply[I] { type Out = O }

  type Apply[I <: Base] <: Fun[I]
  def Apply[B <: Base](implicit app: Apply[B]): app.type = app
}

trait FoldNat extends Foldable[Nat] {
  type Z <: R
  type S[X <: R] <: R

  implicit val foldZero: Zero ~> Z
  implicit def foldSucc[N <: Nat](implicit app: Apply[N]): Succ[N] ~> S[app.Out]
}

object IsEven extends FoldNat {

  type R = Bool
  type Z = True
  type S[X <: Bool] = X#Not

  class Apply[I <: Nat](_out: => Boolean) extends Fun[I] {
    lazy val out = _out
  }
  implicit val foldZero: Zero ~> Z = new Apply[Zero](true) { type Out = Z }
  implicit def foldSucc[N <: Nat](implicit app: Apply[N]): Succ[N] ~> S[app.Out]
    = new Apply[Succ[N]](!app.out) { type Out = S[app.Out] }

  implicitly[     S[True] =:= False ]
  implicitly[  S[S[True]] =:= True  ]
  implicitly[ S[S[False]] =:= False ]

  val res0 = Apply[Zero]
  val res1 = Apply[Succ[Zero]]
  val res2 = Apply[Succ[Succ[Zero]]]
  val res3 = Apply[Succ[Succ[Succ[Zero]]]]
  val res4 = Apply[Succ[Succ[Succ[Succ[Zero]]]]]

  implicitly[ res0.Out =:= True  ]
  implicitly[ res1.Out =:= False ]
  implicitly[ res2.Out =:= True  ]
  implicitly[ res3.Out =:= False ]
  implicitly[ res4.Out =:= True  ]

  println(res4.out)
}