Whats a one liner to describe the Y-Combinator to someone new to FP?
'An generic implementation of a fixed point attractor'
Hmm.. not quite it.
um.. 'DSEL's ? no-one calls them that.. 'DSL' has taken hold, although overloaded somewhat [eg graphical symbol set over UML, or language-in-a-language, the conventional meaning]
Whats a one liner to describe the Y-Combinator to someone new to FP?
For someone mathematically comfortable with the idea of higher-order functions, it's "a function operating on higher-order functions, that returns a fixed point of its argument". That is, Y(f) = f' such that f(f') = f', where f and f' are both higher-order functions. Of course, I doubt there're many people familiar with higher-order functions and fixed points that don't already know functional programming.
On the other hand, it's relatively easy to get a feel for what Y does if you try manually evaluating it in the lambda calculus. This is easy, since evaluating lambda calculus by hand is little more than repeated string substitution, but it's not really a "one liner".
From a "practical" standpoint of doing anonymous recursion, the way it works can be described as "Evaluating Y on an ersatz recursive function f evaluates f itself, but passes in Y(f) as an argument that f can evaluate in turn." Leaves Y as a black box, but makes it clearer how it creates recursive functions.
Honestly, trying to explain Y to someone new to functional programming is probably pointless. It's weird and mostly useless, since recursive functions will rarely need to be anonymous in practice. I remember understanding Y as being one of those almost transcendental moments where everything finally fell into place and I could comprehend the full power of the lambda calculus. Wonderful, but not particularly useful.
http://www.cs.chalmers.se/Cs/Grundutb/Kurser/afp/lectures.ht...