Name: Encoding HKTs in TS4.1
Rating: 1.3 (3065 reviews)
Author: mikearnaldi

There have been many attempts at finding valid HKT encodings in TypeScript. Currently the most used and 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:

export interface URItoKind<A> {}

export interface URItoKind2<E, A> {}

export interface URItoKind3<R, E, A> {}

export interface URItoKind4<S, R, E, A> {}

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:

export const URI = "Either"

export type URI = typeof URI

declare module "./HKT" {
  interface URItoKind2<E, A> {
    readonly [URI]: Either<E, A>
  }
}

export const URI = "Option"

export type URI = typeof URI

declare module "./HKT" {
  interface URItoKind<A> {
    readonly [URI]: Option<A>
  }
}

After augmentation the records will look like:

export interface URItoKind<A> {
    Option: Option<A>
    ...
}

export interface URItoKind2<E, A> {
    Either: Either<E, A>
    ...
}

export interface URItoKind3<R, E, A> {
    ReaderTaskEither: ReaderTaskEither<R, E, A>
    ...
}

export interface URItoKind4<S, R, E, A> {
    StateReaderTaskEither: StateReaderTaskEither<S, R, E, A>
    ...
}

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

type Result = URItoKind<string, number>["Either"]

Which corresponds to:

Either<string, number>

Using this method fp-ts defines:

export type URIS = keyof URItoKind<any>
export type URIS2 = keyof URItoKind2<any, any>
export type URIS3 = keyof URItoKind3<any, any, any>
export type URIS4 = keyof URItoKind4<any, any, any, any>

export type Kind<URI extends URIS, A> = URI extends URIS ? URItoKind<A>[URI] : any
export type Kind2<URI extends URIS2, E, A> = URI extends URIS2
  ? URItoKind2<E, A>[URI]
  : any
export type Kind3<URI extends URIS3, R, E, A> = URI extends URIS3
  ? URItoKind3<R, E, A>[URI]
  : any
export type Kind4<URI extends URIS4, S, R, E, A> = URI extends URIS4
  ? URItoKind4<S, R, E, A>[URI]
  : any

we can now access:

type Result = Kind2<"Either", string, number>

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

For example, we can write:

export interface Functor1<F extends URIS> {
  readonly URI: F
  readonly map: <A, B>(fa: Kind<F, A>, f: (a: A) => B) => Kind<F, B>
}

and have:

const functorOption: Functor1<"Option"> = {
    URI: "Option",
    map: ... // map is now correctly typed to work with Option<*>
}

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.

export interface Functor1<F extends URIS> {
  readonly URI: F
  readonly map: <A, B>(fa: Kind<F, A>, f: (a: A) => B) => Kind<F, B>
}

export interface Functor2<F extends URIS2> {
  readonly URI: F
  readonly map: <E, A, B>(fa: Kind2<F, E, A>, f: (a: A) => B) => Kind2<F, E, B>
}

export interface Functor2C<F extends URIS2, E> {
  readonly URI: F
  readonly _E: E
  readonly map: <A, B>(fa: Kind2<F, E, A>, f: (a: A) => B) => Kind2<F, E, B>
}

export interface Functor3<F extends URIS3> {
  readonly URI: F
  readonly map: <R, E, A, B>(fa: Kind3<F, R, E, A>, f: (a: A) => B) => Kind3<F, R, E, B>
}

export interface Functor3C<F extends URIS3, E> {
  readonly URI: F
  readonly _E: E
  readonly map: <R, A, B>(fa: Kind3<F, R, E, A>, f: (a: A) => B) => Kind3<F, R, E, B>
}

export interface Functor4<F extends URIS4> {
  readonly URI: F
  readonly map: <S, R, E, A, B>(
    fa: Kind4<F, S, R, E, A>,
    f: (a: A) => B
  ) => Kind4<F, S, R, E, B>
}

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.

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:

function addOne<URI extends URIS>(F: Functor1<URI>) {
  return (fa: Kind<F, number>): Kind<F, number> => F.map(fa, (n) => n + 1)
}

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

const addOneOption = addOne(functorOption) // (fa: Option<number>) => Option<number>

We can generalise further and support different kinds via overloading:

