Hacker News Reader

Comment by Joker_vD | Hacker News Reader

    let  odd'(n, odd, even) = if n == 0 then False else even(n-1, odd, even)
    let even'(n, odd, even) = if n == 0 then  True else  odd(n-1, odd, even)
    let   odd(n) =  odd'(n, odd', even')
    let  even(n) = even'(n, odd', even')

Look ma, no hands! Well, actually, it is explicit closure-conversion done by hand so... anyhow, there are more straightforward and performant ways to get recursion in practice.

View on HN

In lambda calculus, you could use a variadic fixed point combinator to solve such recurrence relations elegantly

But you don't need to solve these, they're solved already: these four definitions are non-recursive. Yet when evaluated, they will exhibit properly recursive behaviour.

The only reason to use Y combinator in practice is when you for some reason don't want to keep manually passing the function to itself like "func fact(self, n) { return (n < 1) ? 1 : n * self(self, n-1) }; print(fact(fact, 5))" — maybe because it's tedious and error-prone, — and don't have a sufficiently ergonomic term-rewrite system at hand that would do this for you.

Yes, I realize that. However, the alternative using a variadic fixed point combinator looks slightly cleaner and would (optimally) reduce to the same term. For example, using a list-based vfix:

    even' _ odd n = if n == 0 then True else (odd (n - 1)))
    odd' even _ n = if n == 0 then False else (even (n - 1))
    even = head $ vfix [even', odd']
    odd = tail $ vfix [even', odd']

Here, the functions don't need to be passed explicitly to the "recursive" calls. I prefer this a lot, it makes my lambda functions much more readable.

Reply on news.ycombinator.com