Functional TypeScript and generics

Question

I have created a functional TypeScript solution for a code exercise, based on a Haskell solution for that same exercise. The exercise is to take a very large integer and finding the largest product of a group of adjacent digits of length n.

I wrote a curried function groups that takes an array of numbers and returns an array of arrays, with each nested array consisting of a number of digits.

For example:

groups([1,2,3,4,5,6,7,8,9])(3)

will return:

[[1,2,3], [4,5,6], [7,8,9]]

The groups function:

type groups = <A>(xs: A[]) => (n: number) => A[][];
const groups: groups = xs => n => xs.length < n ? [] : [take(n)(xs)].concat(groups(drop(1)(xs))(n)); 

// groups uses the functions 'take' and 'drop':

type take = <A>(n: number) => (xs: A[]) => A[];
const take: take = n => xs => xs.slice(0, n);

type drop = <A>(n: number) => (xs: A[]) => A[];
const drop: drop = n => xs => xs.slice(n);

But groups gives the error:

TS2322: Type '{}[][]' is not assignable to type 'A[][]'.

However when I add as [] the error goes away:

const groups: groups = xs => n => xs.length < n ? [] : [take(n)(xs)].concat(groups(drop(1)(xs))(n)) as [];

My first question is: why is that?

I stated the return type of groups is A[][] and the argument xs is of type A[] so why is this parsed as {}[][]? I don't fully understand how this works.

Then when I run the final solution with Quokka in Webstorm I get the correct answer but another error.

First, the final solution:

const largestProduct = (count: number): number[] => {
  const num = '73167176531330624919225119674426574742355349194934969835203127745063262395';
  const digits = num.split('').map((x: string) => parseInt(x, 10));

  return Math.max(...map(product)(groups(digits)(count)));
};

// the functions 'map' and 'product' used:

type map = <A, B>(f: (a: A) => B) => (xs: A[]) => B[];
const map: map = f => xs => xs.map(f);

type product = (xs: number[]) => number;
const product: product = xs => xs.reduce((acc, x) => acc * x, 1);

The line with the return statement gives the error:

TS2322: Type 'number' is not assignable to type 'number[]'

The map function indeed returns number[] but I use the spread operator here. For example Math.max(...[1,2,3]) does not give this error.

What am I doing wrong here?

Answer 1

The problem is that your take and drop functions have the type parameter A on the outer function, while the inference site for this parameter (in the form of the xs parameter) is on the inner function. Typescript can't really handle this, it wants to determine all type arguments when it checks the first call (for example take(1)) and since it has nowhere to infer A from it just infers it to {} leading to your problems.

The simplest solution is to move the type parameter on the inner function:

type groups = <A>(xs: A[]) => (n: number) => A[][];
const groups: groups = xs => n => xs.length < n ? [] : [take(n)(xs)].concat(groups(drop(1)(xs))(n)); 

type take = (n: number) => <A>(xs: A[]) => A[];
const take: take = n => xs => xs.slice(0, n);

type drop = (n: number) => <A>(xs: A[]) => A[];
const drop: drop = n => xs => xs.slice(n);

Just as a side not I am not 100% sold on your approach of defining the function type before. You can fully annotate an arrow function (including return type):

const groups = <A>(xs: A[]) => (n: number) : A[][] => xs.length < n ? [] : [take(n)(xs)].concat(groups(drop(1)(xs))(n)); 

const take = (n: number) => <A>(xs: A[]) : A[]=> xs.slice(0, n);

const drop = (n: number) => <A>(xs: A[]): A[] => xs.slice(n);

Although in this case the return type is not strictly necessary for take and drop and can be inferred based on return type (it is necessary for group because of the recursive nature of the function)

const groups = <A>(xs: A[]) => (n: number) : A[][] => xs.length < n ? [] : [take(n)(xs)].concat(groups(drop(1)(xs))(n)); 

const take = (n: number) => <A>(xs: A[]) => xs.slice(0, n);

const drop = (n: number) => <A>(xs: A[]) => xs.slice(n);

My preference is not to write types out that the compiler can figure out. Those few times I actually want to the full type of the symbol I just need to hover over it to know what TS inferred for the omitted types. But like I said this is just a preference your way is good too :)