Is it possible to legitimately type a reduce/merge operation on an array?

Question

I have this code, which works as written but requires ignoring the error Type instantiation is excessively deep and possibly infinite.

type Something<T> = () => T;

type SomethingParam<S extends Something<any>> = ReturnType<S>

type CombineSomethings<S1 extends Something<any>, S2 extends Something<any>> = Something<SomethingParam<S1> & SomethingParam<S2>>;

type First<A extends Array<any>> = A[0];
// from https://stackoverflow.com/a/56370310
type Rest<T extends any[]> =  ((...t: T) => void) extends ((h: any, ...r: infer R) => void) ? R : never;

// @ts-ignore without specific input this type is infinitely recursive and barfs, even ignored it will be resolved correctly when called
type MergeAllThings<Sa extends Array<Something<any>>> = Rest<Sa> extends [] ? First<Sa> : CombineSomethings<First<Sa>, MergeAllThings<Rest<Sa>>>

type Merged = MergeAllThings<[() => ({foo: 'foo'}), () => ({bar: 'bar'})]>

In the code i have now, when i provide the array type to the generic, it gives me exactly what i'm looking for, but MergeAllThings in its generic form, and any utilities that use it before actually calling it throw the recursion error.

The error makes sense, in the generic form the array has no length so it never hits the base case, but i'm not sure how else to write this.

I tried to find existing examples, like Object.assign link that do basically the same thing, but the accepted practice seems to be to define overloads for every possible number of arguments up to a certain point and then have a fall through that returns any, which i'd really rather not do.

Is there a way to accomplish what i'm trying to do legitimately in typescript?

score 1 · Accepted Answer · answered Dec 11 '20 at 21:27

The support for recursive conditional types added in TypeScript 4.1 is great, but isn't perfect and can still end up causing performance issues or unexpected warnings.

If the compiler can't be sure that the recursion will terminate, you get an error. There are usually ways to finagle the expressions to avoid this, but it's more of an art than a science. For the particular algorithm you're following, I would rewrite this using the support for variadic tuple types added in TypeScript 4.0:

type MergeAllThings<S extends Something<any>[]> =
  S extends [infer F, ...infer R] ? F extends Something<any> ? R extends Something<any>[] ?
  R extends [] ? F : CombineSomethings<F, MergeAllThings<R>> : never : never : never

This works without error, and sidesteps the First and Rest definitions:

type Merged = MergeAllThings<[
  () => ({ foo: 'foo' }), () => ({ bar: 'bar' }), () => ({ baz: 'baz' })
]>
/* type Merged = () => {
    foo: 'foo';
} & {
    bar: 'bar';
} & {
    baz: 'baz';
} */

On the other hand, if you're really just looking for an "intersection of a bunch of things", you can do this without recursion by using contravariance in distributive conditional types to turn "unions of stuff" into "intersections of stuff", shown here as UnionToIntersection:

type UnionToIntersection<U> =
  (U extends any ? (k: U) => void : never) extends ((k: infer I) => void) ? I : never

In this case, MergeAllThings<S> might be seen as just getting the union of return types of S, turning that into an intersection, and then making that the return type of a new function type:

type MergeAllThings2<S extends Something<any>[]> =
  Something<UnionToIntersection<SomethingParam<S[number]>>>;

type Merged2 = MergeAllThings2<[
  () => ({ foo: 'foo' }), () => ({ bar: 'bar' }), () => ({ baz: 'baz' })
]>;
/* type Merged2 = () => {
    foo: 'foo';
} & {
    bar: 'bar';
} & {
    baz: 'baz';
} */

I usually avoid recursion in the type system if I can help it; the union-to-intersection solution scales better for longer tuples.

There's somewhat of a difference between MergeAllThings and MergeAllThings2, depending on whether the tuple elements' return types are themselves union types at all. If so, (e.g., MergeAllThings<[()=>(A | B), ()=>(C | D)]>), you might get the wrong answer: (e.g., ()=>(A & B & C & D)) you can use a more complicated version like

type MergeAllThings3<S extends Something<any>[]> =
  Something<Extract<UnionToIntersection<{ [K in keyof S]:
    S[K] extends Something<infer R> ? [R] : never }[number]>, [any]>[0]>;

in which we first wrap each return type (e.g., [A | B] | [C | D]) so that the union-to-intersection doesn't conflate outer unions with inner unions (e.g., [A | B] & [C | D]), and then unwrap at the end (e.g., (A | B) & (C | D))... but that could be overkill depending on your needs.

Playground link to code

this is an amazing answer. for now i'm using the last suggestions because it seems like the best/most flexible. but for my own education, i'm trying to figure out why your first response works and my original doesn't. i added some of the extra conditions you have, and changed my first/rest helpers to use variadic tuples. it seems like it won't work unless the tuple extraction is done inline, maybe because that is the only way to get it to narrow the type correctly. do you have any input on that? — tomwoodward, Dec 14 '20 at 19:34
Sometimes the compiler can more easily "see" that a recursive type is okay when everything is inline like `type X = {x: X}`, whereas it takes a more pessimistic attitude when the types are broken into multiple pieces like `type F = {x: T}; type X = F`. The latter is unacceptably circular, while the former is just fine. I'm not 100% sure exactly what's going on with `MergeAllThings` to the extent that I can fully explain it (as I said, it's more of an art than a science in my experience), but that's my intuition here also. — jcalz, Dec 14 '20 at 21:14

Is it possible to legitimately type a reduce/merge operation on an array?

1 Answers1