Higher-order type functions in TypeScript?

Question

Please consider the following pseudo-code trying to define a higher-order type function with a function-typed parameter M<?>:

type HigherOrderTypeFn<T, M<?>> = T extends (...)
  ? M<T>
  : never;

M<?> is syntactically incorrect TypeScript, but declaring the type signature as HigherOrderTypeFn<T, M> yields the error Type 'M' is not generic. ts(2315) on the second line.

Am I correct assuming that such a type is currently unrepresentable in TS?

Dukas

Answer 1

You're correct, it's not currently representable in TypeScript. There's a longstanding open GitHub feature request, microsoft/TypeScript#1213, which should probably be titled something like "support higher kinded types" but currently has the title "Allow classes to be parametric in other parametric classes".

There are some ideas in the discussion about how to simulate such higher kinded types in the current language (see this comment for a concrete example), but in my opinion they probably don't belong in production code. If you have some specific structure you're tying to implement, maybe something appropriate can be suggested.

But in any case if you want to increase the chance (probably negligibly so, unfortunately) that this will ever happen you might want to go to that issue and give it a 👍 and/or describe your use case if you think it's particularly compelling compared to what's already there. !

Bracknell

Thanks @Bracknell for clearing this up! This was an experiment on my part (trying to DRY up my typing), but I agree I’ll be better off implementing this in a more concise (albeit more redundant) way in production. Nice to see though that such a construct is doable with current TS semantics. – Dukas

This discussion makes me think that the future programming languages will look a lot like Haskell... – Colliery

this is why I never got into typescript – Hochman

Answer 2

For you and others searching for a workaround, you can try a simple idea based on placeholders (see this comment in the discussion mentioned by jcalz):

type Placeholder = {'aUniqueKey': unknown};
type Replace<T, X, Y> = {
  [k in keyof T]: T[k] extends X ? Y : T[k];
};

So, your function would look like follows:

type HigherOrderTypeFn<T, M> = T extends (...) ? Replace<M, Placeholder, T> : never;

and be called for example like that:

type M<U> = U[];
type X = HigherOrderTypeFn<number, M<Placeholder>> // is number[] (if ... is number)

Palanquin

Answer 3

For people coming across this, there's this nice example floating around on the TypeScript discord server:

export interface Hkt<I = unknown, O = unknown> {
  [Hkt.isHkt]: never,
  [Hkt.input]: I,
  [Hkt.output]: O,
}

export declare namespace Hkt {
  const isHkt: unique symbol
  const input: unique symbol
  const output: unique symbol

  type Input<T extends Hkt<any, any>> =
    T[typeof Hkt.input]

  type Output<T extends Hkt<any, any>, I extends Input<T>> =
    (T & { [input]: I })[typeof output]

  interface Compose<O, A extends Hkt<any, O>, B extends Hkt<any, Input<A>>> extends Hkt<Input<B>, O>{
    [output]: Output<A, Output<B, Input<this>>>,
  }

  interface Constant<T, I = unknown> extends Hkt<I, T> {}
}

Which can be used as follows. The snippet below defines a SetFactory, where you specify the type the desired set type when creating a factory, e.g. typeof FooSet or typeof BarSet . typeof FooSet is the constructor for a FooSet and is like a higher kinded type, the constructor type takes any T and returns a FooSet<T>. The SetFactory contains several methods such as createNumberSet, which returns a new set of the given type, with the type parameters set to number.

interface FooSetHkt extends Hkt<unknown, FooSet<any>> {
    [Hkt.output]: FooSet<Hkt.Input<this>>
}
class FooSet<T> extends Set<T> {
    foo() {} 
    static hkt: FooSetHkt;
}

interface BarSetHkt extends Hkt<unknown, BarSet<any>> {
    [Hkt.output]: BarSet<Hkt.Input<this>>;
}
class BarSet<T> extends Set<T> { 
    bar() {} 
    static hkt: BarSetHkt;
}

class SetFactory<Cons extends {
    new <T>(): Hkt.Output<Cons["hkt"], T>;
    hkt: Hkt<unknown, Set<any>>;
}> {
    constructor(private Ctr: Cons) {}
    createNumberSet() { return new this.Ctr<number>(); }
    createStringSet() { return new this.Ctr<string>(); }
}

// SetFactory<typeof FooSet>
const fooFactory = new SetFactory(FooSet);
// SetFactory<typeof BarSet>
const barFactory = new SetFactory(BarSet);

// FooSet<number>
fooFactory.createNumberSet();
// FooSet<string>
fooFactory.createStringSet();

// BarSet<number>
barFactory.createNumberSet();
// BarSet<string>
barFactory.createStringSet();

Short explanation of how this works (with FooSet and number as an example):

• The main type to understand is Hkt.Output<Const["hkt"], T>. With our example types substituted this becomes Hkt.Output<(typeof FooSet)["hkt"], number>. The magic now involves turning this into a FooSet<number>
• First we resolve (typeof FooSet)["hkt"] to FooSetHkt. A lot of the magic lies here, by storing the info about how to create a FooSet in the static hkt property of FooSet. You need to do this for each supported class.
• Now we have Hkt.Output<FooSetHkt, number>. Resolving the Hkt.Output type alias, we get (FooSetHkt & { [Hkt.input]: number })[typeof Hkt.output]. The unique symbols Hkt.input / Hkt.output help for creating unique properties, but we could have also used unique string constants.
• Now we need to access the Hkt.output property of FooSetHkt. This is different for each class and contains the details on how to construct a concrete type with the type argument. FooSetHkt defines the output property to be of type FooSet<Hkt.Input<this>>.
• Finally, Hkt.Input<this> just acceses the Hkt.input property of FooSetHkt. It would resolve to unknown, but by using the intersection FooSetHkt & { [Hkt.input]: number }, we can change the Hkt.input property to number. And so if we've reached our goal, Hkt.Input<this> resolves to number and FooSet<Hkt.Input<this>> resolves to FooSet<number>.

---

For the example from the question, Hkt.Output is essentially what was being asked for, just with the type parameters reversed:

interface List<T> {}
interface ListHkt extends Hkt<unknown, List<any>> {
    [Hkt.output]: List<Hkt.Input<this>>
}
type HigherOrderTypeFn<T, M extends Hkt> = Hkt.Output<M, T>;
// Gives you List<number>
type X = HigherOrderTypeFn<number, ListHkt>;

Doggo

Answer 4

There's an implementation of HKTs (leveraging module augmentation) in fp-ts.

The workaround for Higher Kinded Types as documented here by its author is:

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

And 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;
}

Check it out this question: higher kinded type in typescript from fp-ts and URI

Maybe that can shed some light?

Cheers

Marguritemargy