Encoding HKTs in TS4.1
There have been many attempts at finding valid HKT encodings in TypeScript. Currently, the most reliable one is implemented by fp-ts.
In fp-ts all the types are recorded into a number of type-level maps that index URI -> Concrete Type and this map is different for each kind:
Those type-level records are filled progressively by using the module augmentation feature. Let's look at how Either & Option are wired in those records:
After augmentation the records will look like:
Accessing those types requires getting the proper record key and filling in the params:
Which corresponds to:
Using this method fp-ts defines:
we can now access:
With these constructs it’s possible to write generic interfaces that don't specify the URI.
For example, we can write:
and have:
Clearly, this is not enough to generalise over different kinds. In fp-ts you will find multiple definitions of every typeclass (interface with a generic URI, for this matter) for each of the kind.
As we can see, in addition to the 4 kinds, we also have *C interfaces that are used to add a constraint to the E parameter. This is used in Validation where E represents the Error channel and we ask Monoid<e> to eventually combine errors together.</e>
Let's now look at how to use those typeclasses. How can we write a function that consumes a generic Functor?
Starting from the base case, we want a generic function addOne that works by mapping a number output by adding one:
Calling this function with the appropriate typeclass instance it will yield a specific function for the data-type.
We can generalise further and support different kinds via overloading:
The only trouble is defining the very scary base case (any, any, any).
In fp-ts we can use HKT defined as:
Now we can define a specific Functor interface for HKT like:
and use this to type the base case:
Short and practical, isn't it? Let’s write a composition of functors:
And that’s not even complete...
Another limitation is that every single type needs to be independently indexed. This makes typeclass transformers extremely impractical.
Our goal is to have the same features (or a bit more) with significantly less boilerplate.
Let’s now look at a restricted version of the encoding used in @effect-ts/core. While @effect-ts/core allows for as much as 10 type parameters (2 of which are used to encode generic keys, i.e. nominal keys for records, generic keys for maps, integer keys for arrays, etc), let’s limit ourselves to 4 for simplicity (the same number as in fp-ts).
The full code is available at:
https://github.com/Matechs-Garage/matechs-effect/tree/master/packages/core/src/Prelude/HKT
And the typeclasses (inspired by zio-prelude):
https://github.com/Matechs-Garage/matechs-effect/tree/master/packages/core/src/Prelude
The first idea is to shrink the number of type-level records, instead of having multiple records we are only going to have one:
We can then temporarily define the Kind to be:
This already removes quite a bit of boilerplate. We can then define typeclasses as follows:
and instances:
and Bifunctor
and instances:
Looking better, but how are we going to encode constraints like fixing "E" to a specific value?
The answer is to add a generic C to hold the constraints:
and change our typeclasses to become:
the code of the instances didn't change at all, but we can now create a constrained instance in this way:
We have a couple more unused parameters but we get the signature we wanted.
Unfortunately there is no way to remove those phantom types without multiple registries and much more boilerplate, but in the end, who cares?
In a single definition we can now compact multiple kinds and multiple potential constraints, in fact Fix is safe for intersection so we could have written Fix<"e", string=""> & Fix<"s", number="">.</"s",></"e",>
Our addOne function looks much better:
We could leave it here and already have a decent save but there is a downside; Errors in the generic implementation tend to become unreadable. The reason being, URIS is a very big union and any type error will basically try every possible combination generating unusable error messages.
We can take inspiration from fp-ts in defining one HKT to write the base implementation and leave the rest to overloads, but we don't really want to define separated typeclasses for HKT so we will add HKT into the registry:
and we can now define the base case in terms of "F_":
Any type error in the implementation will now be specific to "F_".
However, there is a problem with this solution of "F_".
If we have a single HKT it's fine but what if we have multiple?
For example in cases like getFunctorComposition:
For that we are going to add multiple "fake" types in the registry taking care of discriminating them using a "_tag" field:
In this way we can safely "name" multiple HKTs making sure that they cannot be mixed, with a bit more work we could also extend the logic of Kind to accept another form of non primitive URIs that allow for embedding of custom parameters and with that discriminate HKTs like functor-composition-in-core.
Good enough? Not even close, we are going to attempt transformers.
What if we want a Functor for Either<e, option<a="">>? How can we do that without reindexing?</e,>
The idea is to make the URI of Kind composable, we can use a variadic tuple to represent a list of URIS and have Kind recursively build up the type:
our typeclasses and instances change accordingly:
But now we can do:
Without any reindex we have created an instance of a composed type. To prove it works we can use our addOne:
Apart from the excessive phantom types the signature is what we wanted (like before).
In addition, @effect-ts/core uses the C parameter to encode parameter variance and defines utility types to mix generic parameters which respect the annotated variance.
For that check the code at https://github.com/Matechs-Garage/matechs-effect!
This article code extracted to: https://gist.github.com/mikearnaldi/
