Recursion using the Y – combinator

The reason for writing this article was the desire to understand how the Y-combinator works.

So that the brains do not rust and work like a clock, I try to try new and unusual things.
For the sake of interest, I compiled Lua 5.x under DOS, there were no problems with this, but when checking Lua on its standard tests, I found the factorial calculation code, which I did not understand.
But he clearly realized that this is something related to functional programming.


')
As a result, I found an article in Wikipedia , an article about practical use in Ruby, and an article about a Y-combinator in Python , which I finally understood at least when analyzing.

Y-combinator allows you to turn an ordinary (including anonymous) function into a recursive one. Its main value is theoretical, to substantiate theories of formal computation, but some find practical applications for it (such a feeling appeared after reading the comments on the aforementioned articles).

From Wikipedia it follows that the Y-combinator is a special case of higher order functions that take the function f as input and return the function g, such that f (g) = g. It may be so, but this definition did not give me any use for understanding ^{[1] [2]} .

Let's try to understand the classic example of factorial how it all works. Python will be used because I am more familiar with it.

In the process of analysis will be used auxiliary function dumb , from which we subsequently get rid of.

def dumb ( ) :
pass

Let's try to convert the next lambda function into a recursive function that calculates the factorial.

test = lambda f: lambda n: 1 if n == 0 else n * f ( n- 1 )

We have already taken a step forward, as test (dumb) (0) == 1 .

Let's try to call test (dumb) (1) . We will get an exception, because the interpreter will not be able to call dumb with argument 0. We can go slyly and make a call to test (test (dumb)) (1) . Having gone this way, we can even reach such a call test (test (test (test (test (test (test (dumb))))))) (6) , which successfully counts factorial up to 6.

Is it possible to make such a call: test (test (...)) (x) , where ... is an infinite number of calls to our test function?
It is possible, and Y-combinator will help us in this.
Here is one of its forms, in which such a call structure is clearly visible:

def Y ( f ) :
return f ( lambda x: Y ( f ) ( x ) )

And, accordingly, the factorial can be defined as:

factorial = Y ( test )

As part of the definition from Wikipedia, it can be said that we received a link to the internal lambda function (this is which lambda n: ... ) and called test with this link.

Another known recursive function can be written as:

fibbonacci = Y ( lambda f: lambda n: 1 if n == 0 or n == 1 else f ( n- 2 ) + f ( n- 1 ) )

Another form of Y-combinator, in which the call structure is effectively hidden:

def Y ( f ) :
def g ( k ) :
return f ( lambda a: ( k ( k ) ) ( a ) )
return g ( g )

Of course, there is no practical value in such a realization of factorial, it is even slower than the usual recursive call. You can sacrifice memory and speed up calculations at the expense of caching. To do this, we need to slightly modify the Y-combinator:

def Ycache ( f, data ) :
def _fn ( x ) :
if x in data:
return data [ x ]
else :
temp = ( f ( lambda x: Ycache ( f, data ) ( x ) )
) ( x )
data [ x ] = temp
return temp
return _fn

And the function of calculating Fibbonacci numbers will look like this:

fibbonacci = Ycache ( test , { } )

The calculation of the 200th Fibbonacci number happens almost instantly, unlike the simple recursive version.

And finally, a little bit exotic: quick sorting ( quick_sort )

qsort = lambda h: lambda lst: ( lst if len ( lst ) < = 1 else (
h ( [ item for item in lst if item < lst [ 0 ] ] ) + \
[ lst [ 0 ] ] * lst. count ( lst [ 0 ] ) + \
h ( [ item for item in lst if item > lst [ 0 ] ] ) ) )

print ( Y ( qsort ) ( [ 1 , 13 , 2 , 12 , 3 , 11 , 4 , 10 , 5 , 9 , 6 , 8 , 7 ] ) )

_________
The text was prepared in Habra Editor
^[1] There is a thought that this is somehow related to the fact that for some class of functions f (f (f (f (f (f (f (f (f (f (... f (x)))))) ))))) will converge to the value of y , such that f (y) = y .
^[2] In the Wikipedia discussion, they wrote that the Y-combinator is not obliged to solve algorithmically unsolvable problems, but simply to provide its behavior on a certain class of functions.