Higher-kinded types encoded as path-dependent types

gistfile1.scala

trait λ {
  type α
}

trait Functor extends λ {
  type α <: λ

  def map[A,B](x: α { type α = A })(f: A => B): α { type α = B }
}

sealed trait ListRep extends λ { self =>
  def isEmpty: Boolean
  def uncons: Option[(α, ListRep { type α = self.α })]

  def foldRight[B](z: B)(f: (α, B) => B): B

  def toList: List[α] = foldRight(scala.List[α]())(_ :: _)
}
abstract class Nil extends ListRep { 
  val isEmpty = true
  def uncons = None
  def foldRight[B](z: B)(f: (α, B) => B) = z
}
abstract class Cons extends ListRep { self =>
  def head: α
  def tail: ListRep {
    type α = self.α
  }

  val isEmpty = false
  def uncons = Some((head, tail))
  def foldRight[B](z: B)(f: (α, B) => B) =
    f(head, tail.foldRight(z)(f))
}

object List extends Functor {
  type α = ListRep

  type List[A] = ListRep { type α = A }

  def map[A,B](as: List[A])(f: A => B) =
      as.foldRight(nil[B])((a, bs) => cons(f(a), bs))
  
  def nil[A]: List[A] = new Nil {
    type α = A
  }

  def cons[A](a: A, as: List[A]): List[A] = new Cons {
    type α = A
    val head = a
    val tail = as
  }
}

object HigherKinded {
  def unzip[F <: Functor, A, B](F: F)(abs: F.α { type α = (A,B) })
    : (F.α { type α = A }, F.α { type α = B }) =
      (F.map(abs)(_._1), F.map(abs)(_._2))
}

object Test {
  import List._

  val xs: List[(Int, Int)] = cons((1,2), cons((2,3), nil))

  def foo = HigherKinded.unzip(List)(xs)
}