Encoding HKTs in TypeScript (Once Again)

A lot has happened in Effect this year, many new contributors and many new ecosystem projects!

Encoding HKTs in TypeScript (Once Again)

ℹī¸Ž For a better experience of this article, please visit: https://dev.to/matechs/encoding-of-hkts-in-typescript-5c3.


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.

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 to 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.

a man saying "one does not simply encode HKT in typescript"

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:

coding screenshot

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:

coding screenshot

with that we could say:

coding screenshot

in fact we could also define:

coding screenshot

and we could even implement generic functions like:

coding screenshot

and use it like:

coding screenshot

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:

coding screenshot

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:

coding screenshot

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:

coding screenshot

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:

coding screenshot

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:

coding screenshot

and then we can say:

coding screenshot

and expect that X is number[].

Now we can define our Mappable from before:

coding screenshot

and we can define:

coding screenshot

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:

coding screenshot

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.

coding screenshot

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:

coding screenshot

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.


Effect Core Series

1. Encoding HKTs in TS4.1

2. Effect-TS Core: ZIO-Prelude Inspired Typeclasses & Module Structure

3. The Effect Data Types: Effect

4. The Effect Data Types: Managed & Layer

5. Abusing TypeScript Generators

6. Encoding HKTs in TypeScript (Once Again)

Stay updated on news & learning resources on web design, development and web accessibility!

Be social