... until the collector arrives ...

This "blog" is really just a scratchpad of mine. There is not much of general interest here. Most of the content is scribbled down "live" as I discover things I want to remember. I rarely go back to correct mistakes in older entries. You have been warned :)

2012-02-11

Y-Combinator in Mathematica

Adding to the growing collection of posts about the Y-combinator...

Inspired by a question on the Mathematica StackExchange site, I came up with this implementation of the Y-combinator in Mathematica:

Y[f_] := #[#]&[Function[n, f[#[#]][n]]&]

... along with a test case:

fac[r_] := If[# < 2, 1, # * r[# - 1]]&

Y[fac][10]

What I really wanted to do was emulate the expression in that StackExchange question: (#[#] &)[#[#][#] &]. Note that it uses nothing but the special slot input form #, the postfix function operator &, the matchfix application operator [...] and parentheses. Expressing the Y-combinator in a form like this has eluded me so far.

Not all is lost, though. The Mathematica definition suggested some "simplifications" (obfuscations?) for the versions that I have used in other languages.

Javascript:

function Y(f) {
   return (function(g) { return g(g) })(
     function(h) { return function(n) { return f(h(h))(n) }} )
}

Scheme:

(define Y
   (lambda (f)
     ((lambda (g) (g g))
      (lambda (h) (lambda (n) ((f (h h)) n))) )))

Another Mathematica version, using the rarely seen \[Function] operator (entered as ESC f n ESC):

Y = f ↦ (g ↦ g[g])[h ↦ n ↦ f[h[h]][n]]

(*Y = f \[Function] (g \[Function] g[g])[h \[Function] n \[Function] f[h[h]][n]]*)

Blog Archive