One of the more frequent comments that Haskell developers make about other programming languages is that they lack something called higherkinded types.
Which leads to a communication problem. Since those programming languages don’t have a way to express either kinds or HKTs, it is hard for nonHaskell developers to understand what they are missing out on.
In the end, the words of the Haskell developer are dismissed as mad ravings, and everybody moves on.
But once you start working with Haskell, it makes it very intuitive for you to understand both kinds and higherkinded types.
In this article, I will introduce you to the concept of kinds. Then, we’ll use our newfound knowledge to understand what are higherkinded types and what makes them useful.
What’s the type of a type?
In one sentence, kinds are to types what types are to values.
We can imagine a universe of values, populated by values like "hello"
, True
, [1, 2, 3]
. And we can imagine a universe of types governing those values, with types such as String
, Bool
, and [Int]
.
But in Haskell, we have the third universe governing types, which is populated by kinds.
*
* > *
* > * > *
For now, the most important thing about them is that they show the arity of a type (if we think of that type as a function).
You can read *
as Type
. In fact, a commonly used GHC extension called NoStarIsType
disables the use of *
in favor of Type
. But since GHC still uses *
by default, I’ll use that in the article.
To see the kind signature of a type, you can use the :k
command in GHCi.
Let’s look at some examples.
All concrete types, such as String
, Bool
, and [Int]
have the kind of *
.
> :k String
String :: *
> :k Bool
Bool :: *
> :k [Int]
[Int] :: *
To have a more complex kind, you need a polymorphic type – a type with type variables in its definition. In other languages, type variables are also called generics.
For example, look at how Maybe
(Haskell’s optional type) is defined in Haskell.
data Maybe a = Nothing  Just a
Maybe
takes a type variable – a
– and returns a type – Maybe a
– that might contain an item of a
.
Hence, it has the kind of * > *
.
> :k Maybe
Maybe :: * > *
Maybe
by itself is a typelevel function, a type constructor. As such, there are no actual values of type Maybe
– there are only values of types like Maybe Int
, Maybe String
, etc. We can say that Maybe
is uninhabited.
Once you provide a type to Maybe
, it will return a concrete type that contains values.
> :k Maybe Bool
Maybe Bool :: *
> :k Maybe String
Maybe String :: *
To have a kind of * > * > *
, you need to have two type variables.
A classic example of this is Either
(Haskell’s result type).
data Either a b = Left a  Right b
It takes two types – a
and b
– and returns a concrete type.
It can be applied with zero, one, or two arguments. Its kind signature varies accordingly.
> :k Either
Either :: * > * > *
> :k Either String
Either String :: * > *
> :k Either String Int
Either String Int :: *
Most programming languages support these kinds of types – the most common examples of these are list and array types.
But if concrete types are like values and polymorphic types are like functions, can we have something akin to higherorder functions on types?
In other words, can we have a kind like (* > *) > * > *
?
Turns out, yes. In Haskell, it’s kinda easy.
What are higherkinded types in Haskell?
One of the things that separates Haskell from most programming languages is the existence of higherkinded types.
Higherkinded types are types with kind signatures that have parenthesis somewhere on the left side, like this: (* > *) > * > *
.
This means that they are types that take a type like Maybe
as an argument. In other words, they abstract over polymorphic types.
A common example is a type for any collection.
data Collection f a = Collection (f a) deriving (Show)
> :k Collection
Collection :: (* > *) > * > *
This type takes a wrapper f
(such as []
) and a concrete type a
such as Int
and returns a collection of f a
(such as Collection [] Int
).
a :: Collection [] Int
a = Collection [1,2,3]
b :: Collection [] String
b = Collection ["call", "me", "ishmael"]
c :: Collection Maybe String
c = Collection (Just "whale")
Types like this one cannot be created in most programming languages like Java, TypeScript, or Rust without resorting to dark magic.
Example of a (failed) HKT attempt in C#.
interface ISingleton<out T>
{
T<A> One<A>(A x);
}
class ListSingleton : ISingleton<List>
{
public List<A> One<A>(A x) => new List<A>(new A[]{x});
}
The following code returns three compilation errors, out of which the first – The type parameter 'T' cannot be used with type arguments
– is the compiler explicitly forbidding HKTs.
You can also see a TypeScript example of an unimplementable Collection
in our article about functional TypeScript.
Of course, we cannot really write a lot of functions for this data type because it is too generic. To make it more useful, we can add some constraints, such as the outer type (f
) being a functor.
But what is a functor?
HKTs and functors
In Haskell, HKTs is the realm of typeclasses like Functor
and Monad
. In this article, we’ll cover only Functor
since it’s simpler. But most things written here apply to Monad
as well.
Let’s look at what GHCi can tell us about Functor
.
> :info Functor
type Functor :: (* > *) > Constraint
class Functor f where
fmap :: (a > b) > f a > f b
(<$) :: a > f b > f a
If you’re not familiar with Haskell, this might look a little confusing. Let’s try to untangle it.
Functor in Haskell is a typeclass, which is something that bears resemblance to Rust traits, or if you squint hard, Java interfaces. Typeclasses define a set of common methods that can be shared across types.
The kind signature of Functor
is (* > *) > Constraint
, which means that it takes a type constructor like Maybe
and returns something of a Constraint
kind.
Constraint kind
While *
is the most common kind that you will find in basic Haskell without extensions, it’s not the only one.
While data types are of kinds like *
or * > *
, typeclasses are of a kind like * > Constraint
or (* > *) > Constraint
.
Constraint
is the kind of class constraints – it covers anything that can appear on the left side of the arrow when defining a type.
For example, if we want to define a polymorphic plus function in Haskell, we need to add a constraint of Num
.
 {1}
