Higher-Kinded Types

On this page

Higher-Kinded Types (HKTs) might sound complex, but they are a valuable concept in programming that can simplify code and make it more flexible. In this article, we'll explore what HKTs are and why they are useful for developers, especially those who are just starting out.

What Are Higher-Kinded Types?

At its core, a higher-kinded type is a type that abstracts over another type, which, in turn, abstracts over yet another type. In simpler terms, it allows us to create generic structures that can work with a wide range of data types. Think of it as a way to build reusable code that can adapt to different data structures.

The Need for HKTs

To understand why HKTs are useful, let's consider a practical scenario. We often want to implement similar functionality across different data structures, like arrays, chunks, and options. Here are some functions as examples:

ts
import { Chunk, Option } from "effect"
 
declare const mapArray: <A, B>(self: Array<A>, f: (a: A) => B) => Array<B>
 
declare const mapChunk: <A, B>(
  self: Chunk.Chunk<A>,
  f: (a: A) => B
) => Chunk.Chunk<B>
 
declare const mapOption: <A, B>(
  self: Option.Option<A>,
  f: (a: A) => B
) => Option.Option<B>
ts
import { Chunk, Option } from "effect"
 
declare const mapArray: <A, B>(self: Array<A>, f: (a: A) => B) => Array<B>
 
declare const mapChunk: <A, B>(
  self: Chunk.Chunk<A>,
  f: (a: A) => B
) => Chunk.Chunk<B>
 
declare const mapOption: <A, B>(
  self: Option.Option<A>,
  f: (a: A) => B
) => Option.Option<B>

Notice that these functions share a lot of similarities; in fact, they are almost identical except for the data type they operate on (Array, Chunk, Option).

Now, imagine if we could define a common interface to describe this behavior. This would make our code more organized and easier to maintain. However, doing this in a straightforward way is not so obvious.

The Ideal Solution

In an ideal world, we could create an interface like this:

ts
interface Mappable<F<~>> {
  readonly map: <A, B>(self: F<A>, f: (a: A) => B) => F<B>
}
ts
interface Mappable<F<~>> {
  readonly map: <A, B>(self: F<A>, f: (a: A) => B) => F<B>
}

With this interface in place, we could do the following:

ts
declare const mapArray: Mappable<Array>["map"]
declare const mapChunk: Mappable<Chunk>["map"]
declare const mapOption: Mappable<Option>["map"]
ts
declare const mapArray: Mappable<Array>["map"]
declare const mapChunk: Mappable<Chunk>["map"]
declare const mapOption: Mappable<Option>["map"]

We could also define instances of this interface for different data types:

ts
declare const ArrayMappable: Mappable<Array>
declare const ChunkMappable: Mappable<Chunk>
declare const OptionMappable: Mappable<Option>
ts
declare const ArrayMappable: Mappable<Array>
declare const ChunkMappable: Mappable<Chunk>
declare const OptionMappable: Mappable<Option>

Additionally, we could create generic functions like stringify:

ts
const stringify =
  <F>(T: Mappable<F>) =>
  (self: F<number>): F<string> =>
    T.map(self, (n) => `number: ${n}`)
ts
const stringify =
  <F>(T: Mappable<F>) =>
  (self: F<number>): F<string> =>
    T.map(self, (n) => `number: ${n}`)

And use them like this:

ts
const stringifiedArray: Array<string> = stringify(ArrayMappable)([0, 1, 2])
ts
const stringifiedArray: Array<string> = stringify(ArrayMappable)([0, 1, 2])

A Brief Terminology

Before we move on, let's clarify some terms:

  • F<~> is known as a "higher-kinded type".
  • The interface Mappable<F<~>> is referred to as a "type class".
  • Values like ArrayMappable are "instances" of the Mappable type class.

Now, let's pause our dream scenario and acknowledge that F<~> is not valid TypeScript. However, we've grasped the concept of what we'd like to achieve.

In the following sections, we will delve into how HKTs are emulated in Effect. This process involves gradually constructing the essential components needed to work with higher-kinded types effectively.

Type Lambdas

