typescripttypescript-genericshigher-order-functions

How to correctly type a transduce function in TypeScript?


Below is a minimal transduce implementation, but its output type is incorrect. Looking for what needs to change to correct it. Here's the example in a TS Playground containing transduce and all arguments passed to it. In case it helps, here's a possibly more minimal example playground. I'm not sure if it's oversimplified.

/* transducer */
const map =
  <VOut,VIn,KIn>(mapper: (v: VIn, k?:KIn) => VOut) =>
    <A, R>(nextReducer: (acc: A, v: VOut, k?:KIn) => R) =>
      <V extends VIn>(acc: A, value: V, key?:KIn) => nextReducer(acc, mapper(value,key), key);

/* final reducer */
const toSet = <V,K,A>(acc:A=new Set() as A, v: V, k?:K) => {
  (acc as Set<V>).add(v);
  return acc as Set<V>;
};

/* test map and toSet by themselves */
// test correct - mapNum is Set<string> 
const mapStr = map((v: number) => `${v}`)(toSet)(undefined,1,'a');
// test correct - mapNum is Set<number> 
const mapNum = map((v: number) => v + 2)(toSet)(undefined,1,'a');
// @ts-expect-error test correct - string 'aa' passed to number mapper should error
const mapStrError = map((v: number) => v + 2)(toSet)(undefined,'aa','a');

/* transduce */
const transduce = <AccIn,AccOut,VIn,VOut,KIn,KOut>(
  collection: Map<KIn, VIn>,
  transducer:  <
                NextReducer extends (a:any,v:any,k?:any)=>any
              >(nextReducer:NextReducer)=>((a:AccIn,v:VIn,k?:KIn)=>AccOut),
  finalReducer: (a:AccOut|undefined,v:VOut,k?:KOut)=>AccOut,
) => {
  let combinedReducer = transducer(finalReducer);
  let acc = undefined as AccOut;
  for (const [key, value] of collection) {
    acc = combinedReducer(acc as unknown as AccIn, value, key);
  }
  return acc;
}

/* test transduce */
// @ts-expect-error correct - string collection passed to number mapper should error
const transduceStr = transduce(new Map([['a', 'aa']]), map((v: number) => v * 2), toSet);

// incorrect - transduceNum is unknown. Should be Set<number> like mapNum
const transduceNum = transduce(new Map([['a', 1]]), map((v: number) => v * 2), toSet);

Solution

  • TypeScript cannot perform the sort of inference you're looking for. See microsoft/TypeScript#30727 for an authoritative answer.

    TypeScript's ability to infer higher order generics is quite limited. Theoretically it could use a full unification algorithm which would be able to handle arbitrary generic functions that operate on other generic functions and produce the results you're looking for. There is a discussion at microsoft/TypeScript#30134 about this. The current inference algorithm is essentially heuristic in nature and is optimized for dealing with a wide range of real world code, and especially for dealing with partially written code, so that IDEs can complete and suggest things more easily than full unification would. See this comment by the language architect on microsoft/TypeScript#17520.

    So for better or worse TypeScript cannot infer your generic type arguments the way you want, and this is unlikely to change significantly in the future. You will need to work around the issue somehow. One general approach is to manually specify the intended generic type arguments instead of letting TypeScript infer them. This is tedious, especially if your generic function has... six... type parameters, but will always behave predictably and let you know if you have a real error:

    const transduceNum = transduce<Set<number>, Set<number>, number, number, string, string>(
      new Map([['a', 1]]), map((v: number) => v * 2), toSet
    ); // okay, Set<number> as desired, no error
    

    There might be ways to reorder your generic type parameters and use default type arguments so that you could specify fewer type arguments and still get the types you want.

    Or you could use instantiation expressions to turn your generic function arguments like toSet into specific non-generic functions:

    const transduceNum = transduce(
      new Map([['a', 1]]), map((v: number) => v * 2), toSet<number, string, Set<number>>
    ); // okay, Set<number> as desired, no error
    

    Or you could work around things by refactoring entirely, but this is out of scope of the question as asked so I won't digress further.

    Playground link to code