Higher-Kinded Types
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:
declare const mapArray: <A>(self: Array<A>, f: (a: A) => B) => Array<B>
declare const mapChunk: <A>(self: Chunk<A>, f: (a: A) => B) => Chunk<B>
declare const mapOption: <A>(self: Option<A>, f: (a: A) => B) => 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:
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:
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:
declare const ArrayMappable: Mappable<Array>
declare const ChunkMappable: Mappable<Chunk>
declare const OptionMappable: Mappable<Option>
Additionally, we could create generic functions like stringify
:
const stringify =
<F>(T: Mappable<F>) =>
(self: F<number>): F<string> =>
T.map(self, (n) => `number: ${n}`)
And use them like this:
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 theMappable
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:
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:
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:
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
:
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:
// $ExpectType string[]
type Test1 = Kind<ArrayTypeLambda, string> // Applying ArrayTypeLambda to string
// $ExpectType number[]
type Test2 = Kind<ArrayTypeLambda, number> // Applying ArrayTypeLambda to number
Let's take a step further and define Type Lambdas for other data types, such as Chunk
and Option
:
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"]>
}
// $ExpectType Chunk<string>
type Test3 = Kind<ChunkTypeLambda, string>
// $ExpectType Option<string>
type Test4 = Kind<OptionTypeLambda, string>
Type Classes
We are now ready to define the Mappable
type class, which we introduced earlier:
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.
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:
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:
// $ExpectType string[]
const arrayTest = stringify(MappableArray)([1, 2, 3])
console.log(arrayTest)
// [ 'number: 1', 'number: 2', 'number: 3' ]
// $ExpectType Chunk<string>
const chunkTest = stringify(MappableChunk)(Chunk.fromIterable([1, 2, 3]))
console.log(chunkTest)
// { _id: 'Chunk', values: [ 'number: 1', 'number: 2', 'number: 3' ] }
// $ExpectType Option<string>
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<E, A>
or Effect<R, E, A>
, 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:
-
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. -
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. -
Out1
(Covariant): Similar toOut2
,Out1
is a covariant type parameter, enabling operations that result in a more specific output type. -
Target
(Invariant): TheTarget
type parameter remains invariant, meaning that it maintains the exact type as the original without any variation.
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:
import { TypeLambda } from "./HKT"
import { Either } from "effect"
export interface EitherTypeLambda extends TypeLambda {
readonly type: Either.Either<this["Out1"], this["Target"]>
}
Please note that we are using the Out1
parameter, which is covariant since the E
type parameter of Either<E, A>
is covariant.
And here's how to define the Mappable
type class:
import { TypeLambda, TypeClass, Kind } from "effect/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:
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
:
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
:
- ): 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)
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:
import { TypeLambda } from "./HKT"
import { Either } from "effect"
import { Zippable } from "./Zippable"
export interface EitherTypeLambda extends TypeLambda {
readonly type: Either.Either<this["Out1"], this["Target"]>
}
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:
Either<E1 | E2, readonly [A, B]>
This signifies that the system has correctly managed the covariance of the E
type parameter by returning the union of possible errors: E1 | E2
.