import std.algorithm; import std.range; auto factorial = Y((int delegate(int) self) => (int n) => 0 == n ? 1 : n * self(n - 1)); auto ackermann = Y((ulong delegate(ulong, ulong) self) => (ulong m, ulong n) => (!m && n)? (n+1) : (m && !n)? self(m-1, 1) : self(m-1, self(m, n-1))); auto qsort = Y((int[] delegate(int[]) self) => (int[] arr) => arr.length? self(arr.filter!(a => a < arr[0]).array) ~ arr[0] ~ self(arr.filter!(a => a > arr[0]).array) : []); assert(factorial(6) == 720); assert(ackermann(3, 5) == 253); assert(qsort([8, 5, 10, 2, 16, 9, 1, 100, 3]) == [1, 2, 3, 5, 8, 9, 10, 16, 100]);
Y combinator Description: We're all familiar with the idea of a function as something that takes some input value and returns some output value. Say, the function for squaring numbers:
The fixed points of a function are any input values for which f(x) is equal to x. So, the fixed points of f(x) = x*x are 0 and 1.
Now, we have things called higher-order functions. These are functions that take another function as input, or return a function as output, or both.
The fixed point of a higher-order function f is another function p such that f(p) = p. It may be more helpful to think in terms of functions actually being executed. The previous statement is equivalent to the statement that f(p)(x) = p(x) for all values of x.
Y (the Y combinator) is a special function that returns the fixed points of higher-order functions, that is to say:
Y combinator is commonly use to allow anonymous recursion without assuming your host language supports it.