function addOne<URI extends URIS4, E>(
  F: Functor4C<URI, E>
): <S, R>(fa: Kind4<F, S, R, E, number>) => Kind4<F, S, R, E, number>
function addOne<URI extends URIS4>(
  F: Functor4<URI>
): <S, R, E>(fa: Kind4<F, S, R, E, number>) => Kind4<F, S, R, E, number>
function addOne<URI extends URIS3, E>(
  F: Functor3C<URI, E>
): <R>(fa: Kind3<F, R, E, number>) => Kind3<F, R, E, number>
function addOne<URI extends URIS3>(
  F: Functor3<URI>
): <R, E>(fa: Kind3<F, R, E, number>) => Kind3<F, R, E, number>
function addOne<URI extends URIS2, E>(
  F: Functor2C<URI, E>
): (fa: Kind2<F, E, number>) => Kind2<F, E, number>
function addOne<URI extends URIS2>(
  F: Functor2<URI>
): <E>(fa: Kind2<F, E, number>) => Kind<F, E, number>
function addOne<URI extends URIS>(
  F: Functor1<URI>
): (fa: Kind<F, number>) => Kind<F, number>
function addOne(F: any) {
  return (fa: any): any => F.map(fa, (n) => n + 1)
}

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

In fp-ts we can use HKT defined as:

export interface HKT<URI, A> {
  readonly _URI: URI
  readonly _A: A
}

export interface HKT2<URI, E, A> extends HKT<URI, A> {
  readonly _E: E
}

export interface HKT3<URI, R, E, A> extends HKT2<URI, E, A> {
  readonly _R: R
}

export interface HKT4<URI, S, R, E, A> extends HKT3<URI, R, E, A> {
  readonly _S: S
}

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

export interface Functor<F> {
  readonly URI: F
  readonly map: <A, B>(fa: HKT<F, A>, f: (a: A) => B) => HKT<F, B>
}

and use this to type the base case:

function addOne<URI extends URIS4, E>(
  F: Functor4C<URI, E>
): <S, R>(fa: Kind4<F, S, R, E, number>) => Kind4<F, S, R, E, number>
function addOne<URI extends URIS4>(
  F: Functor4<URI>
): <S, R, E>(fa: Kind4<F, S, R, E, number>) => Kind4<F, S, R, E, number>
function addOne<URI extends URIS3, E>(
  F: Functor3C<URI, E>
): <R>(fa: Kind3<F, R, E, number>) => Kind3<F, R, E, number>
function addOne<URI extends URIS3>(
  F: Functor3<URI>
): <R, E>(fa: Kind3<F, R, E, number>) => Kind3<F, R, E, number>
function addOne<URI extends URIS2, E>(
  F: Functor2C<URI, E>
): (fa: Kind2<F, E, number>) => Kind2<F, E, number>
function addOne<URI extends URIS2>(
  F: Functor2<URI>
): <E>(fa: Kind2<F, E, number>) => Kind<F, E, number>
function addOne<URI extends URIS>(
  F: Functor1<URI>
): (fa: Kind<F, number>) => Kind<F, number>
function addOne<URI>(F: Functor<URI>) {
  return (fa: HKT<URI, number>): HKT<URI, number> => F.map(fa, (n) => n + 1)
}

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

export interface FunctorComposition<F, G> {
  readonly map: <A, B>(fa: HKT<F, HKT<G, A>>, f: (a: A) => B) => HKT<F, HKT<G, B>>
}

export interface FunctorCompositionHKT1<F, G extends URIS> {
  readonly map: <A, B>(fa: HKT<F, Kind<G, A>>, f: (a: A) => B) => HKT<F, Kind<G, B>>
}

export interface FunctorCompositionHKT2<F, G extends URIS2> {
  readonly map: <E, A, B>(fa: HKT<F, Kind2<G, E, A>>, f: (a: A) => B) => HKT<F, Kind2<G, E, B>>
}

export interface FunctorCompositionHKT2C<F, G extends URIS2, E> {
  readonly map: <A, B>(fa: HKT<F, Kind2<G, E, A>>, f: (a: A) => B) => HKT<F, Kind2<G, E, B>>
}

export interface FunctorComposition11<F extends URIS, G extends URIS> {
  readonly map: <A, B>(fa: Kind<F, Kind<G, A>>, f: (a: A) => B) => Kind<F, Kind<G, B>>
}

export interface FunctorComposition12<F extends URIS, G extends URIS2> {
  readonly map: <E, A, B>(fa: Kind<F, Kind2<G, E, A>>, f: (a: A) => B) => Kind<F, Kind2<G, E, B>>
}

export interface FunctorComposition12C<F extends URIS, G extends URIS2, E> {
  readonly map: <A, B>(fa: Kind<F, Kind2<G, E, A>>, f: (a: A) => B) => Kind<F, Kind2<G, E, B>>
}

export interface FunctorComposition21<F extends URIS2, G extends URIS> {
  readonly map: <E, A, B>(fa: Kind2<F, E, Kind<G, A>>, f: (a: A) => B) => Kind2<F, E, Kind<G, B>>
}

export interface FunctorComposition2C1<F extends URIS2, G extends URIS, E> {
  readonly map: <A, B>(fa: Kind2<F, E, Kind<G, A>>, f: (a: A) => B) => Kind2<F, E, Kind<G, B>>
}

export interface FunctorComposition22<F extends URIS2, G extends URIS2> {
  readonly map: <FE, GE, A, B>(fa: Kind2<F, FE, Kind2<G, GE, A>>, f: (a: A) => B) => Kind2<F, FE, Kind2<G, GE, B>>
}

export interface FunctorComposition22C<F extends URIS2, G extends URIS2, E> {
  readonly map: <FE, A, B>(fa: Kind2<F, FE, Kind2<G, E, A>>, f: (a: A) => B) => Kind2<F, FE, Kind2<G, E, B>>
}

export interface FunctorComposition23<F extends URIS2, G extends URIS3> {
  readonly map: <FE, R, E, A, B>(fa: Kind2<F, FE, Kind3<G, R, E, A>>, f: (a: A) => B) => Kind2<F, FE, Kind3<G, R, E, B>>
}

export interface FunctorComposition23C<F extends URIS2, G extends URIS3, E> {
  readonly map: <FE, R, A, B>(fa: Kind2<F, FE, Kind3<G, R, E, A>>, f: (a: A) => B) => Kind2<F, FE, Kind3<G, R, E, B>>
}

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:

export interface URItoKind<S, R, E, A> {
  XPure: XPure<S, S, R, E, A>
  Effect: Effect<R, E, A>
  Either: Either<E, A>
  Option: Option<A>
}

export type URIS = keyof URItoKind<any, any, any, any>

We can then temporarily define the Kind to be:

export type Kind<F extends URIS, S, R, E, A> = URItoKind<S, R, E, A>[F]

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

export interface Functor<F extends URIS> {
  URI: F
  map: <A, A2>(
    f: (a: A) => A2
  ) => <S, R, E>(fa: Kind<F, S, R, E, A>) => Kind<F, S, R, E, A2>
}

and instances:

export const functorOption: Functor<"Option"> = {
  URI: "Option",
  map: (f) => (fa) => (fa._tag === "None" ? fa : { _tag: "Some", value: f(fa.value) })
}

and Bifunctor

export interface Bifunctor<F extends URIS> {
  URI: F
  bimap: <A, A2, E, E2>(
    f: (a: A) => A2,
    g: (a: E) => E2
  ) => <S, R>(fa: Kind<F, S, R, E, A>) => Kind<F, S, R, E2, A2>
}

and instances:

export const bifunctorEither: Bifunctor<"Either"> = {
  URI: "Either",
  bimap: (f, g) => (fa) =>
    fa._tag === "Left"
      ? { _tag: "Left", left: g(fa.left) }
      : { _tag: "Right", right: f(fa.right) }
}

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:

export type Param = "S" | "R" | "E"

export interface Fix<P extends Param, K> {
  Fix: {
    [p in P]: K
  }
}

export type OrFix<P extends Param, C, V> = C extends Fix<P, infer K> ? K : V

export type Kind<F extends URIS, C, S, R, E, A> = URItoKind<
  OrFix<"S", C, S>,
  OrFix<"R", C, R>,
  OrFix<"E", C, E>,
  A
>[F]

and change our typeclasses to become:

export interface Functor<F extends URIS, C = {}> {
  URI: F
  map: <A, A2>(
    f: (a: A) => A2
  ) => <S, R, E>(fa: Kind<F, C, S, R, E, A>) => Kind<F, C, S, R, E, A2>
}

export interface Bifunctor<F extends URIS, C = {}> {
  URI: F
  bimap: <A, A2, E, E2>(
    f: (a: A) => A2,
    g: (a: OrFix<"E", C, E>) => OrFix<"E", C, E2>
  ) => <S, R>(fa: Kind<F, C, S, R, E, A>) => Kind<F, C, S, R, E2, A2>
}

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

export const bifunctorStringValidation: Bifunctor<"Either", Fix<"E", string>> = {
  URI: "Either",
  bimap: (f, g) => (fa) =>
    fa._tag === "Left"
      ? { _tag: "Left", left: g(fa.left) }
      : { _tag: "Right", right: f(fa.right) }
}

// <A, A2, E, E2>(f: (a: A) => A2, g: (a: string) => string) => <S, R>(fa: Either<string, A>) => Either<string, A2>
export const bimapValidation = bifunctorStringValidation.bimap

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

Our addOne function looks much better:

