Encoding HKTs in TypeScript (Once Again)

It was about a year ago when I was writing enthusiastically about a new way of encoding Higher Kinded Types (HKTs) in TypeScript in such a way that we could support transformers and reduce the need for verbose declarations.

The article mentioned can be found at: https://www.matechs.com/blog/encoding-hkts-in-ts4-1

A lot has happened in Effect this year, many new contributors and many new ecosystem projects and I couldn't be more excited, looking forward into the future I see a lot of good happening in this space!

Behind all the good there is a lot of effort, and sometimes to reach something that looks simple you have to iterate into multiple stages tackling complexity bit by bit.

This is the story of how we collectively missed something simple, for many years.

If you want to read the history read the article mentioned above, I will start here from zero.

Why do we need HKTs?

We want to implement common functionality across modules, let's for example take the following functions:

declare const mapArray: 
  <A>(self: Array<A>, f: (a: A) => B) => Array<B>

declare const mapTree: 
  <A>(self: Tree<A>, f: (a: A) => B) => Tree<B>

declare const mapOption: 
  <A>(self: Option<A>, f: (a: A) => B) => Option<B>

We can notice how much of the above signatures is in common, in fact they have everything equal except for the type they target Array|Tree|Option.

We would like to define an interface to describe this behaviour, unfortunately it isn't that obvious how.

Let's dream for a second and write:

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

with that we could say:

declare const mapArray: Mappable<Array>["map"]
declare const mapTree: Mappable<Tree>["map"]
declare const mapOption: Mappable<Option>["map"]

in fact we could also define:

declare const ArrayMappable: Mappable<Array>
declare const TreeMappable: Mappable<Tree>
declare const OptionMappable: Mappable<Option>

and we could even implement generic functions like:

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

and use it like:

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

To introduce some terminology F<~> is called a Higher Kinded Type and interface Mappable<F<~>> is called a TypeClass.

So far we only seen data types with a single parameter like Option<~> or Array<~>, there are also data types with multiple parameters like Either<~, ~> or Effect<~, ~, ~> and we would also like to include those in the same setup, ideally we could do so by defining:

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

but we now have the problem of defining who's who, for example is A in Either the first or the second parameter? we could have some conventions where E is always the second and R is always the first and A always the last but that isn't too flexible too.

In fact there is no general solution to this, a lot of ideas exists though, for example in Scala you would be able to define type lambdas (sort of mappers between type parameters).

Let's now stop dreaming and realise that F<~> isn't even valid TypeScript, hopefully we got the idea of what we would like to have.

Let me tell you about

Lately I've been hearing more and more that a good design is a design that minimize the needs to tell you about unrelated things, in the previous encodings this list would be huge but I am now happy to say that I only have to tell you about a single "trick" (confirmed as reliable expected behaviour).

The this type unification logic, given:

interface MyInterface {
  readonly x?: unknown
}

type X = (MyInterface & { readonly x: number })["x"]

you would rightfully expect the type X to be number given that unknown & number = number.

Inside an interface you can also reference the this type so you can also expect:

interface MyInterface {
  readonly x?: unknown
  readonly y: this["x"]
}

type Y = (MyInterface & { readonly x: number })["y"]

that can be surprising, one would think that y would be always unknown but instead the this parameter is special because it always represent the current type even in an extension chain X extends Y extends Z, something defined as this in Z will appear as X. That's fairly logical if you think about it for the usage in classes and interfaces for plain OOP inheritance.

Single Parameter Encoding

Let's define something along the lines of the above, namely:

interface HKT {
  // will reference the A type
  readonly _A?: unknown

  // will represent the computed type
  readonly type?: unknown
}

now we'll need a way to reference a generic type using something like Kind<F, A> as a meaning for F<A>, doing that is a little tricky:

type Kind<F extends HKT, A> = 
  F extends {
    readonly type: unknown
  } ?
  // F has a type specified, it is concrete (like F = ArrayHKT)
  (F & {
    readonly _A: A
  })["type"] :
  // F is generic, we need to mention all of the type parameters
  // to guarantee that they are never excluded from type checking
  {
    readonly _F: F
    readonly _A: () => A
  }

