hfix.scala

package test

trait ListF[+A, +S]
trait Nil extends ListF[Nothing, Nothing]
object Nil extends Nil
case class Cons[A, +S](x: A, xs: S) extends ListF[A, S]

case class Fix[F[_]](f: F[Fix[F]])

object list {
  type List[A] = Fix[ListF[A, ?]]
  def nil[A] = Fix[ListF[A, ?]](Nil)
  def cons[A] = (x:A, xs: List[A]) => Fix[ListF[A, ?]](Cons(x, xs))
}

trait Inductive
case class HFix[F[_], R <: Inductive](f: F[R]) extends Inductive
trait INil extends Inductive

object hlist {
  def hnil = HFix[ListF[Nil, ?], INil](Nil)
  def hcons[X, XS <: Inductive](x: X, xs: XS) = HFix[ListF[X, ?], XS](Cons(x, xs))

  val test = hcons(1, hcons("bar", hnil))
}

object coproduct {
  sealed trait :+:[+H, +T]
  final case class Inl[+H, +T](head : H) extends :+:[H, T]
  final case class Inr[+H, +T](tail : T) extends :+:[H, T]

  def r[T](v: T) = HFix[:+:[T, ?], INil](Inl(v))
  def l[T] = new {
    def apply[C <: Inductive](c: C) = HFix[:+:[T, ?], C](Inr(c))
  }

  val test = l[Double](l[Int](r("bar")))
}