wake-up-neo.com

Kann sich eine Lambda-Funktion in Python rekursiv aufrufen?

Eine reguläre Funktion kann einen Aufruf an sich in ihrer Definition enthalten, kein Problem. Ich kann nicht herausfinden, wie ich es mit einer Lambda-Funktion mache, obwohl die Lambda-Funktion keinen Namen hat, auf den sie zurückgreifen kann. Gibt es eine Möglichkeit, dies zu tun? Wie?

61
dsimard

Die einzige Möglichkeit, die ich mir vorstellen kann, besteht darin, der Funktion einen Namen zu geben:

fact = lambda x: 1 if x == 0 else x * fact(x-1)

oder alternativ für frühere Versionen von Python:

fact = lambda x: x == 0 and 1 or x * fact(x-1)

Update : Mit den Ideen der anderen Antworten konnte ich die faktorielle Funktion zu einem einzigen unbenannten Lambda zusammenfügen:

>>> map(lambda n: (lambda f, *a: f(f, *a))(lambda rec, n: 1 if n == 0 else n*rec(rec, n-1), n), range(10))
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

So ist es möglich, aber nicht wirklich zu empfehlen!

63
Greg Hewgill

ohne reduzierte, map, benannte Lambdas oder Python-Interna:

(lambda a:lambda v:a(a,v))(lambda s,x:1 if x==0 else x*s(s,x-1))(10)
45
Hugo Walter

Sie können es nicht direkt tun, weil es keinen Namen hat. Mit einer Hilfsfunktion wie dem Y-Kombinator, auf den Lemmy verwiesen hat, können Sie eine Rekursion erstellen, indem Sie die Funktion als Parameter an sich selbst übergeben (so seltsam das klingt):

# helper function
def recursive(f, *p, **kw):
   return f(f, *p, **kw)

def fib(n):
   # The rec parameter will be the lambda function itself
   return recursive((lambda rec, n: rec(rec, n-1) + rec(rec, n-2) if n>1 else 1), n)

# using map since we already started to do black functional programming magic
print map(fib, range(10))

Dies gibt die ersten zehn Fibonacci-Zahlen aus: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

23
sth

Im Gegensatz zu dem, was etw gesagt hat, können Sie dies direkt tun.

(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f: (lambda i: 1 if (i == 0) else i * f(i - 1)))(n)

Der erste Teil ist der Festkomma-KombinatorY, der die Rekursion im Lambda-Kalkül erleichtert

Y = (lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))

der zweite Teil ist die rekursiv definierte faktorielle Funktion fact

fact = (lambda f: (lambda i: 1 if (i == 0) else i * f(i - 1)))

Y wird auf fact angewendet, um einen anderen Lambda-Ausdruck zu bilden

F = Y(fact)

was auf den dritten Teil angewendet wird, n, der zur n-ten Fakultät führt

>>> n = 5
>>> F(n)
120

oder gleichwertig

>>> (lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f: (lambda i: 1 if (i == 0) else i * f(i - 1)))(5)
120

Wenn Sie jedoch fibs gegenüber facts vorziehen, können Sie dies auch mit demselben Kombinator tun

>>> (lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f: (lambda i: f(i - 1) + f(i - 2) if i > 1 else 1))(5)
8
22
Nux

Ja. Ich habe zwei Möglichkeiten, es zu tun, und eine wurde bereits abgedeckt. Dies ist mein bevorzugter Weg.

(lambda v: (lambda n: n * __import__('types').FunctionType(
        __import__('inspect').stack()[0][0].f_code, 
        dict(__import__=__import__, dict=dict)
    )(n - 1) if n > 1 else 1)(v))(5)
11
habnabit

Ich habe Python noch nie benutzt, aber das ist wahrscheinlich das, wonach Sie suchen.

6
Lemmy

Diese Antwort ist ziemlich einfach. Es ist etwas einfacher als die Antwort von Hugo Walter:

>>> (lambda f: f(f))(lambda f, i=0: (i < 10)and f(f, i + 1)or i)
10
>>>

Hugo Walters Antwort:

(lambda a:lambda v:a(a,v))(lambda s,x:1 if x==0 else x*s(s,x-1))(10)
2
motoku
def recursive(def_fun):
    def wrapper(*p, **kw):
        fi = lambda *p, **kw: def_fun(fi, *p, **kw)
        return def_fun(fi, *p, **kw)

    return wrapper


factorial = recursive(lambda f, n: 1 if n < 2 else n * f(n - 1))
print(factorial(10))

fibonaci = recursive(lambda f, n: f(n - 1) + f(n - 2) if n > 1 else 1)
print(fibonaci(10))

Hoffe, es wäre jemandem hilfreich.

1
Sergey Luchko

Nun, nicht gerade reine Lambda-Rekursion, aber sie ist an Orten anwendbar, an denen Sie nur Lambdas verwenden können, z. reduzieren, kartieren und listen sie verständnisse oder andere lambdas auf. Der Trick besteht darin, vom Listenverständnis und dem Namensumfang von Python zu profitieren. Das folgende Beispiel durchsucht das Wörterbuch anhand der angegebenen Schlüsselkette.

>>> data = {'John': {'age': 33}, 'Kate': {'age': 32}}
>>> [fn(data, ['John', 'age']) for fn in [lambda d, keys: None if d is None or type(d) is not dict or len(keys) < 1 or keys[0] not in d else (d[keys[0]] if len(keys) == 1 else fn(d[keys[0]], keys[1:]))]][0]
33

Das Lambda verwendet seinen im Listenverständnisausdruck (fn) definierten Namen. Das Beispiel ist ziemlich kompliziert, zeigt aber das Konzept.

0
ahanin

Dazu können wir Festkomma-Kombinatoren , speziell Z-Kombinator verwenden, da er in strengen Sprachen arbeitet, die auch als eifrige Sprachen bezeichnet werden:

const Z = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)))

fact-Funktion definieren und ändern:

1. const fact n = n === 0 ? 1 : n * fact(n - 1)
2. const fact = n => n === 0 ? 1 : n * fact(n - 1)
3. const _fact = (fact => n => n === 0 ? 1 : n * fact(n - 1))

Beachte das:

tatsache === Z (_Fakt)

Und benutze es:

const Z = f => (x => f(v => x(x)(v)))(x => f(v => x(x)(v)));

const _fact = f => n => n === 0 ? 1 : n * f(n - 1);
const fact = Z(_fact);

console.log(fact(5)); //120

Siehe auch: Festkomma-Kombinatoren in JavaScript: Rekursive Funktionen merken

0
kogoia

Lambda kann in Python leicht rekursive Funktionen ersetzen:

Zum Beispiel dieses grundlegende compound_interest:

def interest(amount, rate, period):
    if period == 0: 
        return amount
    else:
        return interest(amount * rate, rate, period - 1)

kann ersetzt werden durch:

lambda_interest = lambda a,r,p: a if p == 0 else lambda_interest(a * r, r, p - 1)

oder für mehr Sichtbarkeit:

lambda_interest = lambda amount, rate, period: \
amount if period == 0 else \
lambda_interest(amount * rate, rate, period - 1)

VERWENDUNGSZWECK:

print(interest(10000, 1.1, 3))
print(lambda_interest(10000, 1.1, 3))

Ausgabe:

13310.0
13310.0
0
Kevin Sabbe