Welcome, guest | Sign In | My Account | Store | Cart

The Y combinator is a famous higher order function used to implement recursion on anonymous functions i.e. lambda expressions. Y combinators have the fixed point property which is formally expressed by the relation Y(f) = f(Y(f)).

Python, 55 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55``` ```''' Implementation of the fixed point combinator Y. ----------------------------------------------- The Y combinator is a higher order function that suffices following relation: Y(F) = F(Y(F)) From the fixed point property we can get an idea on how to implement a recursive anonymous function. The function F passed to Y has to be a function that takes a single function argument f and produces another function g ( i.e. Y(F) ). Suppose g calls f again. In a simple case where g takes also only one argument we can write: g = lambda n: ... f( ... n ) A concrete example of g we use to proceed the discussion is: g = lambda n: (1 if n<2 else n*f(n-1)) If g is returned by F(f) we can write: F = lambda f: lambda n: (1 if n<2 else n*f(n-1)) Now we call F passing Y(F): Y(F) = F(Y(F)) = lambda n: (1 if n<2 else n*Y(F)(n-1)) Finally we state: Y(F)(k) = (1 if k<2 else k*Y(F)(k-1)) ''' Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg))) # # Examples # # 1. factorial fac = lambda f: lambda n: (1 if n<2 else n*f(n-1)) assert Y(fac)(7) == 5040 # 2. quicksort qsort = lambda h: lambda lst: (lst if len(lst)<=1 else ( h([item for item in lst if itemlst]))) assert Y(qsort)([2,4,2,7,1,8]) == [1, 2, 2, 4, 7, 8] ```

A more thorough discussion of fixed point combinators can be found here:

http://en.wikipedia.org/wiki/Fixed_point_combinator Created by kay schluehr on Sun, 20 Jul 2008 (MIT)

### Required Modules

• (none specified)