Hacker News Reader

Comment by marvinborner | Hacker News Reader

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