Kinds and Higher-Kinded Types in Haskell
Tags: haskell
Published: 2022-08-03 11:04:32

---
title: Kinds and Higher-Kinded Types in Haskell
published: true
date: 2022-08-02 00:00:00 UTC
tags: haskell
canonical_url: https://serokell.io/blog/kinds-and-hkts-in-haskell
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rh4afgobvrpb0nd6nvrg.png
---

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](https://serokell.io/blog/typescript-for-haskellers#hkts).

* * *

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](https://serokell.io/blog/haskell-typeclasses), 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](https://serokell.io/blog/whats-that-typeclass-functor).

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 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](https://hackage.haskell.org/package/base-4.16.1.0/docs/Data-Monoid.html#g:5) and [applicative](https://hackage.haskell.org/package/base-4.16.1.0/docs/Data-Monoid.html#g:6) wrappers from [Data.Monoid](https://hackage.haskell.org/package/base-4.16.1.0/docs/Data-Monoid.html).)

 |

## 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](https://serokell.io/blog/rust-guide), 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](https://github.com/gcanti/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](https://diogocastro.com/blog/2018/10/17/haskells-kind-system-a-primer/) by Diogo Castro.

And if you want to read more about Haskell typeclasses like `Functor`, we have a series called [What’s That Typeclass](https://serokell.io/blog/what's-that-typeclass) that covers them.

To read more articles like these, follow us on [Twitter](https://twitter.com/serokell) or subscribe to the Serokell newsletter via the form below.