How to make a sum in Lambda with recursive logic using successor and predecessor?

6

I'm trying to mount a Sum with recursion logic using only successor and predecessor in Lambda. But they are not getting ...

In case:

suc = λx.x+1

ant = λx.x-1

I've already done something like this:

{λx.[λy.(x-1)+(y+1)][λy.(x-1)+(y+1)]}

But I do not know if this is right ... There is no error code, because I did not implement it, I'm trying to set up the logic.

    
asked by anonymous 23.11.2015 / 13:37

1 answer

2

According to the SO response in English:
link

You can assemble a logical sum (or other algorithms) with recursion using functions lambda in Python.

An important point about recursive functions is that they must have a stop condition, that is, at some point, the algorithm must return to avoid an infinite looping (references at the end of the response).

According to the answer above, there are several ways to create these expressions.

The examples below, make (recursively) the calculation:

x=10
soma = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55

Examples:

a) Name the function lambda created (easiest):

soma = lambda x: 1 if x == 1 else x+soma(x-1)

Result:

>>> soma = lambda x: 1 if x == 1 else x+soma(x-1)
>>> soma(10)
55

The variable soma receives the value of an anonymous function ( lambda ) and returns if the function parameter is 1 (stop condition).

If the value is greater than 1 , it adds the value of the parameter x to the result of a recursive call with parameter x-1 , made through the reference stored in the soma variable.

b) Using an auxiliary function:

def soma(f, *p, **kw):
    return f(f, *p, **kw)

soma( (lambda fr, x: 1 if x == 1 else x + fr(fr, x-1)), 10 )

Result:

>>> soma( (lambda fr, x: 1 if x == 1 else x + fr(fr, x-1)), 10 )
55

This type of function is known as Fixed-point merge (see references) or Lemmy's Y-combinator .

The auxiliary function soma receives 3 parameters:

  • f - will receive an anonymous function

  • *p - gets a list of positional parameters

  • **kw - gets a list of named parameters

See: Keyword Arguments Python Documentation

When calling the function soma , the first parameter entered is a lambda function that receives 2 parameters: the function itself (in fr ) and the value 10 .

The recursive call occurs in: x + fr(fr, x-1) and later in return f(f, *p, **kw) .

The stop condition is the same as the previous one.

c) Only with anonymous functions (more complex):

(lambda f1: lambda v1: f1(f1, v1))(lambda f, x: 1 if x == 1 else x+f(f, x-1))(10)

Result:

>>> (lambda f1: lambda v1: f1(f1, v1))(lambda f, x: 1 if x == 1 else x+f(f, x-1))(10)
55

This function is also a variation of Lemmy's Y-combinator .

Dividing the command line into 3 parts:

1) The first part is equivalent to the auxiliary function of the example ( b ) above.

The parameter f1 receives the function of item 2 (below) and the parameter v1 will receive the value 10 , from the recursive call f1(f1, v1) :

(lambda f1: lambda v1: f1(f1, v1))

2) The second part is the function that performs the calculation:

(lambda f, x: 1 if x == 1 else x+f(f, x-1))

3) The third part is value 10, which will be sent to the parameter v1 , and later to x :

(10)

To facilitate understanding of this example, the command is equivalent to the example ( a ) as follows:

f1 = lambda f, x: 1 if x == 1 else x+f(f, x-1)
v1 = 10
f1(f1, v1)

For tests, Python 2.7.11 was used.

Important: According to references, this type of code has academic utility and is probably not recommended for use in production environments.

References:

Wikibooks - Algorithms and Data Structures / Recursion

Wikipedia - Lambda Calculation

Wikipedia - Fixed Point Combiner

    
02.02.2016 / 03:38