One of the more frequent comments that Haskell developers make about other programming languages is that they lack something called higher-kinded 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 non-Haskell 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 higher-kinded types.
In this article, I will introduce you to the concept of kinds. Then, we’ll use our newfound knowledge to understand what are higher-kinded 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 type-level 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 higher-order functions on types?
In other words, can we have a kind like (* -> *) -> * -> *?
Turns out, yes. In Haskell, it’s kinda easy.
What are higher-kinded types in Haskell?
One of the things that separates Haskell from most programming languages is the existence of higher-kinded types.
Higher-kinded 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 Eitheror (,)(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 fmapfor collections that have a Functor wrapper.
> fmap (<> "!") (Collection ["call", "me", "ishmael"])
Collection ["call!","me!","ishmael!"]
Quite cool.
And this concludes our journey into higher-kinded types in Haskell. 🏞️
To sum up, here’s a table with the differences between concrete types, simple polymorphic types, and higher-kinded types.
| | Concrete types | Polymorphic types | Higher-kinded types |
| Example kind signature | * | * -> * | (* -> *) -> * |
| Example data type | Int | Maybe a | Collection f a
(Real-life examples from base include alternative and applicative wrappers from Data.Monoid.)
|
Benefits of higher-kinded types
So why would a language need to support higher-kinded 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 higher-kinded 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 fp-ts), 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, higher-kinded 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)