0

I am playing around with understanding how the Y-combinator works in functional programming. I have a basic factorial function which I have translated to:

console.log((f => n => (n===0) ? 1 : n*f(f)(n-1))(f => n => (n===0) ? 1 : n*f(f)(n-1))(5));
// 120

But how exactly does this simplify (to itself) after calling itself repeatedly? For example, after two times it looks like this:

const fact0 = (f => n => (n===0) ? 1 : n*f(f)(n-1))(f => n => (n===0) ? 1 : n*f(f)(n-1));

// 1. substitute "f => n => (n===0) ? 1 : n*f(f)(n-1)" for function call of f
const fact1 = (n => (n===0) ? 1 : n*(f => n => (n===0) ? 1 : n*f(f)(n-1))(f => n => (n===0) ? 1 : n*f(f)(n-1))(n-1));

// 2. ... ?
// 3. ... ?

// Test to make sure results are ok
console.log(fact0(5) === fact1(5))
David542
  • 104,438
  • 178
  • 489
  • 842
  • 1
    https://stackoverflow.com/questions/13759207/i-couldnt-understand-the-y-combinator – Bergi Apr 06 '22 at 18:39
  • @Bergi thanks for that link but I really don't get how it's simplified or at least a fixed point when calling itself. – David542 Apr 06 '22 at 19:34
  • It's not really calling itself. It's calling a new function that'll behave the same as the original. – Bergi Apr 06 '22 at 19:37
  • 2
    I show the precise evaluation of factorial using Y-combinator in [this Q&A](https://stackoverflow.com/a/37506975/633183). To gain better insight on how Y actually works, you can see [this Q&A](https://stackoverflow.com/a/57939039/633183). – Mulan Apr 09 '22 at 18:43
  • 1
    @Mulan The first one looks like a good duplicate target, don't you think? – Bergi Apr 09 '22 at 21:38
  • @Bergi it's not exactly the same `fact` function but i think the answer there serves the same purpose here. – Mulan Apr 11 '22 at 01:30

0 Answers0