Higher-Kinded Types, Any useful?

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.


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] = {

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].




Leave a Reply

Name and email address are required. Your email address will not be published.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

You may use these HTML tags and attributes:

<a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <pre> <q cite=""> <s> <strike> <strong> 

%d bloggers like this: