higher kinded type in typescript from fp-ts and URI

Question

In fp-ts they have this workaround for higher kinded types:

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

And it can be used like this:

export interface Foldable<F> {
  readonly URI: F;
  reduce: <A, B>(fa: HKT<F, A>, b: B, f: (b: B, a: A) => B) => B;
}

What are the members _URI and what is _A?

is it clearer if written the following way? https://gist.github.com/jnizet/f8cc19c6e6c6f4937268cd5d095e851c. — JB Nizet, Apr 14 '18 at 07:44
`String` is a ground type, i.e. it has values. Let's denote ground types with `*`. `[a]` is a parameterized type, because it requires another ground type `a`. Consequently it has the form `* -> *`and is called a first-order type. Now a higher-order (or higher-kinded) type abstracts from the parameterized type `[]` and has the form `(* -> *) -> *`. `_URI` represents this first class paramterized type `(* -> *)` and `_A` represents the ground type `*`. That means an instance of `Foldable` requires a parameterized type (e.g. `[]`) and a ground type (e.g. `String`) to become a ground type itself. — , Apr 14 '18 at 10:11

score 10 · Accepted Answer · edited Jul 08 '23 at 19:42

10

This article written by the author of fp-ts explains very well,in combination with documentation on TypeScript's union types.

_A is the type of the value in our HKT: HKT<"Option", string> => Option<string>. We'll see how mapping works in a bit.

_URI is the identifier for the HKT, for example Option.ts. It has 2 instances, None and Some, both of which have "Option" as their _URI.

Taking a look at the usage of F in Foldable we can see it's used in the Type type, along with A; Type<F, A>. Assume F == "Option" & A == string so Type<F, A> == Type<"Option", string>, which is very similar to Option<string>. Currently, we cannot pass a generic type to another generic as it's generic parameter: <F,A>(fa: F<A>) will not compile and this is the main problem.

To achieve Type<"Option", string> => Option<string>, there are several "mapping" interfaces (this is explained in the article). We can see this done for Option here:

declare module './HKT' {
  interface URI2HKT<A> {
    Option: Option<A>
  }
}

The leftmost Option is a string key, the rightmost is the actual Option type, this is a normal record interface after all. Let's have a quick look at the definition of Type: type Type<URI extends URIS, A> = URI2HKT<A>[URI].

URI2HKIT is a map from our "Option" to our actual Option. It's allowing is to pass 2 generic parameters to get back our value type wrapped in our higher kinded type, solving the generics issue mentioned earlier.

edited Jul 08 '23 at 19:42

Community

1
1

answered Jul 01 '18 at 15:26

MaxWillmott

2,170
2
23
34

your answer has really helped. One thing I do not get is why both `Some` and `None` have both a `_tag` property and a `_URI` property – dagda1 Jul 14 '18 at 07:06
2

They do separate jobs. `_tag` as explained is the tag used to distinguish between the individual types in the union. `_URI` is used to extend the `URIS` type from `/lib/HKT` https://github.com/gcanti/fp-ts/blob/8ddf3b85af2e7f8b51cd7dda70be94564606916b/src/HKT.ts#L22. You'll find a usage of `URIS` in `foldable`: https://github.com/gcanti/fp-ts/blob/3f6023aaa35280c9753146437253cda762aa57fe/src/Foldable.ts#L22 – MaxWillmott Jul 15 '18 at 10:49
1

More relevant to this is the `Type` type; `type Type = URI2HKT[URI];`. Without the `extends URIS`, we would not be able to use `URI` as the index type `URI2HKT [URI]`. `URI2HKT = {"Option": Option , ...}` which generates: `URIS` = "Option" | ...; – MaxWillmott Jul 15 '18 at 11:09
This has the extra advantage of disallowing the mapping interface from having a different key to the `_URI`. If I do `{"Poption": Option}` then try to use `Type<"Poption", string>`, the resultant type will be `any` and not `Option`, as `"Poption"` isn't in `URIS`. (Though it's a shame it resolves to `any` and not a compile error). – MaxWillmott Jul 15 '18 at 11:13
i really can’t thank you enough. i finally understand this – dagda1 Jul 16 '18 at 05:54
1

@MaxWillmo looks like a typescript bug (thanks for pointing out), I think I found a way to fix it though https://github.com/gcanti/fp-ts/pull/529 – gcanti Jul 17 '18 at 07:18

higher kinded type in typescript from fp-ts and URI

1 Answers1

Linked