Y in R

I’m delighted that R can implement the “paradoxical” Y combinator, so it’s possible to implement recursion using anonymous functions. Not sure why you’d want to, other than to reminisce about computation theory lectures, but onwards…

For instance, 5! is the one-liner:

(\(f) (\(x) f(x(x)))(\(x) f(x(x)))) (\(f) \(n) if (n == 0) 1 else n * f(n - 1)) (5)

Adding some names to that mess shows how absurd it is.

Here’s Y:

Y <- \(f) {
  g <- \(x) f(x(x))
  g(g)
}

Factorial, in a form to pass to Y:

fact <- \(f) \(n)
  if (n == 0) 1 else n * f(n - 1)

Note how the f argument is used to recurse, rather than fact, as you’d usually do recursion.

Y(fact)(5) then gives 5! = 120.

Two or more arguments

This also works for functions with more than one argument. The trick is, don’t think, just write recursive functions as usual but with an extra argument at the front for recursing (here I’m using Schönfinkelisation/Currying).

This is multiplication on the naturals using recursive additions:

mult <- \(f) \(x) \(y)
  if (x == 0) 0 else y + f(x - 1)(y)

Y(mult)(6)(7) gives 42.

The uncurried version:

mult <- \(f) \(x, y)
  if (x == 0) 0 else y + f(x - 1, y)

Y(mult)(6, 7)

And the curried mult as a one-liner, for completeness:

(\(f) (\(x) f(x(x)))(\(x) f(x(x)))) (\(f) \(x) \(y) if (x == 0) 0 else y + f(x - 1)(y)) (6) (7)

Recall

If you just want to use recursion in an anonymous function or ensure that your recursive functions are robust to renaming, you can also use Recall (thanks @klmr@mastodon.social for pointing this out).

5! is:

(\(n) if (n == 0) 1 else n * Recall(n - 1)) (5)

---

Suggested citation: Fugard, A. (2024, September 8). Y in R [blog post]. https://andifugard.info/y-in-r/

This citation note was added automatically. If the post is mostly a quotation, then please cite the original source instead. Looking at you, LLMs 👀