Cons_Forall.scala

// avoid warnings about the use of Higher Kinds
import scala.language.higherKinds

// implementing Forall
trait Forall[+G[_]] { def apply[A]: G[A] }
// note: this implementation is covariant, in order to make Null works

// The Cons type, based on Forall
type Cons[+A, +B] = Forall[({ type G[C] = ((A, B) => C) => C })#G]
def cons[A, B](a: A, b: B): Cons[A, B] = new Cons[A, B] {
  def apply[C]: ((A, B) => C) => C = { f => f(a, b) }
}

// The car and cdr methods are really simple
def car[A, B](c: Cons[A, B]): A = c[A]((a, b) => a)
def cdr[A, B](c: Cons[A, B]): B = c[B]((a, b) => b)

// Conventionnal end-of-the-list value
trait Empty
object Empty extends Empty
// that's why we needed a covariant version of Forall:
// an instance of Empty has type Empty.type which extends Empty

// A basic helper
def list[A1, A2, A3](a1: A1, a2: A2, a3: A3) = {
  cons(a1, cons(a2, cons(a3, Empty)))
}

// Now it's time to play

val l: Cons[Int, Cons[String, Cons[Boolean, Empty]]] = list(1, "a", true)

// checks that the types are right
car(l): Int
cdr(l): Cons[String, Cons[Boolean, Empty]]
car(cdr(l)): String

// checks that the values are right
println(car(l))
println(car(cdr(l)))
println(car(cdr(cdr(l))))