Replace Generic Interface Type Parameter

Question

I am attempting to create a generic function interface for functor map, that respects the interface provided. In the code shown below, I would like the value of mb to be of type Maybe<number>, as opposed to the actual type Functor<number>.

I do realize that one possible solution is to add an overload to the interface FMap. The reason I am not happy with this solution is that I would like this code to reside in a package, allowing users to create implementations for Functor, and have the behavior I described above when using the function map.

interface Functor<A> {
  map<B>(fn: (a: A) => B): Functor<B>;
}

interface FMap {
  <A, B>(fn: (a: A) => B, Fa: Functor<A>): Functor<B>;
}

const map: FMap = (fn, Fa) => (
  Fa.map(fn)
);

class Maybe<A> implements Functor<A> {
  constructor(private readonly a: A) {}
  map<B>(fn: (a: A) => B): Maybe<B> {
    return new Maybe<B>(fn(this.a));
  }
}


const sqr = (x: number) => x*x;
const ma = new Maybe(5);
const mb = map(sqr, ma);

I would like some means of expressing the following semantics:

// Theoretical Code

interface PretendFMap {
  <A, B, FA extends Functor<A>>(fn: (a: A) => B, Fa: FA): FA extends (infer F)<A> ? F<B> : never;
}

This however does not function, as a generic interface, without a type parameter is not a valid TypeScript type, i.e. an interface such as Functor requires a type parameter to be considered a type, Functor itself is not a valid type.

If there are currently no means of expressing these semantics, any suggestions regarding a solution that requires as little code as possible on the side of the user would be greatly appreciated.

Thank you in advance for your time and consideration.

Answer 1

What stands in our way, is when you try to pass a type variable F as type parameter to another type variable T, like T<F>, TS just doesn't allow that even if you know T is in fact a generic interface.

There's a discussion on this topic dated back to 2014 in a github issue, and it's still open, so TS team probably won't support it in near future.

The term for this language feature is called higher kinded type. Using that search keyword, google took me to a trip down the rabbit hole.

It turns out theres exist a very clever workaround!

By leveraging TS declaration merging (aka module augmentation) feature, we can effectively define an empty "type store" interface, which acts like a plain object that holds reference to other useful types. Using this technique, we are able to overcome this blocker!

I'll use your case as example to cover the idea of this technique. If you want to dive deeper, I include some useful links at the end.

Here's the TS Playground link (spoiler alert) to the final result. See it in live for sure. Now let's break it down (or should I say build it up?) step by step.

1. First, let's declare an empty TypeStore interface, we'll update it's content later.

// just think of it as a plain object
interface TypeStore<A> { } // why '<A>'? see below


// example of "declaration merging"
// it's not re-declaring the same interface
// but just adding new members to the interface
// so we can amend-update the interface dynamically
interface TypeStore<A> {
  Foo: Whatever<A>;
  Maybe: Maybe<A>;
}

2. Let's also get the keyof TypeStore. Noted that as content of TypeStore gets updated, $keys also get updated accordingly.

type $keys = keyof TypeStore<any>

3. Now we patch up the missing language feature "higher kinded type", using a utility type.

// the '$' generic param is not just `string` but `string literal`
// think of it as a unique symbol
type HKT<$ extends $keys, A> = TypeStore<A>[$]

// where we mean `Maybe<A>`
// we can instead use:
HKT<'Maybe', A>  // again, 'Maybe' is not string type, it's string literal

4. Now we have the right tools, let's start building useful stuffs.

interface Functor<$ extends $keys, A> {
  map<B>(f: (a: A) => B): HKT<$, B>
}

class Maybe<A> implements Functor<'Maybe', A> {
  constructor(private readonly a: A) {}
  map<B>(f: (a: A) => B): HKT<'Maybe', B> {
    return new Maybe(f(this.a));
  }
}

// HERE's the key!
// You put the freshly declare class back into `TypeStore`
// and give it a string literal key 'Maybe'
interface TypeStore<A> {
  Maybe: Maybe<A>
}

5. Finally FMap:

// `infer $` is the key here
// remember what blocked us? 
// we cannot "infer Maybe from T" then apply "Maybe<A>"
// but we can "infer $" then apply "HKT<$, A>"!
interface FMap {
  <A, B, FA extends { map: Function }>
  (f: (a: A) => B, fa: FA): FA extends HKT<infer $, A> ? HKT<$, B> : any
}

const map: FMap = (fn, Fa) => Fa.map(fn);

---

Reference

1. The github discussion on supporting higer kinded type in TS
2. Entrance to the rabbit hole
3. Declaration Merging in TS Handbook
4. SO post on higher kinded type
5. Medium post by @gcanti, on higher kinded types in TS
6. fp-ts lib by @gcanti
7. hkts lib by @pelotom
8. typeprops lib by @SimonMeskens