3 ms·
In lambda calculus, you could use a variadic fixed point combinator to solve such recurrence relations elegantly
by marvinborner 2y ago
In lambda calculus, you could use a variadic fixed point combinator to solve such recurrence relations elegantly
- Joker_vD 2y agoBut 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.
- marvinborner 2y agoYes, 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.