News for hackers. Stuff that matters.
Re:The Y Combinator in Go with generics by justinpombrio on Sunday June 12, 2022 @11:35AM (#31715283)
The Y combinator lets you implement recursion without using recursion. For example, a Javascript closure can't refer to itself. But if we define the (strict) Y combinator using JS closures:

    let Y = f => (x => x(x))(x => f(z => x(x)(z)))
then we can call it, again only using closures, and define a function that sums the numbers from 1 to N by "calling itself":

    let sumToN = Y(sumToN => n => n == 0 ? 0 : n + sumToN(n-1))

    sumToN(4)
    // -> 10
In practice, no one actually implements recursion this way because it would be slow. So instead it's more of a statement about the expressiveness of languages, and how "we have recursion!" doesn't actually give you any power you didn't have before, if you had functions.

There are no comments on this comment yet.