Encoding HKTs in TypeScript (Once Again)
A lot has happened in Effect this year, many new contributors and many new ecosystem projects!
â
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.
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:
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:
with that we could say:
in fact we could also define:
and we could even implement generic functions like:
and use it like:
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:
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:
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:
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:
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:
and then we can say:
and expect that X is number[].
Now we can define our Mappable from before:
and we can define:
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:
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.
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:
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.
â
