Encoding of List using rank-3 types (Runar's code from http://paste.pocoo.org/show/463632/)

gistfile1.scala

import scalaz._
import Scalaz._

type List[A] = Forall[({type f[B] = ((A, B) => B, B) => B})#f]

val nil: Forall[List] = new Forall[List] {
  def apply[A] = new List[A] {
    def apply[B] = (c, n) => n
  }
}

val cons: Forall[({type f[x] = (x, List[x]) => List[x]})#f] =
  new Forall[({type f[x] = (x, List[x]) => List[x]})#f] {
    def apply[A] = (h, t) => new List[A] {
      def apply[B] = (c, n) => c(h, t.apply(c, n))
    }
  }

def map[A, B](f: A => B, as: List[A]): List[B] =
  as.apply[List[B]]((h, t) => cons.apply(f(h), t), nil.apply[B])