To work effectively with Higher-Kinded Types (HKTs), we need to first grasp the concept of "Type Lambdas." Type Lambdas are a way to define type-level functions in TypeScript, which are not natively supported by the language.

A Type Lambda, like Target -> F<Target>, essentially defines a function that operates on types and returns other types. Let's break down this concept:

ts
Target -> Array<Target>
ts
Target -> Array<Target>

In this example, the Type Lambda maps the input type Target to the output type Array<Target>. It's like defining a rule that transforms one type into another.

Type Lambdas allow us to express Higher-Kinded Types directly without the need for complex type definitions.

Implementing a Type Lambda

To implement a Type Lambda, we'll start by defining an interface that includes a Target field. Here's how it's done:

ts
export interface TypeLambda {
  readonly Target: unknown
}
ts
export interface TypeLambda {
  readonly Target: unknown
}

This simple interface sets the foundation for our Type Lambdas.

Creating a Type Lambda

Let's create a specific Type Lambda for the Array data type:

ts
export interface ArrayTypeLambda extends TypeLambda {
  readonly type: Array<this["Target"]>
}
ts
export interface ArrayTypeLambda extends TypeLambda {
  readonly type: Array<this["Target"]>
}

Here, we extend the base TypeLambda interface to define an ArrayTypeLambda. This specific Type Lambda is tailored for working with arrays.

Applying the Type Lambda

Now that we have our Type Lambda and its specialized version for arrays, we need a way to apply this type-level function to a concrete type A. We'll call this operator Kind:

ts
export type Kind<F extends TypeLambda, Target> = F extends {
  readonly type: unknown
}
  ? // If F has a type property, it means it is a concrete type lambda (e.g., F = ArrayTypeLambda).
    // The intersection allows us to obtain the result of applying F to Target.
    (F & {
      readonly Target: Target
    })["type"]
  : // If F is generic, we must explicitly specify all of its type parameters
    // to ensure that none are omitted from type checking.
    {
      readonly F: F
      readonly Target: (_: Target) => Target // This enforces invariance.
    }
ts
export type Kind<F extends TypeLambda, Target> = F extends {
  readonly type: unknown
}
  ? // If F has a type property, it means it is a concrete type lambda (e.g., F = ArrayTypeLambda).
    // The intersection allows us to obtain the result of applying F to Target.
    (F & {
      readonly Target: Target
    })["type"]
  : // If F is generic, we must explicitly specify all of its type parameters
    // to ensure that none are omitted from type checking.
    {
      readonly F: F
      readonly Target: (_: Target) => Target // This enforces invariance.
    }

The Kind operator takes a Type Lambda F and a Target type. It ensures that F is a valid type lambda and then applies it to the Target. This allows us to obtain a type that represents the result of the Type Lambda operation.

Let's test our operator with some examples:

ts
// Applying ArrayTypeLambda to string
type Test1 = Kind<ArrayTypeLambda, string>
 
// Applying ArrayTypeLambda to number
type Test2 = Kind<ArrayTypeLambda, number>
ts
// Applying ArrayTypeLambda to string
type Test1 = Kind<ArrayTypeLambda, string>
 
// Applying ArrayTypeLambda to number
type Test2 = Kind<ArrayTypeLambda, number>

Let's take a step further and define Type Lambdas for other data types, such as Chunk and Option:

ts
import { Chunk, Option } from "effect"
 
export interface ChunkTypeLambda extends TypeLambda {
  readonly type: Chunk.Chunk<this["Target"]>
}
 
export interface OptionTypeLambda extends TypeLambda {
  readonly type: Option.Option<this["Target"]>
}
 
type Test3 = Kind<ChunkTypeLambda, string>
 
type Test4 = Kind<OptionTypeLambda, string>
ts
import { Chunk, Option } from "effect"
 
export interface ChunkTypeLambda extends TypeLambda {
  readonly type: Chunk.Chunk<this["Target"]>
}
 
export interface OptionTypeLambda extends TypeLambda {
  readonly type: Option.Option<this["Target"]>
}
 
type Test3 = Kind<ChunkTypeLambda, string>
 
