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.

Encoding HKTs in TS4.1

Matechs 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

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:

coding screenshot

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:

coding screenshot
coding screenshot

After augmentation the records will look like:

coding screenshot

Accessing those types requires getting the proper record key and filling in the params:

coding screenshot

Which corresponds to:

coding screenshot

Using this method fp-ts defines:

coding screenshot

we can now access:

coding screenshot

With these constructs it’s possible to write generic interfaces that don't specify the URI.

For example, we can write:

coding screenshot

and have:

coding screenshot

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.

coding screenshot

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:

coding screenshot

Calling this function with the appropriate typeclass instance it will yield a specific function for the data-type.

coding screenshot

We can generalise further and support different kinds via overloading:

coding screenshot

The only trouble is defining the very scary base case (any, any, any).

In fp-ts we can use HKT defined as:

coding screenshot

Now we can define a specific Functor interface for HKT like:

coding screenshot

and use this to type the base case:

coding screenshot


Short and practical, isn't it? Let’s write a composition of functors:

coding screenshot

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:

coding screenshot

We can then temporarily define the Kind to be:

coding screenshot

This already removes quite a bit of boilerplate. We can then define typeclasses as follows:

coding screenshot

and instances:

coding screenshot

and Bifunctor

coding screenshot

and instances:

coding screenshot

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:

coding screenshot

and change our typeclasses to become:

coding screenshot

the code of the instances didn't change at all, but we can now create a constrained instance in this way:

coding screenshot

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:

coding screenshot

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:

coding screenshot

and we can now define the base case in terms of "F_":

coding screenshot

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:

coding screenshot

For that we are going to add multiple "fake" types in the registry taking care of discriminating them using a "_tag" field:

coding screenshot

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:

coding screenshot

our typeclasses and instances change accordingly:

coding screenshot

But now we can do:

coding screenshot

Without any reindex we have created an instance of a composed type. To prove it works we can use our addOne:

coding screenshot

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/

Effect Core

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

Stay updated on our current and upcoming training workshops!

Be social
Be social