4 ms·

I like this explanation, because it focuses in it's latter portion on the one thing that actually made Y click for me: expanding it. I think it's why it's so s

• drostie 12y ago
  Yeah, I agree. To explain where I see it most firmly, though, I have to explain how I personally got to Y. For me it was more interactive. You start with (Python syntax) def factorial(n): return 1 if n <= 1 else n * factorial(n - 1) and a task: to remove the second word "factorial" from inside the function, with the hint that it becomes a parameter. (In other words, we will hand you the factorial function of type `int -> int` and you have to make the factorial function out of it.) You thus write: def factmaker(recurse): def fact_try(n): return 1 if n <= 1 else n * recurse(n - 1) return fact_try This works if you pass in the function factorial -- but the problem is that now you don't have access to factorial at the outermost scope, so that factorial = factmaker(factmaker) # ...? fails because the types are wrong: when `factmaker` becomes `recurse` it receives an int as its argument, but `factmaker` needs a function as its argument. The key here for me was to accept `factorial = factmaker(factmaker)` and poke at `recurse` instead: how do we make it take a function as its argument? The only way to move forward is really that there really is which you can do with it is to replace `recurse` with `recurse(recurse)`, so that `recurse` can take a function as its argument: def factmaker(recurse): def fact_try(n): return 1 if n <= 1 else n * recurse(recurse)(n - 1) return fact_try factorial = factmaker(factmaker) And surprisingly, that works! As you've said, you can now kind of see why it works in terms of expansion: you return 1 if n is the right value, or otherwise you return factmaker(factmaker), which we said was factorial, of n - 1. (You can also see why infinite types get involved: this requires a duck-typing approach where you say "function" but don't peek inside any further; the actual type of factmaker is (itself) -> int -> int.) With a bit of abstraction to separate out the logic, restore the original form of factmaker, and handle more arguments, you can eventually get: def Y(maker): def F(f): def recurse(*a, **kw): return f(f)(*a, **kw) return maker(recurse) return F(F) def factmaker(fact): def fact2(n): return 1 if n <= 1 else n * fact(n - 1) return fact2 factorial = Y(factmaker) That's one step away from the actual lambda-calculus version.
  • throwaway_99837 12y ago
    Is this just a long winded way of saying: 'turn recursion into mutual recursion thus eliminating the self-reference.'?
• viksit 12y ago
  That was exactly my problem too - I've tried in a complementary post to talk about some practical applications of the YCombinator. http://www.viksit.com/tags/clojure/practical-applications-y-combinator-clojure http://www.viksit.com/tags/clojure/practical-applications-y-...
  • jarcane 12y ago
    That's pretty nice. I ultimately only included Y in Heresy as an academic exercise (I see the main purpose of it, if any, as being a playground for learning FP and Lisp concepts); on Racket at least, even with it's very good tail-call optimizations, it wasn't really performant enough by itself to be useful.