and then we can say:

interface ArrayHKT extends HKT {
  readonly type: Array<this["_A"]>
}

type X = Kind<ArrayHKT, number>

and expect that X is number[].

Now we can define our Mappable from before:

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

and we can define:

const MappableArray: Mappable<ArrayHKT>

we can check the signature of MappableArray["map"] and it will appear as <A, B>(self: A[], f: (a: A) => B) => B[].

With the above we can also write:

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

and the job is done.

Multi Parameter Encoding

The only thing to really know here is that the base case of Kind has to mention all of the type parameters with their respective variance, so for example let's say we want to support up to 3 params one input and two outputs called R, E and A.

interface HKT {
  readonly _R?: unknown
  readonly _E?: unknown
  readonly _A?: unknown

  readonly type?: unknown
}

type Kind<F extends HKT, R, E, A> = 
  F extends {
    readonly type: unknown
  } ?
  (F & {
    readonly _R: R
    readonly _E: E
    readonly _A: A
  })["type"] :
  {
    readonly _F: F
    readonly _R: (_: R) => void
    readonly _E: () => E
    readonly _A: () => A
  }

interface Mappable<F extends HKT> {
  readonly map: 
    <R, E, A, B>(
      self: Kind<F, R, E, A>,
      f: (a: A) => B
    ) => Kind<F, R, E, B>
}

interface ArrayHKT extends HKT {
  readonly type: Array<this["_A"]>
}

const stringify = 
  <F extends HKT>(T: Mappable<F>) => 
  <R, E>(self: Kind<F, R, E, number>) => 
  T.map(self, (n) => `number: ${n}`)

declare const ArrayMappable: Mappable<ArrayHKT>

const res = stringify(ArrayMappable)([0, 1, 2])

Inference with TypeClasses

We fully encoded Higher Kinded Types and we were able to define a TypeClass like Mappable, 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 parameter like:

interface TypeClass<F extends HKT> {
  readonly _F?: F
}

interface Mappable<F extends HKT> extends TypeClass<F> {
  readonly map: 
    <R, E, A, B>(
      self: Kind<F, R, E, A>,
      f: (a: A) => B
    ) => Kind<F, R, E, B>
}

The End

You can find the full prototype of this encoding at https://github.com/mikearnaldi/hkt-new including the usage with transformers (such as ValidationT, ReaderT, etc).

At the moment of writing this post Effect still uses the old encoding and progress to move to this one is tracked in https://github.com/Effect-TS/core/issues/1005.

Comments

[Barisere Jonathan]

There seems to be one limitation to this approach. It cannot capture the this type as an HKT.
Suppose class A is a parent of class B, and A provides common methods for its children. We can return the this type from the methods of A to enable us chain the methods with those in its sub classes. But if A has a type parameter, say A<'a>, we cannot pass that parameter to the this type as A<'b>.
Using the registry approach to HKTs, I was able to do that. It's useful for modelling OOP libraries like joi.

I still like this approach, it's simpler.

Edit

It's actually possible to pass a new type argument to a sub class from its super class. It requires defining a separate HKT for each class, then passing the HKT of the sub class to its super class.

[Michael Arnaldi]

Not sure I understand would you mind making a simple example?

[Frederik Krautwald]

All interesting stuff, but what’s wrong with fp-ts?

[Michael Arnaldi]

Doesn't support transformers, every definition of a typeclass requires multiple interfaces defined (4*2, where 4 is the amount of supported parameters and 2 is the number of supported constraints, only the E can be fixed) and any definition of a function that operated on a typeclass requires the same amount of overloads.

The following is the definition of Functor in fp-ts:
github.com/gcanti/fp-ts/blob/maste...

And of a function that operated on a typeclass:
github.com/gcanti/fp-ts/blob/maste...

The following two examples of this encoding:

github.com/mikearnaldi/hkt-new/blo...
github.com/mikearnaldi/hkt-new/blo...