type Test4 = Kind<OptionTypeLambda, string>

Type Classes

We are now ready to define the Mappable type class, which we introduced earlier:

ts
export interface Mappable<F extends TypeLambda> {
  readonly map: <A, B>(self: Kind<F, A>, f: (a: A) => B) => Kind<F, B>
}
ts
export interface Mappable<F extends TypeLambda> {
  readonly map: <A, B>(self: Kind<F, A>, f: (a: A) => B) => Kind<F, B>
}

In the code above, we define a Mappable type class. This type class provides a blueprint for creating functions that can map values from one type to another. It's a powerful tool for writing code that's both generic and flexible.

Instances

To put our Mappable type class to use, we need to create instances for specific data types. These instances will allow us to perform mapping operations on those data types.

ts
import { Chunk, Option } from "effect"
 
export const MappableArray: Mappable<ArrayTypeLambda> = {
  map: (self, f) => self.map(f)
}
 
export const MappableChunk: Mappable<ChunkTypeLambda> = {
  map: Chunk.map
}
 
export const MappableOption: Mappable<OptionTypeLambda> = {
  map: Option.map
}
ts
import { Chunk, Option } from "effect"
 
export const MappableArray: Mappable<ArrayTypeLambda> = {
  map: (self, f) => self.map(f)
}
 
export const MappableChunk: Mappable<ChunkTypeLambda> = {
  map: Chunk.map
}
 
export const MappableOption: Mappable<OptionTypeLambda> = {
  map: Option.map
}

Here, we've created instances for Array, Chunk, and Option types. Each instance is equipped with a map function tailored to its respective data type.

Now, we can proceed to create our stringify function:

ts
export const stringify =
  <F extends TypeLambda>(TC: Mappable<F>) =>
  (self: Kind<F, number>): Kind<F, string> =>
    TC.map(self, (n) => `number: ${n}`)
ts
export const stringify =
  <F extends TypeLambda>(TC: Mappable<F>) =>
  (self: Kind<F, number>): Kind<F, string> =>
    TC.map(self, (n) => `number: ${n}`)

To ensure that everything works as expected, let's run some tests:

ts
const arrayTest = stringify(MappableArray)([1, 2, 3])
console.log(arrayTest)
// [ 'number: 1', 'number: 2', 'number: 3' ]
 
const chunkTest = stringify(MappableChunk)(Chunk.fromIterable([1, 2, 3]))
console.log(chunkTest)
// { _id: 'Chunk', values: [ 'number: 1', 'number: 2', 'number: 3' ] }
 
const optionTest = stringify(MappableOption)(Option.some(1))
console.log(optionTest)
// { _id: 'Option', _tag: 'Some', value: 'number: 1' }
ts
const arrayTest = stringify(MappableArray)([1, 2, 3])
console.log(arrayTest)
// [ 'number: 1', 'number: 2', 'number: 3' ]
 
const chunkTest = stringify(MappableChunk)(Chunk.fromIterable([1, 2, 3]))
console.log(chunkTest)
// { _id: 'Chunk', values: [ 'number: 1', 'number: 2', 'number: 3' ] }
 
const optionTest = stringify(MappableOption)(Option.some(1))
console.log(optionTest)
// { _id: 'Option', _tag: 'Some', value: 'number: 1' }

These tests demonstrate how our Mappable type class, stringify function, and type instances work together to consistently map values across different data types.

Enhancements

In our current implementation, we've created a simplified version of what Effect provides. However, there is an important enhancement that we need to address. Specifically, we must accommodate more than one parameter, not just Target. For instance, certain data types, like Either<A, E> or Effect<A, E, R>, require two or more type parameters to function correctly.

In Effect, we have the capability to work with data types that can have up to four type parameters, each with distinct variance characteristics. These parameters are essential for defining the behavior and constraints of various data types within Effect. Let's take a closer look at these type parameters:

  1. In (Contravariant): This type parameter is used for contravariant operations, which means that it accepts input types that are more general or broader than the original type.

  2. Out2 (Covariant): Out2 represents a covariant type parameter. It allows for operations where the output type is more specific or narrower than the original type.

  3. Out1 (Covariant): Similar to Out2, Out1 is a covariant type parameter, enabling operations that result in a more specific output type.

  4. Target (Invariant): The Target type parameter remains invariant, meaning that it maintains the exact type as the original without any variation.

