Is it possible to implement a TypeScript generic version of Y-combinator?

Issue

The Y-combinator JavaScript implementation:

const Y = g => (x => g(x(x)))(x => g(x(x)))
//or
const Y = f => {
  const g = x => f(x(x))
  return g(g)
}

I'm just curious, is it possible to implement a TypeScript generic version of Y-combinator?

type Y<F> = ???

Solution

The short answer:

The TypeScript type of a fixed point combinator whose input is a one-argument function is:

type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;

The long answer follows:

---

The type of a fixed point combinator should be a generic function of the following form:

type Fixed = <T>(f: (t: T) => T) => T;

So if you had a value fixed of type Fixed, you should be able to call it on any one argument function whose output is the same type as the input, and (magically?) get a result which is a fixed point of that function:

console.log(fixed(Math.cos)) // 0.739085...

You can get something like this behavior for certain well-behaved functions f just by starting with some random value and iterating f a bunch of times:

const fixed: Fixed = f => {
  let r = null as any;
  for (let i = 0; i < 1000; i++) r = f(r);
  return r;
}

That's a silly implementation (or at least not the classic one) but it works well enough for the normal use case of finding a fixed point of a function whose input is itself a function.

For example, let's define a protoFactorial function whose fixed point calculates the factorial of a non-negative integer via recursion:

const protoFactorial = (f: (n: number) => number) =>
  (n: number) => n === 0 ? 1 : n * f(n - 1)

Note that the input f is a function of type (n: number) => number, and the output is another function of this type, whose input n is the n is the number whose factorial we want to calculate. If n is 0 it returns 1; otherwise it returns n * f(n - 1).

If we have a fixed point combinator fixed, we should be able to get the desired factorial function like so:

const factorial = fixed(protoFactorial);
console.log(factorial(7)); // 5040

And the above fixed does work for this.

---

But for the Y combinator in particular we tend to require that the type T on which it operates is itself a function type (although in untyped lambda calculus there's not really a distinction), and therefore I'd be inclined to give Y a generic type that specifically depends on the input and output of the T function type:

type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;

That is like Fixed if you replace T with (i: I) => O. Anyway, with a value Y of type Y, we should presumably be able to call Y(protoFactorial) and get the correct factorial.

Here's an implementation of Y in TypeScript:

interface Ω<T> {
  (x: Ω<T>): T;
}

const Y: Y = <I, O>(F: (f: (i: I) => O) => (i: I) => O) =>
  ((x: Ω<(i: I) => O>) => F(x(x)))((x: Ω<(i: I) => O>) => F(x(x)));

Note that in order to strongly type the Y combinator implementation we need the recursive type Ω<T>; the x parameter has to be of such a type in order to allow a call like x(x) to compile and produce an output of type (i: I) => O.

This is the same as your g => (x => g(x(x)))(x => g(x(x))) implementation with g renamed to F and with type annotations to help the compiler.

---

That's the answer to the question as asked, but unfortunately the Y combinator cannot be used as-is in JavaScript, which eagerly evaluates all function inputs before evaluating the function body:

try {
  const factorial = Y(protoFactorial);
} catch (e) {
  console.log(e); // too much recursion
}

Oops, calling Y(protoFactorial) eagerly expands out to the unending F(F(F(F(F(F(.... and explodes.

---

To get a viable fixed-point combinator in JavaScript, we need something more like the Z combinator which delays the calculation of x(x) by using eta abtraction (see What is Eta abstraction in lambda calculus used for?) to produce v => x(x)(v):

const Z: Y = <I, O>(F: (f: (i: I) => O) => (i: I) => O) =>
  ((x: Ω<(i: I) => O>) => F(v => x(x)(v)))((x: Ω<(i: I) => O>) => F(v => x(x)(v)));

Now if we use Z in place of Y it works at runtime:

const factorial = Z(protoFactorial);
// const factorial: (i: number) => number
console.log(factorial(7)); // 5040

---

Of course, if all we care about are the typings and we are don't need to pretend that JavaScript and TypeScript lack first-class recursion at runtime, then we can just implement a function of type Y recursively with a lot less hassle:

const R: Y = f => f(x => R(f)(x))    
console.log(R(protoFactorial)(7)) // 5040

---

From the perspective of the type system, all of fixed, Y, Z, and R are values of type Y:

function acceptY(y: Y) { }
acceptY(fixed)
acceptY(Y)
acceptY(Z)
acceptY(R)

And so we can say fairly confidently that the TypeScript type of a fixed point combinator whose input is a one-argument function is:

type Y = <I, O>(F: (f: (i: I) => O) => ((i: I) => O)) => (i: I) => O;

Playground link to code

Answered By - jcalz