plus :: Num a => a > a > a
plus a b = a + b
 {1}: Num constraint on the type of a in the signature.
It comes from the Num
typeclass, whose kind is * > Constraint
.
In general, kinds with names are something you will run into much more when starting to work with extensions like DataKinds
.
The main method of Functor
is fmap
, which is a map
that works for multiple types of wrappers. Below are some examples of its usage.
fmap
with []
:
> fmap (+3) [1, 2, 3]
[4,5,6]
fmap
with Maybe
:
> fmap (+3) (Just 1)
Just 4
fmap
with Either
:
> fmap (+3) (Right 5)
Right 8
> fmap (+3) (Left "fatal Err0r")
Left "fatal Err0r"
If you want more information about the typeclass, you can read our article on functors.
In general, since types with the kind of * > *
don’t have any values, you can’t really work with them in most programming languages.
But in Haskell, we can take a type with such a kind and create a Functor
instance for it. For example, our own data type Optional
.
data Optional a = Some a  None deriving (Show)
instance Functor Optional where
fmap f (Some a) = Some (f a)
fmap f None = None
Once we have the instance, we can use the Functor
methods for this data type.
> fmap (+3) (Some 4)
Some 7
Functor instance restrictions
Note that you can only define a Functor
instance for a type of a kind * > *
. So it has to be Optional
, not Optional Int
or Optional String
.
Types with the kind of * > * > *
like Either
or (,)
(the tuple type) cannot have Functor
instances without being applied up to the correct kind. For example, you can have a functor instance for Either a
, but not Either
or Either a b
.
instance Functor (Either a) where
fmap _ (Left x) = Left x
fmap f (Right y) = Right (f y)
And because partial application happens from the left, fmap
maps only the Right
element of Either
.
Now that we are somewhat familiar with Functor
, we can use it as a constraint for the Collection
data type. We’ll define a cfmap
function on collections whose wrappers are functors.
It takes a function and a Collection
that has a functor wrapper, and returns a Collection
with the same functor wrapper but with the function applied to the value inside of it.
cfmap :: Functor f => (a > b) > Collection f a > Collection f b
cfmap fun (Collection a) = Collection (fmap fun a)
Here’s how this method works:
> cfmap (<> "!") (Collection ["call", "me", "ishmael"])
Collection ["call!","me!","ishmael!"]
> cfmap (+3) (Collection [1, 2, 3])
Collection [4,5,6]
Of course, the definition is awfully similar to the fmap
itself. So we could just make Collection
a Functor
instead.
instance Functor f => Functor (Collection f) where
fmap fun (Collection a) = Collection (fmap fun a)
This enables us to use fmap
for collections that have a Functor
wrapper.
> fmap (<> "!") (Collection ["call", "me", "ishmael"])
Collection ["call!","me!","ishmael!"]
Quite cool.
And this concludes our journey into higherkinded types in Haskell. 🏞️
To sum up, here’s a table with the differences between concrete types, simple polymorphic types, and higherkinded types.
  Concrete types  Polymorphic types  Higherkinded types 
 Example kind signature  *
 * > *
 (* > *) > *

 Example data type  Int
 Maybe a
 Collection f a
(Reallife examples from base include alternative and applicative wrappers from Data.Monoid.)

Benefits of higherkinded types
So why would a language need to support higherkinded types?
If you ask a Haskeller, it is, of course, to be able to easily define something similar to the Functor
and Monad
typeclasses.
These typeclasses are very beneficial for those that know how to use them. Abstracting over a bunch of similar behaviors can lead to very elegant code.
And, additionally, if HKTs are available naturally, there’s a smaller chance that someone will create an FP library that’s unreadable for 99% of the language users. 🙃
At the same time, plenty of programming languages choose to skip HKTs. Rust, for example, is somewhat inspired by FP languages like Haskell, but it lacks higherkinded types at the moment. People love it nonetheless.
So, it’s a complex tradeoff at the very least. Thankfully, it is one mostly resolved by language designers and not us mere mortals.
All in all, if you write code in a language that enables you to write HKTs (like Haskell), you should, of course, make use of the power. They are not that complex but help quite a lot.
But if you want to use them in a language where they are not natural to use (for example, via an FP library like fpts), be sure that everyone involved is OK with that beforehand.
Further reading
This article covered a wide variety of topics in a piecemeal fashion. We looked at kinds, higherkinded types, and the Functor
typeclass. While I tried to give all the necessary information, each of these topics deserves an article of its own.
To learn more about kinds in Haskell, I suggest this awesome article by Diogo Castro.
And if you want to read more about Haskell typeclasses like Functor
, we have a series called What’s That Typeclass that covers them.
To read more articles like these, follow us on Twitter or subscribe to the Serokell newsletter via the form below.
Top comments (0)