DEV Community

loading...
Cover image for TypeScript Sandbox: Type Tail|Curry, How to use `infer` word and recursion

TypeScript Sandbox: Type Tail|Curry, How to use `infer` word and recursion

jsmitar profile image JSmith AR ใƒป3 min read

Function tail

Let's to see first what is tail.

function tail<T extends any[]>([head, ...tail]: T): Tail<T> {
  return tail as Tail<T>;
}

const array_tail = tail([1, 2, 3, 4]);
// out: [2,3,4]

It's really simple, a pure function that drops the head of the array.

Now for build the type Tail we will follow the same approach, we need to do a trick.

// TS: 3.0^
type Tail<T extends any[]> = ((...array: T) => any) extends (
  head: any,
  ...tail: infer Tail_
) => any
  ? Tail_
  : never;

As TS 3.0^ doesn't allow to use array expresions to deconstruct T, we need to use a function with rest parameters and infer word to obtain the tail.

The main restriction for use infer is a conditional <left expr> extends <here infer a type> ? <access to infered type> : <otherwise>. As the arrays are used for type rest parameters, I put T in left hand of extends just like that ((...array: T) => any) and rigth hand I can deconstruct the array and infer what I'm interested me (head: any, ...tail: infer Tail_).

With TS 4.0^ we can simplify this definition, but the approach is the same.
Look at this.

// TS: 4.0^
type Tail<T extends any[]> = T extends [head: any, ...tail: infer Tail_]
  ? Tail_
  : never;

๐Ÿ› Currifying functions

The currification is a Functional Programming technique that transforms a function with multiple arguments in a function that takes arguments one by one until the last argument is provided and then returns the final result.
The term curry is in honor of Haskell Brooks Curry, he was the great matematician who created the Lambda Calculus ๐Ÿ˜ƒ.

The cool thing about this, is that the currified functions allow to do partial application of functions.

Consider the next function.

// currified add function
const add = (a: number) => (b: number) => a + b;

// partial application with 10
const add10 = add(10);
// function: (b: number) => 10 + b

add10(1);
// out: 11

add10(5);
// out: 15

Instead of declare add as (a, b) => a + b, add takes first a, later takes b and then do the calculation.

Now the idea is to create a type that takes a function and gives the same function but currified.

First we are going to create a Curry type that bit to bit let us to improve.

type Length<T extends any[]> = T["length"];

type Head<T extends any[]> = T extends [] ? never : T[0];

type Curry<
  F extends (...args: any[]) => any,
  P extends any[] = Parameters<F>, // P: are the parameters of F
  R = ReturnType<F> // R: the return type of F
> = Length<P> extends 0 | 1
  ? F
  : (arg_0: Head<P>) => Curry<(...args: Tail<P>) => R>;

type F0 = Curry<() => Date>;
// type: () => Date

type F1 = Curry<(a: number) => Date>;
// type: (arg: number) => Date

type F2 = Curry<(a: number, b: string) => Date>;
// type: (arg: number) => (arg: string) => Date

First I decompose F in parameters P and return type R. If the function has 0 or 1 arguments then F is already currified, else takes the Head of P and with help Tail previously declared, I defined the return in terms of itself Curry<(...args: Tail<P>). But this Curry type has some issues.

type F = Curry<(a?: string, b?: string, c?: string) => Date>;
// type: (a: string) => (b: string) => (c?: string) => Date

Now the parameters a and b aren't optional. This happens because Head don't preserve the optionality.

type First = Head<[string?]>;
// type: string

To control this edge case we need to discard the tail without loss the optionality in the front of the array.

type Take1<T extends any[]> = Take1_<T>["type"];

interface Take1_<T extends any[]> {
  type: T extends { 0: infer U } ? [U] 
        : T extends { 0?: infer U } ? [U?] 
          : never;
}

type T1 = Take1<[string?]>;
// type: [string?]

type T2 = Take1<[string]>;
// type: [string]

Then with this new type we can fix Curry.

type Curry<
  F extends (...args: any[]) => any,
  P extends any[] = Parameters<F>, // P: are the parameters of F
  R = ReturnType<F> // R: the return type of F
> = 
  Take1<Tail<P>> extends never
    ? F // F is () => any | (a: any) => any | (a: any, ...args: any[]) => any
    : (...args: Take1<P>) => Curry<(...args: Tail<P>) => R>;

type F = Curry<(a?: string, b?: string, ...c: string[]) => Date>;
// type: (a?: string) => (b?: string, ...c: string[]) => Date

When Take1<Tail<P>> is never it means that P is [] | [any] | any[] and then is time to stop the recursion. Aftermore note how functions such as (a: any, ..args: any[]) => any will not be currified, but we could do it if we wanted.

How would you implement a curry function for this type?

Edit ts_curry

Discussion (0)

pic
Editor guide