Generics of a Higher Kind

Moors, Piessens and Odersky's paper Generics of a Higher Kind (OOPSLA 2008) describes a new feature in the Scala language, which is rapidly gaining popularity (the language, not the feature, that is).

This new feature, higher-level generics, allows for type parameters in more places, which reduces code duplication. For example, consider the definition of a trait (class component in Scala) called Iterable, and a sub-trait List which extends it. Iterable has a method, filter, which is abstract; and a method remove, which is implemented in terms of filter. Like this:

trait Iterable[T] {
  def filter(p: T => Boolean): Iterable[T]
  def remove(p: T => Boolean): Iterable[T] = filter (x => !p(x))
}

trait List[T] extends Iterable[T] {
  def filter(p: T => Boolean): List[T]
  override def remove(p: T => Boolean): List[T] = filter (x => !p(x))
}

Note how List has to repeat the declaration of both methods, just to specialize the return type. With higher-order generics, the code is made as simple as:

trait Iterable[T, Container[X]] {
  def filter(p: T => Boolean): Container[T]
  def remove(p: T => Boolean): Container[T] = filter (x => !p(x))
}

trait List[T] extends Iterable[T, List]

This might seem trivial, but try to do this in Java or C# generics to see why it isn't. This particular case was solved elsewhere with "current type" keywords (e.g., in Eiffel), but higher-order generics are more general than that and can be used in other cases, where the type parameter isn't the current type and (obviously) a current-type solution won't cut it.