ts
export interface TypeLambda {
  readonly In: unknown
  readonly Out2: unknown
  readonly Out1: unknown
  readonly Target: unknown
}
 
export type Kind<F extends TypeLambda, In, Out2, Out1, Target> = F extends {
  readonly type: unknown
}
  ? (F & {
      readonly In: In
      readonly Out2: Out2
      readonly Out1: Out1
      readonly Target: Target
    })["type"]
  : {
      readonly F: F
      readonly In: (_: In) => void // Contravariant
      readonly Out2: () => Out2 // Covariant
      readonly Out1: () => Out1 // Covariant
      readonly Target: (_: Target) => Target // Invariant
    }
 
export declare const URI: unique symbol
 
export interface TypeClass<F extends TypeLambda> {
  // To improve inference it is necessary to mention the F parameter inside it
  // otherwise it will be lost, we can do so by adding an optional property
  readonly [URI]?: F
}
ts
export interface TypeLambda {
  readonly In: unknown
  readonly Out2: unknown
  readonly Out1: unknown
  readonly Target: unknown
}
 
export type Kind<F extends TypeLambda, In, Out2, Out1, Target> = F extends {
  readonly type: unknown
}
  ? (F & {
      readonly In: In
      readonly Out2: Out2
      readonly Out1: Out1
      readonly Target: Target
    })["type"]
  : {
      readonly F: F
      readonly In: (_: In) => void // Contravariant
      readonly Out2: () => Out2 // Covariant
      readonly Out1: () => Out1 // Covariant
      readonly Target: (_: Target) => Target // Invariant
    }
 
export declare const URI: unique symbol
 
export interface TypeClass<F extends TypeLambda> {
  // To improve inference it is necessary to mention the F parameter inside it
  // otherwise it will be lost, we can do so by adding an optional property
  readonly [URI]?: F
}

Here's how to define a Type Lambda for the Either type:

ts
import { TypeLambda } from "./HKT"
import { Either } from "effect"
 
export interface EitherTypeLambda extends TypeLambda {
  readonly type: Either.Either<this["Target"], this["Out1"]>
}
ts
import { TypeLambda } from "./HKT"
import { Either } from "effect"
 
export interface EitherTypeLambda extends TypeLambda {
  readonly type: Either.Either<this["Target"], this["Out1"]>
}

Please note that we are using the Out1 parameter, which is covariant since the E type parameter of Either<A, E> is covariant.

And here's how to define the Mappable type class:

ts
import { TypeLambda, TypeClass, Kind } from "./HKT"
 
export interface Mappable<F extends TypeLambda> extends TypeClass<F> {
  readonly map: <R, O, E, A, B>(
    self: Kind<F, R, O, E, A>,
    f: (a: A) => B
  ) => Kind<F, R, O, E, B>
}
ts
import { TypeLambda, TypeClass, Kind } from "./HKT"
 
export interface Mappable<F extends TypeLambda> extends TypeClass<F> {
  readonly map: <R, O, E, A, B>(
    self: Kind<F, R, O, E, A>,
    f: (a: A) => B
  ) => Kind<F, R, O, E, B>
}

Variance

You might be wondering about the purpose of the second branch of the conditional type in the Kind type.

This second branch serves to enforce something called "variance." To understand this concept, let's explore an example. Imagine we define a type class like this:

ts
import { Kind, TypeClass, TypeLambda } from "./HKT"
 
export interface Zippable<F extends TypeLambda> extends TypeClass<F> {
  readonly zip: <R1, O1, E1, A, R2, O2, E2, B>(
    first: Kind<F, R1, O1, E1, A>,
    second: Kind<F, R2, O2, E2, B>
  ) => Kind<F, R1 & R2, O1 | O2, E1 | E2, readonly [A, B]>
}
ts
import { Kind, TypeClass, TypeLambda } from "./HKT"
 
