6 ms·
For those of us who don't know what a Y-Combinator is or why it's useful, I found a SO answer [1] that makes sense to me: A Y-combinator is a "functional"
by abetusk 8y ago
For those of us who don't know what a Y-Combinator is or why it's useful, I found a SO answer [1] that makes sense to me:
A Y-combinator is a "functional" (a function that
operates on other functions) that enables recursion,
when you can't refer to the function from within
itself. In computer-science theory, it generalizes
recursion, abstracting its implementation, and
thereby separating it from the actual work of the
function in question. The benefit of not needing a
compile-time name for the recursive function is
sort of a bonus. =)
[1] https://stackoverflow.com/questions/93526/what-is-a-y-combinator/94056#94056 https://stackoverflow.com/questions/93526/what-is-a-y-combin...
- amelius 8y agoWondering if anybody here has ever used the Y-combinator in practice (and not as an academic exercise) ... (though I get that it can be a useful intermediate construct inside a compiler)
- billsix 8y agoIt's not useful in practice. But defining recursion via a function is a good mental exercise. I'm unaware of compilers using the Y combinator. Perhaps you were thinking of continuation passing style
- amelius 8y agoI believe Simon Peyton Jones has a chapter on combinators in his compiler book, but I don't think they are being used in the final proposed solution.
- taneq 8y agoFunctional programming: Making you feel clever by allowing you to solve problems that nobody else even knew existed, in order to let you do what everyone else could do from the start.
- billsix 8y agoDiscussion of the Y Combinator on news.ycombinator.com should not be derided.
- smadge 8y agoI’m not sure about it actually being used in compilers. However as I understand it the simply typed lambda calculus does not support recursive functions. If you want a typed functional language you have to introduce as a primitive a recursive combinatory like fix or the Y combinator.
- viksit 8y agoI’ve used it in a semi professional way (internal tooling in clojure). I’ve also written about it here (Practical applications of the ycombinator in clojure) [1]. [1] http://www.viksit.com/tags/clojure/practical-applications-y-combinator-clojure/ http://www.viksit.com/tags/clojure/practical-applications-y-...
- flatline 8y agoI’ve used it for recursion in anonymous functions in C#. It is straightforward enough to implement. Was it the best choice? Probably not, but I took the opportunity when presented.
- mehrdadn 8y agoNope, but I felt good when I finally managed to write one from scratch, because I knew for sure there was a time when I couldn't. So maybe the same would happen for you too.
- scrame 8y agoThere was a good practical ruby example for auto-vivification of hashes using the applicative ycombinator many years back, but I'm having trouble finding it.
- braythwayt 8y agohttps://www.sbf5.com/~cduan/technical/ruby/ycombinator.shtml https://www.sbf5.com/~cduan/technical/ruby/ycombinator.shtml
- kadoban 8y agoI've use something very similar in practice. Haskell's fixed point operator is: fix f = let x = f x in x This allows you to turn a non-recursive function into a recursive one, it factors the recursion out. It turns out that you can write a similar combinator (usually called mfix or memofix as I recall) that will result in a memoized version of the same recursive function. So it allows you to abstract away the memoization, write it once and then use it on any recursive function. That way you can write quite natural recursive functions and just memoize them in one wrapper call. https://hackage.haskell.org/package/memoize-0.8.1/docs/Data-Function-Memoize.html https://hackage.haskell.org/package/memoize-0.8.1/docs/Data-... looks similar to what I ended up with I used this in competitive programming for a while, it was nice for certain types of dynamic programming problems where the interesting part is the recursive definition, so once I found that there wasn't any more to write. Quite satisfying when it applied.
- KayEss 8y agoUseful when you have a lambda that needs to call itself, but the language doesn't bind the name until after the lambda is parsed (so you can't call by name). This happens in a few languages I think, C++ and C# for sure.
- dionidium 8y agoThis SO answer is posted every time this topic comes up, so I've seen it many times (and, in fact, I provided one of the answers there, too) and it's still the one and only place I've ever seen "functional" used as a noun like that. I'm always tempted to edit it, but maybe I'm missing something?
- dataflow 8y agoIt's correct as a noun. I believe it's taken from math: https://en.wikipedia.org/wiki/Functional_(mathematics) https://en.wikipedia.org/wiki/Functional_(mathematics) The CS term is "higher-order function": https://en.wikipedia.org/wiki/Higher-order_function https://en.wikipedia.org/wiki/Higher-order_function