function addOne<URI extends URIS, C>(
  F: Functor<URI, C>
): <S, R, E>(fa: Kind<URI, C, S, R, E, number>) => Kind<URI, C, S, R, E, number> {
  return F.map((n) => n + 1)
}

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:

export interface F_<A> {
  _tag: "F_"
  A: A
}

export interface URItoKind<S, R, E, A> {
  F_: F_<A>
  XPure: XPure<S, S, R, E, A>
  Effect: Effect<R, E, A>
  Either: Either<E, A>
  Option: Option<A>
}

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

function addOne<URI extends URIS, C>(
  F: Functor<URI, C>
): <S, R, E>(fa: Kind<URI, C, S, R, E, number>) => Kind<URI, C, S, R, E, number>
function addOne(F: Functor<"F_">): (fa: F_<number>) => F_<number> {
  return F.map((n) => n + 1)
}

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:

export function getFunctorComposition<F, G>(F: Functor<F>, G: Functor<G>): FunctorComposition<F, G> {
  return {
    map: (fa, f) => F.map(fa, (ga) => G.map(ga, f))
  }
}

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

export interface F_<A> {
  _tag: "F_"
  A: A
}
export interface G_<A> {
  _tag: "G_"
  A: A
}
export interface H_<A> {
  _tag: "H_"
  A: A
}

export interface URItoKind<S, R, E, A> {
  F_: F_<A>
  G_: G_<A>
  H_: H_<A>
  XPure: XPure<S, S, R, E, A>
  Effect: Effect<R, E, A>
  Either: Either<E, A>
  Option: Option<A>
}

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?

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:

export type KindURI = [URIS, ...URIS[]]

export type Kind<F extends KindURI, C, S, R, E, A> = ((...args: F) => any) extends (
  head: infer H,
  ...rest: infer Rest
) => any
  ? H extends URIS
    ? Rest extends KindURI
      ? URItoKind<
          OrFix<"S", C, S>,
          OrFix<"R", C, R>,
          OrFix<"E", C, E>,
          Kind<Rest, C, S, R, E, A>
        >[H]
      : URItoKind<OrFix<"S", C, S>, OrFix<"R", C, R>, OrFix<"E", C, E>, A>[H]
    : never
  : never

our typeclasses and instances change accordingly:

export interface Functor<F extends KindURI, C = {}> {
  URI: F
  map: <A, A2>(
    f: (a: A) => A2
  ) => <S, R, E>(fa: Kind<F, C, S, R, E, A>) => Kind<F, C, S, R, E, A2>
}

export interface Bifunctor<F extends KindURI, C = {}> {
  URI: F
  bimap: <A, A2, E, E2>(
    f: (a: A) => A2,
    g: (a: OrFix<"E", C, E>) => OrFix<"E", C, E2>
  ) => <S, R>(fa: Kind<F, C, S, R, E, A>) => Kind<F, C, S, R, E2, A2>
}

export const functorOption: Functor<["Option"]> = {
  URI: ["Option"],
  map: (f) => (fa) => (fa._tag === "None" ? fa : { _tag: "Some", value: f(fa.value) })
}

export const bifunctorEither: Bifunctor<["Either"]> = {
  URI: ["Either"],
  bimap: (f, g) => (fa) =>
    fa._tag === "Left"
      ? { _tag: "Left", left: g(fa.left) }
      : { _tag: "Right", right: f(fa.right) }
}

export const bifunctorStringValidation: Bifunctor<["Either"], Fix<"E", string>> = {
  URI: ["Either"],
  bimap: (f, g) => (fa) =>
    fa._tag === "Left"
      ? { _tag: "Left", left: g(fa.left) }
      : { _tag: "Right", right: f(fa.right) }
}

function addOne<URI extends KindURI, C>(
  F: Functor<URI, C>
): <S, R, E>(fa: Kind<URI, C, S, R, E, number>) => Kind<URI, C, S, R, E, number>
function addOne<C>(F: Functor<["F_"], C>): (fa: F_<number>) => F_<number> {
  return F.map((n) => n + 1)
}

But now we can do:

export const functorEitherOption: Functor<["Either", "Option"], {}> = {
  URI: ["Either", "Option"],
  map: (f) => (fa) =>
    fa._tag === "Left"
      ? { _tag: "Left", left: fa.left }
      : fa.right._tag === "None"
      ? { _tag: "Right", right: { _tag: "None" } }
      : { _tag: "Right", right: { _tag: "Some", value: f(fa.right.value) } }
}

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

// <S, R, E>(fa: Either<E, Option<number>>) => Either<E, Option<number>>
const addOneEitherOption = addOne(functorEitherOption)

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/7388dcf4eda013d806858d945c574fbb