export interface Zippable<F extends TypeLambda> extends TypeClass<F> {
  readonly zip: <R1, O1, E1, A, R2, O2, E2, B>(
    first: Kind<F, R1, O1, E1, A>,
    second: Kind<F, R2, O2, E2, B>
  ) => Kind<F, R1 & R2, O1 | O2, E1 | E2, readonly [A, B]>
}

Now, we derive a pipe-able version of zip:

ts
export const zip =
  <F extends TypeLambda>(Zippable: Zippable<F>) =>
  <R2, O2, E2, B>(that: Kind<F, R2, O2, E2, B>) =>
  <R1, O1, E1, A>(
    self: Kind<F, R1, O1, E1, A>
  ): Kind<F, R1 & R2, O1 | O2, E1 | E2, readonly [A, B]> =>
    Zippable.zip(self, that)
ts
export const zip =
  <F extends TypeLambda>(Zippable: Zippable<F>) =>
  <R2, O2, E2, B>(that: Kind<F, R2, O2, E2, B>) =>
  <R1, O1, E1, A>(
    self: Kind<F, R1, O1, E1, A>
  ): Kind<F, R1 & R2, O1 | O2, E1 | E2, readonly [A, B]> =>
    Zippable.zip(self, that)

However, let's assume that we make a mistake while typing the return type of zip by specifying R1 instead of R1 & R2:

diff
-  ): Kind<F, R1 & R2, O1 | O2, E1 | E2, readonly [A, B]> =>
+  ): Kind<F, R1, O1 | O2, E1 | E2, readonly [A, B]> =>
diff
-  ): Kind<F, R1 & R2, O1 | O2, E1 | E2, readonly [A, B]> =>
+  ): Kind<F, R1, O1 | O2, E1 | E2, readonly [A, B]> =>

In this case, it will not type check, and you'll encounter the following error:

...
Types of property 'In' are incompatible.
  Type '(_: R1 & R2) => void' is not assignable to type '(_: R1) => void'.
    Types of parameters '_' and '_' are incompatible.
      Type 'R1' is not assignable to type 'R1 & R2'.ts(2322)
...
Types of property 'In' are incompatible.
  Type '(_: R1 & R2) => void' is not assignable to type '(_: R1) => void'.
    Types of parameters '_' and '_' are incompatible.
      Type 'R1' is not assignable to type 'R1 & R2'.ts(2322)

The second branch of the conditional type helps catch such type errors and ensures that the type parameters are correctly aligned, enforcing proper type checking.

Now, let's proceed to define an instance of Zippable for the Either type:

ts
import { TypeLambda } from "./HKT"
import { Either } from "effect"
import { Zippable } from "./Zippable"
 
export interface EitherTypeLambda extends TypeLambda {
  readonly type: Either.Either<this["Target"], this["Out1"]>
}
 
export const EitherZippable: Zippable<EitherTypeLambda> = {
  zip: (first, second) => {
    if (Either.isLeft(first)) {
      return Either.left(first.left)
    }
    if (Either.isLeft(second)) {
      return Either.left(second.left)
    }
    return Either.right([first.right, second.right])
  }
}
ts
import { TypeLambda } from "./HKT"
import { Either } from "effect"
import { Zippable } from "./Zippable"
 
export interface EitherTypeLambda extends TypeLambda {
  readonly type: Either.Either<this["Target"], this["Out1"]>
}
 
export const EitherZippable: Zippable<EitherTypeLambda> = {
  zip: (first, second) => {
    if (Either.isLeft(first)) {
      return Either.left(first.left)
    }
    if (Either.isLeft(second)) {
      return Either.left(second.left)
    }
    return Either.right([first.right, second.right])
  }
}

If you hover over EitherZippable.zip you will notice that the return type is as follows:

ts
Either<readonly [A, B], E1 | E2>
ts
Either<readonly [A, B], E1 | E2>

This signifies that the system has correctly managed the covariance of the E type parameter by returning the union of possible errors: E1 | E2.