HList

HList.scala

package hlist

sealed trait List[A]
case class Cons[A](h: A, t: List[A]) extends List[A]
case object Nil extends List[Nothing]

sealed trait HList
case class :*:[+A, +B <: HList](h: A, t: B) extends HList {
  def :*:[C](x: C): C :*: A :*: B = hlist.:*:(x, this)
}
sealed trait HNil extends HList {
  def :*:[A, B <: HList](x: A): A :*: HNil = hlist.:*:(x, this)
}

sealed trait Nat
sealed trait Zero extends Nat
case class Succ[A <: Nat](n: A) extends Nat

trait HAppend[A <: HList, B <: HList, C <: HList] {
  def append(l1: A, l2: B): C
}

trait HFoldr[A, B, C <: HList] {
  def foldr(f: (A, B) => B, i: B, l: C): B
}

trait HNth[A <: HList, B <: Nat, C] {
  def nth(l: A, n: B): C
}

object Nat {
  val nzero = new Zero {}
  def succ[A <: Nat](n: A): Succ[A] = Succ(n)
  def pred[A <: Nat](n: Succ[A]): A = n match {
    case Succ(n) => n
  }
}

object HList {
  val hnil = new HNil {}
  def cons[A, B <: HList](h: A, t: B): A :*: B = :*:(h, t)
  def head[A, B <: HList](l: A :*: B): A = l match {
    case h :*: _ => h
  }
  def tail[A, B <: HList](l: A :*: B): B = l match {
    case _ :*: t => t
  }

  def pp(l: HList): String = l match {
    case h :*: t => "(" + h.toString + ", " + pp(t) + ")"
    case _       => "Nil"
  }

  implicit def appendHNil[A <: HList] = new HAppend[HNil, A, A] {
    def append(l1: HNil, l2: A): A = l2
  }

  implicit def appendHList[A <: HList, B <: HList, C <: HList, X](implicit i: HAppend[A, B, C]) = new HAppend[X :*: A, B, X :*: C] {
    def append(l1: X :*: A, l2: B): X :*: C = cons(head(l1), i.append(tail(l1), l2))
  }

  def append[A <: HList, B <: HList, C <: HList](l1: A, l2: B)(implicit i: HAppend[A, B, C]) =
    i.append(l1, l2)

  implicit def foldrNil[A, B] = new HFoldr[A, B, HNil] {
    def foldr(f: (A, B) => B, v: B, l: HNil): B = v
  }

  implicit def foldrHList[A, B, C <: HList](implicit i: HFoldr[A, B, C]) = new HFoldr[A, B, A :*: C] {
    def foldr(f: (A, B) => B, v: B, l: A :*: C): B =
      f(head(l), i.foldr(f, v, tail(l)))
  }

  def foldr[A, B, C <: HList](f: (A, B) => B, v: B, l: C)(implicit i: HFoldr[A, B, C]): B =
    i.foldr(f, v, l)


  implicit def nthZero[A, B <: HList] = new HNth[A :*: B, Zero, A] {
    def nth(l: A :*: B, n: Zero): A = head(l)
  }

  implicit def nthN[A <: HList, B <: Nat, C, D](implicit i: HNth[A, B, C]) = new HNth[D :*: A, Succ[B], C] {
    def nth(l: D :*: A, n: Succ[B]): C = i.nth(tail(l), Nat.pred(n))
  }

  def nth[A <: HList, B <: Nat, C](l: A, n: B)(implicit i: HNth[A, B, C]) =
    i.nth(l, n)

}

object HelloHList {
  import hlist.HList._
  import hlist.Nat._

  def main(args: Array[String]): Unit = {
    val l1 = 1 :*: "string" :*: 1.0 :*: hnil
    val l2 = "a" :*: 4 :*: null :*: hnil

    println(nth(append(l1, l2), nzero))
  }
}