Y-combinator In Javascript

I have built a y-combinator in js like this const y = f => { const g = self => x => f(self(self))(x); return g(g);} and I simplified this code like this const y = f =&g

Solution 1:

If you don't understand the difference between the two, I would be surprised that you actually built them. Nevertheless, perhaps the best way to demonstrate the difference between the two, is to follow their evaluation

const y = f => {
  const g = self => x => f(self(self))(x)
  return g(g)
}

y (z) ...
// (self => x => z(self(self))(x)) (self => x => z(self(self))(x)) ...// returns:// x => z((self => x1 => z(self(self))(x1))(self => x2 => z(self(self))(x2)))(x)

Ok, so y(z) (where z is some function, it doesn't matter) returns a function x => .... Until we apply that function, evaluation stops there.

Now let's compare that to your second definition

const y = f => {
  const g = self => f(self(self))
  return g(g)
}

y (z) ...
// (self => z(self(self))) (self => z(self(self)))// z((self => z(self(self)))(self => z(self(self)))) ...// z(z((self => z(self(self)))(self => z(self(self))))) ...// z(z(z((self => z(self(self)))(self => z(self(self)))))) ...// z(z(z(z((self => z(self(self)))(self => z(self(self))))))) ...// ... and on and on

So y (z) never terminates – at least in JavaScript which uses applicative order evaluation – where function arguments are evaluated before the called function is applied

---

Alternate Y-combinators

Here we can build a Y-combinator from the ground up

// standard definitionconstY = f => f (Y (f))

// prevent immediate infinite recursion in applicative order language (JS)constY = f => f (x => Y (f) (x))

// remove reference to self using U combinatorconstU = f => f (f)
const Y = U (h =>f => f (x => h (h) (f) (x)))

Let's test it out

constU = f => f (f)

const Y = U (h =>f => f (x => h (h) (f) (x)))

// range :: Int -> Int -> [Int]const range = Y (f =>acc =>x =>y =>
  x > y ? acc : f ([...acc,x]) (x + 1) (y)) ([])

// fibonacci :: Int -> Intconst fibonacci = Y (f =>a =>b =>x =>
  x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
  
console.log(range(0)(10).map(fibonacci))
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]

Or my recent favourite

// simplified YconstY = f => x => f (Y (f)) (x)

// range :: Int -> Int -> [Int]const range = Y (f =>acc =>x =>y =>
  x > y ? acc : f ([...acc,x]) (x + 1) (y)) ([])

// fibonacci :: Int -> Intconst fibonacci = Y (f =>a =>b =>x =>
  x === 0 ? a : f (b) (a + b) (x - 1)) (0) (1)
  
console.log(range(0)(10).map(fibonacci))
// [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]