What is a kind anyway?

From Odersky’s paper Generics of a Higher Kind : *Conceptually, kinds are used to distinguish a type parameter that stands for a proper type, such as List[Int], from a type parameter that abstracts over a type constructor, such as List.*

And from the same paper: *generalisation to types that abstract over types that abstract over types.*

In simple words, higher-kinded types are high order types, like higher order functions types can be expressed as values ( passed as parameters and returned from functions).

What do languages with poor type-systems like Java do for expressing higher-kinded types?

They give up! A map or a filter over a Stream in Java returns a Stream and the programmer is asked to explicitly convert the stream back to the desired proper type.

stream.map(c -> c.length()).collect(Collectors.toList());

Libraries like Guava provide an endless list of static helpers with almost the same functionality in order to return the same type back.

Where in Scala a map over a List returns a List and a map over an Option returns an Option.

How would one achieve type soundness like this?

Higher-Kinded type is the answer.

How?

Lets start by writing a Functor using higher-kinded type.

trait Functor[F[_]]{ def map[A,B](fa: F[_ <:A])(f: A =>B ): F[B] }

Note that funny F[_]! It is not a type parameter, it is rather a kind. A higher order type.

Now lets reinvent a couple of Abstract Data Types.

sealed trait Maybe[+A] case class Just[A](value: A) extends Maybe[A] case object Nope extends Maybe[Nothing] sealed trait Try[+A] case class Failed(throwable: Throwable) extends Try[Nothing] case class Result[A](value: A) extends Try[A]

And their respective functors so we can map over them.

object MaybeFunctor extends Functor[Maybe]{ override def map[A, B](fa: Maybe[_<: A])(f:A=>B):Maybe[B]=fa match { case Nope=> Nope case Just(a) => Just(f(a)) } } object TryFunctor extends Functor[Try]{ override def map[A, B](fa: Try[_<:A])(f:A=>B): Try[B]=fa match { case failed @ Failed(throwable) => failed case Result(value) => Result(f(value)) } }

Nothing special so far. We can just call the specialised ..Functor and get the proper type. However with this abstraction we can express universal map that returns the most specific type.

def universalMap[A,B, F[_]]( source: F[_ <: A])(fn: A=> B)(implicit functor: Functor[F]): F[B] = { functor.map[A,B](source)(fn) }

Using the universal map.

val option: Maybe[String] = Nope implicit val choiceFunctor = MaybeFunctor val optionMapped: Maybe[Int] = universalMap(option)(_.length) val tryValue: Try[String] = Result("Foo") implicit val tryFunctor = TryFunctor val tryMapped: Try[Int] = universalMap(tryValue)(_.length)

Have you noticed the return types? the universal map returns a Maybe[T] when mapped over a Maybe[T] and Try[T] when mapped over a Try[T].