HOWTO zur funktionalen Programmierung¶

In diesem Dokument gehen wir auf einen Streifzug durch die Eigenschaften von Python, die sich dafür eignen, Programme in funktionalem Stil zu schreiben. Nach einer Einführung in die Begriffe der funktionalen Programmierung sehen wir uns Spracheigenschaften wie Iteratoren und Generatoren sowie die einschlägigen Bibliotheksmodule itertools und functools an.

Einführung¶

Dieser Abschnitt erklärt den Grundbegriff der funktionalen Programmierung, wenn du dich nur für die Eigenschaften der Sprache Python interessierst, springe zum nächsten Abschnitt über Iteratoren.

Programmiersprachen unterstützen das Zerlegen von Problemen auf mehrere verschiedene Weisen:

Die meisten Programmiersprachen sind prozedural: Programme sind Listen von Anweisungen, die dem Rechner sagen, was er mit der Eingabe des Programms tun soll. C, Pascal und sogar Unix-Shells sind prozedurale Sprachen.
In deklarativen Sprachen schreibst du eine Spezifikation, die das zu lösende Problem beschreibt, und die Umsetzung der Sprache findet heraus, wie die Berechnung effizient auszuführen ist. SQL ist die deklarative Sprache, die dir am ehesten vertraut sein dürfte. Eine SQL-Abfrage beschreibt den Datensatz, den du abrufen willst, und die SQL-Maschine entscheidet, ob sie Tabellen durchsucht oder Indizes verwendet, welche Teilklauseln zuerst auszuführen sind usw.
Objektorientierte Programme bearbeiten Sammlungen von Objekten. Objekte haben einen inneren Zustand und unterstützen Methoden, die diesen inneren Zustand auf irgendeine Weise abfragen oder verändern. Smalltalk und Java sind objektorientierte Sprachen. C++ und Python sind Sprachen, die objektorientierte Programmierung unterstützen, die Verwendung objektorientierter Eigenschaften aber nicht erzwingen.
Funktionale Programmierung zerlegt ein Problem in eine Menge von Funktionen. Im Idealfall nehmen Funktionen nur Eingaben und erzeugen Ausgaben und haben keinen inneren Zustand, der die für eine gegebene Eingabe erzeugte Ausgabe beeinflusst. Bekannte funktionale Sprachen sind unter anderem die ML-Familie (Standard ML, OCaml und weitere Varianten) und Haskell.

Die Entwerfer mancher Computersprachen entscheiden sich, einen bestimmten Programmieransatz in den Mittelpunkt zu stellen. Das macht es oft schwierig, Programme zu schreiben, die einen anderen Ansatz verwenden. Andere Sprachen sind Multiparadigmen-Sprachen, die mehrere verschiedene Ansätze unterstützen. Lisp, C++ und Python sind Multiparadigmen-Sprachen. Du kannst in all diesen Sprachen Programme oder Bibliotheken schreiben, die größtenteils prozedural, objektorientiert oder funktional sind. In einem großen Programm können verschiedene Teile mit verschiedenen Ansätzen geschrieben sein. Die Benutzeroberfläche könnte zum Beispiel objektorientiert sein, während die Verarbeitungslogik prozedural oder funktional ist.

In einem funktionalen Programm fließt die Eingabe durch eine Menge von Funktionen. Jede Funktion arbeitet auf ihrer Eingabe und erzeugt eine Ausgabe. Der funktionale Stil hält von Funktionen mit Nebenwirkungen ab, die inneren Zustand verändern oder andere Änderungen vornehmen, die im Rückgabewert der Funktion nicht sichtbar sind. Funktionen, die überhaupt keine Nebenwirkungen haben, nennt man rein funktional. Nebenwirkungen zu vermeiden bedeutet, keine Datenstrukturen zu verwenden, die während des Programmlaufs aktualisiert werden. Die Ausgabe jeder Funktion darf nur von ihrer Eingabe abhängen.

Manche Sprachen nehmen es mit der Reinheit sehr genau und haben nicht einmal Zuweisungsanweisungen wie a=3 oder c = a + b, aber es ist schwierig, alle Nebenwirkungen zu vermeiden, etwa das Ausgeben auf dem Bildschirm oder das Schreiben in eine Datei. Ein weiteres Beispiel ist ein Aufruf der Funktion print() oder time.sleep(), von denen keine einen nützlichen Wert zurückgibt. Beide werden nur wegen ihrer Nebenwirkungen aufgerufen: etwas Text auf den Bildschirm zu senden oder die Ausführung eine Sekunde anzuhalten.

Python-Programme, die in funktionalem Stil geschrieben sind, gehen üblicherweise nicht so weit, alle Ein- und Ausgaben oder alle Zuweisungen zu vermeiden. Sie bieten vielmehr eine funktional erscheinende Schnittstelle, verwenden intern aber nicht funktionale Mittel. So verwendet die Umsetzung einer Funktion zum Beispiel weiterhin Zuweisungen an lokale Variablen, verändert aber keine globalen Variablen und hat keine anderen Nebenwirkungen.

Funktionale Programmierung lässt sich als Gegenteil objektorientierter Programmierung auffassen. Objekte sind kleine Kapseln, die etwas inneren Zustand zusammen mit einer Sammlung von Methodenaufrufen enthalten, mit denen sich dieser Zustand verändern lässt, und Programme bestehen darin, die richtige Menge von Zustandsänderungen vorzunehmen. Funktionale Programmierung will Zustandsänderungen so weit wie möglich vermeiden und arbeitet mit Daten, die zwischen Funktionen fließen. In Python könntest du die beiden Ansätze verbinden, indem du Funktionen schreibst, die Instanzen nehmen und zurückgeben, die Objekte in deiner Anwendung darstellen (E-Mail-Nachrichten, Transaktionen usw.).

Funktionaler Entwurf mag wie eine sonderbare Einschränkung erscheinen. Warum solltest du Objekte und Nebenwirkungen vermeiden? Der funktionale Stil hat theoretische und praktische Vorteile:

Formale Beweisbarkeit.
Modularität.
Zusammensetzbarkeit.
Leichteres Debuggen und Testen.

Formale Beweisbarkeit¶

Ein theoretischer Vorteil ist, dass es leichter ist, einen mathematischen Beweis dafür zu führen, dass ein funktionales Programm korrekt ist.

Forscher interessieren sich seit langem für Wege, die Korrektheit von Programmen mathematisch zu beweisen. Das unterscheidet sich davon, ein Programm mit zahlreichen Eingaben zu testen und daraus zu schließen, dass seine Ausgabe üblicherweise korrekt ist, oder den Quellcode eines Programms zu lesen und daraus zu schließen, dass der Code richtig aussieht. Das Ziel ist vielmehr ein strenger Beweis, dass ein Programm für alle möglichen Eingaben das richtige Ergebnis erzeugt.

Die Technik, mit der die Korrektheit von Programmen bewiesen wird, besteht darin, Invarianten aufzuschreiben – Eigenschaften der Eingabedaten und der Variablen des Programms, die immer wahr sind. Für jede Codezeile zeigst du dann: Wenn die Invarianten X und Y vor der Ausführung der Zeile wahr sind, sind die etwas anderen Invarianten X‘ und Y‘ nach der Ausführung der Zeile wahr. Das setzt sich fort, bis du das Ende des Programms erreichst. An diesem Punkt sollten die Invarianten zu den gewünschten Bedingungen für die Ausgabe des Programms passen.

Dass funktionale Programmierung Zuweisungen vermeidet, kam auf, weil Zuweisungen mit dieser Technik schwer zu behandeln sind; Zuweisungen können Invarianten brechen, die vor der Zuweisung wahr waren, ohne neue Invarianten zu erzeugen, die sich weitertragen lassen.

Die Korrektheit von Programmen zu beweisen ist leider größtenteils unpraktikabel und für Python-Software nicht einschlägig. Selbst triviale Programme brauchen Beweise, die mehrere Seiten lang sind. Der Korrektheitsbeweis für ein mittelmäßig kompliziertes Programm wäre riesig, und von den Programmen, die du täglich verwendest (der Python-Interpreter, dein XML-Parser, dein Webbrowser), ließen sich wenige oder keine als korrekt beweisen. Selbst wenn du einen Beweis aufschreiben oder erzeugen würdest, bliebe die Frage, den Beweis zu prüfen. Vielleicht steckt ein Fehler darin, und du glaubst fälschlich, das Programm als korrekt bewiesen zu haben.

Modularität¶

Ein praktischerer Vorteil funktionaler Programmierung ist, dass sie dich zwingt, dein Problem in kleine Stücke zu zerlegen. Programme werden dadurch modularer. Es ist leichter, eine kleine Funktion zu beschreiben und zu schreiben, die eine Sache tut, als eine große Funktion, die eine komplizierte Umformung ausführt. Kleine Funktionen sind außerdem leichter zu lesen und auf Fehler zu prüfen.

Leichteres Debuggen und Testen¶

Ein Programm im funktionalen Stil zu testen und zu debuggen ist leichter.

Das Debuggen wird einfacher, weil Funktionen im Allgemeinen klein und klar beschrieben sind. Wenn ein Programm nicht funktioniert, ist jede Funktion ein Schnittstellenpunkt, an dem du prüfen kannst, ob die Daten korrekt sind. Du kannst dir die Zwischeneingaben und -ausgaben ansehen, um die Funktion, die für einen Fehler verantwortlich ist, schnell einzugrenzen.

Das Testen ist leichter, weil jede Funktion ein möglicher Gegenstand eines Unit-Tests ist. Funktionen hängen nicht von Systemzustand ab, der vor einem Testlauf nachgebildet werden muss. Du musst stattdessen nur die richtige Eingabe erzeugen und dann prüfen, ob die Ausgabe den Erwartungen entspricht.

Zusammensetzbarkeit¶

Während du an einem Programm im funktionalen Stil arbeitest, schreibst du eine Reihe von Funktionen mit unterschiedlichen Eingaben und Ausgaben. Manche dieser Funktionen sind unvermeidlich auf eine bestimmte Anwendung zugeschnitten, andere aber sind in einer großen Vielfalt von Programmen nützlich. So lassen sich zum Beispiel eine Funktion, die einen Verzeichnispfad nimmt und alle XML-Dateien in diesem Verzeichnis zurückgibt, oder eine Funktion, die einen Dateinamen nimmt und deren Inhalt zurückgibt, in vielen verschiedenen Lagen einsetzen.

Mit der Zeit bildet sich eine persönliche Bibliothek von Hilfsmitteln. Oft setzt du neue Programme zusammen, indem du bestehende Funktionen neu anordnest und ein paar Funktionen schreibst, die auf die aktuelle Aufgabe zugeschnitten sind.

Iteratoren¶

Ich beginne mit einer Eigenschaft der Sprache Python, die eine wichtige Grundlage zum Schreiben von Programmen im funktionalen Stil ist: Iteratoren.

Ein Iterator ist ein Objekt, das einen Datenstrom darstellt. Dieses Objekt gibt die Daten Element für Element zurück. Ein Python-Iterator muss eine Methode namens __next__() unterstützen, die keine Argumente nimmt und immer das nächste Element des Stroms zurückgibt. Gibt es keine weiteren Elemente im Strom, muss __next__() die Ausnahme StopIteration auslösen. Iteratoren müssen aber nicht endlich sein. Es ist völlig vernünftig, einen Iterator zu schreiben, der einen unendlichen Datenstrom erzeugt.

Die integrierte Funktion iter() nimmt ein beliebiges Objekt und versucht, einen Iterator zurückzugeben, der den Inhalt beziehungsweise die Elemente des Objekts zurückgibt. Sie löst einen TypeError aus, wenn das Objekt Iteration nicht unterstützt. Mehrere der integrierten Datentypen von Python unterstützen Iteration, am häufigsten Listen und Wörterbücher. Ein Objekt heißt iterierbar, wenn du einen Iterator dafür bekommen kannst.

Du kannst mit der Iterationsschnittstelle von Hand experimentieren:

>>> L = [1, 2, 3]
>>> it = iter(L)
>>> it
<...iterator object at ...>
>>> it.__next__()  # same as next(it)
1
>>> next(it)
2
>>> next(it)
3
>>> next(it)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>

Python erwartet iterierbare Objekte in mehreren verschiedenen Zusammenhängen, am wichtigsten in der for-Anweisung. In der Anweisung for X in Y muss Y ein Iterator oder ein Objekt sein, für das iter() einen Iterator erzeugen kann. Diese zwei Anweisungen sind gleichwertig:

for i in iter(obj):
    print(i)

for i in obj:
    print(i)

Iteratoren lassen sich mit den Konstruktorfunktionen list() oder tuple() zu Listen oder Tupeln verfestigen:

>>> L = [1, 2, 3]
>>> iterator = iter(L)
>>> t = tuple(iterator)
>>> t
(1, 2, 3)

Das Entpacken von Sequenzen unterstützt ebenfalls Iteratoren: Wenn du weißt, dass ein Iterator N Elemente zurückgibt, kannst du sie in ein N-Tupel entpacken:

>>> L = [1, 2, 3]
>>> iterator = iter(L)
>>> a, b, c = iterator
>>> a, b, c
(1, 2, 3)

Integrierte Funktionen wie max() und min() können ein einzelnes Iterator-Argument nehmen und geben das größte beziehungsweise kleinste Element zurück. Die Operatoren "in" und "not in" unterstützen ebenfalls Iteratoren: X in iterator ist wahr, wenn X im Strom gefunden wird, den der Iterator zurückgibt. Du läufst in offensichtliche Probleme, wenn der Iterator unendlich ist: max() und min() kehren nie zurück, und wenn das Element X nie im Strom auftaucht, kehren auch die Operatoren "in" und "not in" nicht zurück.

Beachte, dass du in einem Iterator nur vorwärts gehen kannst. Es gibt keinen Weg, das vorherige Element zu bekommen, den Iterator zurückzusetzen oder eine Kopie davon zu machen. Iterator-Objekte können diese zusätzlichen Fähigkeiten wahlweise bieten, aber das Iterator-Protokoll legt nur die Methode __next__() fest. Funktionen können daher die gesamte Ausgabe des Iterators verbrauchen, und wenn du mit demselben Strom etwas anderes machen musst, musst du einen neuen Iterator erzeugen.

Datentypen, die Iteratoren unterstützen¶

Wir haben schon gesehen, wie Listen und Tupel Iteratoren unterstützen. Tatsächlich unterstützt jeder Sequenztyp von Python, etwa Zeichenketten, automatisch das Erzeugen eines Iterators.

iter() auf einem Wörterbuch aufzurufen gibt einen Iterator zurück, der über die Schlüssel des Wörterbuchs läuft:

>>> m = {'Jan': 1, 'Feb': 2, 'Mar': 3, 'Apr': 4, 'May': 5, 'Jun': 6,
...      'Jul': 7, 'Aug': 8, 'Sep': 9, 'Oct': 10, 'Nov': 11, 'Dec': 12}
>>> for key in m:
...     print(key, m[key])
Jan 1
Feb 2
Mar 3
Apr 4
May 5
Jun 6
Jul 7
Aug 8
Sep 9
Oct 10
Nov 11
Dec 12

Beachte, dass ab Python 3.7 die Iterationsreihenfolge von Wörterbüchern garantiert dieselbe ist wie die Einfügereihenfolge. In früheren Versionen war das Verhalten nicht festgelegt und konnte sich zwischen Umsetzungen unterscheiden.

iter() auf ein Wörterbuch anzuwenden läuft immer über die Schlüssel, aber Wörterbücher haben Methoden, die andere Iteratoren zurückgeben. Wenn du über Werte oder Schlüssel-Wert-Paare iterieren willst, kannst du ausdrücklich die Methoden values() oder items() aufrufen, um einen passenden Iterator zu bekommen.

Der Konstruktor dict() kann einen Iterator annehmen, der einen endlichen Strom von (key, value)-Tupeln zurückgibt:

>>> L = [('Italy', 'Rome'), ('France', 'Paris'), ('US', 'Washington DC')]
>>> dict(iter(L))
{'Italy': 'Rome', 'France': 'Paris', 'US': 'Washington DC'}

Dateien unterstützen Iteration ebenfalls, indem die Methode readline() aufgerufen wird, bis es keine weiteren Zeilen in der Datei gibt. Das heißt, dass du jede Zeile einer Datei so lesen kannst:

for line in file:
    # do something for each line
    ...

Mengen können ihren Inhalt aus einem iterierbaren Objekt nehmen und lassen dich über die Elemente der Menge iterieren:

>>> S = {2, 3, 5, 7, 11, 13}
>>> for i in S:
...     print(i)
2
3
5
7
11
13

Generatorausdrücke und Listen-Comprehensions¶

Zwei verbreitete Operationen auf der Ausgabe eines Iterators sind 1) für jedes Element eine Operation auszuführen und 2) eine Teilmenge von Elementen auszuwählen, die eine Bedingung erfüllen. So willst du zum Beispiel, gegeben eine Liste von Zeichenketten, vielleicht aus jeder Zeile den abschließenden Leerraum entfernen oder alle Zeichenketten herausziehen, die eine bestimmte Teilzeichenkette enthalten.

Listen-Comprehensions und Generatorausdrücke (Kurzform: „Listcomps“ und „Genexps“) sind eine knappe Schreibweise für solche Operationen, geborgt von der funktionalen Programmiersprache Haskell (https://www.haskell.org/). Du kannst mit dem folgenden Code allen Leerraum aus einem Strom von Zeichenketten entfernen:

>>> line_list = ['  line 1\n', 'line 2  \n', ' \n', '']

>>> # Generator expression -- returns iterator
>>> stripped_iter = (line.strip() for line in line_list)

>>> # List comprehension -- returns list
>>> stripped_list = [line.strip() for line in line_list]

Du kannst nur bestimmte Elemente auswählen, indem du eine "if"-Bedingung ergänzt:

>>> stripped_list = [line.strip() for line in line_list
...                  if line != ""]

Mit einer Listen-Comprehension bekommst du eine Python-Liste zurück; stripped_list ist eine Liste mit den entstandenen Zeilen und kein Iterator. Generatorausdrücke geben einen Iterator zurück, der die Werte nach Bedarf berechnet und nicht alle Werte auf einmal verfestigen muss. Das heißt, dass Listen-Comprehensions nicht nützlich sind, wenn du mit Iteratoren arbeitest, die einen unendlichen Strom oder eine sehr große Datenmenge zurückgeben. Generatorausdrücke sind in diesen Lagen zu bevorzugen.

Generatorausdrücke sind von runden Klammern („()“) umgeben und Listen-Comprehensions von eckigen Klammern („[]“). Generatorausdrücke haben die Form:

( expression for expr in sequence1
             if condition1
             for expr2 in sequence2
             if condition2
             for expr3 in sequence3
             if condition3
             ...
             for exprN in sequenceN
             if conditionN )

Auch hier sind bei einer Listen-Comprehension nur die äußeren Klammern anders (eckige Klammern anstelle von runden).

Die Elemente der erzeugten Ausgabe sind die aufeinanderfolgenden Werte von expression. Die if-Klauseln sind alle optional. Sind sie vorhanden, wird expression nur dann ausgewertet und dem Ergebnis hinzugefügt, wenn condition wahr ist.

Generatorausdrücke müssen immer innerhalb von Klammern geschrieben werden, aber die Klammern, die einen Funktionsaufruf anzeigen, zählen mit. Wenn du einen Iterator erzeugen willst, der sofort an eine Funktion übergeben wird, kannst du schreiben:

obj_total = sum(obj.count for obj in list_all_objects())

Die for...in-Klauseln enthalten die Sequenzen, über die iteriert wird. Die Sequenzen müssen nicht dieselbe Länge haben, weil von links nach rechts über sie iteriert wird und nicht parallel. Für jedes Element in sequence1 wird sequence2 von Anfang an durchlaufen. sequence3 wird dann für jedes entstehende Elementpaar aus sequence1 und sequence2 durchlaufen.

Anders gesagt entspricht eine Listen-Comprehension oder ein Generatorausdruck dem folgenden Python-Code:

for expr1 in sequence1:
    if not (condition1):
        continue   # Skip this element
    for expr2 in sequence2:
        if not (condition2):
            continue   # Skip this element
        ...
        for exprN in sequenceN:
            if not (conditionN):
                continue   # Skip this element

            # Output the value of
            # the expression.

Das heißt, dass bei mehreren for...in-Klauseln ohne if-Klauseln die Länge der entstehenden Ausgabe dem Produkt der Längen aller Sequenzen entspricht. Wenn du zwei Listen der Länge 3 hast, ist die Ausgabeliste 9 Elemente lang:

>>> seq1 = 'abc'
>>> seq2 = (1, 2, 3)
>>> [(x, y) for x in seq1 for y in seq2]
[('a', 1), ('a', 2), ('a', 3),
 ('b', 1), ('b', 2), ('b', 3),
 ('c', 1), ('c', 2), ('c', 3)]

Um in die Grammatik von Python keine Uneindeutigkeit einzuschleppen, muss expression von Klammern umgeben sein, wenn es ein Tupel erzeugt. Die erste Listen-Comprehension unten ist ein Syntaxfehler, die zweite ist korrekt:

# Syntax error
[x, y for x in seq1 for y in seq2]
# Correct
[(x, y) for x in seq1 for y in seq2]

Generatoren¶

Generatoren sind eine besondere Klasse von Funktionen, die die Aufgabe vereinfachen, Iteratoren zu schreiben. Gewöhnliche Funktionen berechnen einen Wert und geben ihn zurück, aber Generatoren geben einen Iterator zurück, der einen Strom von Werten zurückgibt.

Du bist zweifellos damit vertraut, wie gewöhnliche Funktionsaufrufe in Python oder C funktionieren. Wenn du eine Funktion aufrufst, bekommt sie einen privaten Namensraum, in dem ihre lokalen Variablen entstehen. Erreicht die Funktion eine return-Anweisung, werden die lokalen Variablen zerstört und der Wert an den Aufrufer zurückgegeben. Ein späterer Aufruf derselben Funktion erzeugt einen neuen privaten Namensraum und einen frischen Satz lokaler Variablen. Aber was, wenn die lokalen Variablen beim Verlassen einer Funktion nicht weggeworfen würden? Was, wenn du die Funktion später dort fortsetzen könntest, wo sie aufgehört hat? Genau das bieten Generatoren. Man kann sie sich als fortsetzbare Funktionen vorstellen.

Hier das einfachste Beispiel einer Generatorfunktion:

>>> def generate_ints(N):
...    for i in range(N):
...        yield i

Jede Funktion, die ein Schlüsselwort yield enthält, ist eine Generatorfunktion. Das erkennt der Bytecode-Compiler von Python, der die Funktion daraufhin besonders kompiliert.

Wenn du eine Generatorfunktion aufrufst, gibt sie keinen einzelnen Wert zurück. Sie gibt stattdessen ein Generatorobjekt zurück, das das Iterator-Protokoll unterstützt. Bei der Ausführung des yield-Ausdrucks gibt der Generator den Wert von i aus, ähnlich wie eine return-Anweisung. Der große Unterschied zwischen yield und einer return-Anweisung ist, dass beim Erreichen eines yield der Ausführungszustand des Generators angehalten und die lokalen Variablen erhalten werden. Beim nächsten Aufruf der Methode __next__() des Generators setzt die Funktion ihre Ausführung fort.

Hier eine Beispielverwendung des Generators generate_ints():

>>> gen = generate_ints(3)
>>> gen
<generator object generate_ints at ...>
>>> next(gen)
0
>>> next(gen)
1
>>> next(gen)
2
>>> next(gen)
Traceback (most recent call last):
  File "stdin", line 1, in <module>
  File "stdin", line 2, in generate_ints
StopIteration

Du könntest genauso for i in generate_ints(5) oder a, b, c = generate_ints(3) schreiben.

Innerhalb einer Generatorfunktion führt return value dazu, dass StopIteration(value) aus der Methode __next__() ausgelöst wird. Sobald das geschieht oder das Ende der Funktion erreicht ist, endet die Folge der Werte, und der Generator kann keine weiteren Werte liefern.

Du könntest die Wirkung von Generatoren von Hand erreichen, indem du deine eigene Klasse schreibst und alle lokalen Variablen des Generators als Instanzvariablen speicherst. So ließe sich das Zurückgeben einer Liste von Ganzzahlen zum Beispiel erreichen, indem self.count auf 0 gesetzt wird und die Methode __next__() self.count erhöht und zurückgibt. Für einen mittelmäßig komplizierten Generator kann es allerdings deutlich unübersichtlicher sein, eine entsprechende Klasse zu schreiben.

Die Testsammlung, die zur Bibliothek von Python gehört, Lib/test/test_generators.py, enthält eine Reihe interessanterer Beispiele. Hier ein Generator, der mit rekursiv verwendeten Generatoren einen Baum in symmetrischer Reihenfolge durchläuft.

# A recursive generator that generates Tree leaves in in-order.
def inorder(t):
    if t:
        for x in inorder(t.left):
            yield x

        yield t.label

        for x in inorder(t.right):
            yield x

Zwei weitere Beispiele in test_generators.py erzeugen Lösungen für das N-Damen-Problem (N Damen so auf ein NxN-Schachbrett zu setzen, dass keine Dame eine andere bedroht) und für den Springerzug (einen Weg zu finden, der einen Springer auf jedes Feld eines NxN-Schachbretts bringt, ohne ein Feld zweimal zu besuchen).

Werte in einen Generator hineingeben¶

In Python 2.4 und älter erzeugten Generatoren nur Ausgaben. War der Code eines Generators einmal aufgerufen, um einen Iterator zu erzeugen, gab es keinen Weg, neue Informationen in die Funktion hineinzugeben, wenn ihre Ausführung fortgesetzt wird. Du konntest sich diese Fähigkeit zusammenbasteln, indem du den Generator eine globale Variable ansehen ließest oder ein veränderliches Objekt hineingabst, das Aufrufer dann verändern, aber diese Wege sind unübersichtlich.

In Python 2.5 gibt es einen einfachen Weg, Werte in einen Generator hineinzugeben. yield wurde zu einem Ausdruck, der einen Wert zurückgibt, der sich einer Variablen zuweisen oder anderweitig verarbeiten lässt:

val = (yield i)

Ich empfehle, einen yield-Ausdruck immer in Klammern zu setzen, wenn du mit dem zurückgegebenen Wert etwas machst, wie im obigen Beispiel. Die Klammern sind nicht immer nötig, aber es ist leichter, sie immer zu setzen, als sich merken zu müssen, wann sie gebraucht werden.

(PEP 342 erklärt die genauen Regeln: Ein yield-Ausdruck muss immer eingeklammert sein, außer wenn er als Ausdruck auf der obersten Ebene der rechten Seite einer Zuweisung steht. Das heißt, dass du val = yield i schreiben kannst, bei einer Operation aber Klammern verwenden musst, etwa val = (yield i) + 12.)

Werte werden in einen Generator hineingegeben, indem seine Methode send(value) aufgerufen wird. Diese Methode setzt den Code des Generators fort, und der yield-Ausdruck gibt den angegebenen Wert zurück. Wird die gewöhnliche Methode __next__() aufgerufen, gibt das yield None zurück.

Hier ein einfacher Zähler, der um 1 erhöht und das Ändern des Werts des inneren Zählers erlaubt.

def counter(maximum):
    i = 0
    while i < maximum:
        val = (yield i)
        # If value provided, change counter
        if val is not None:
            i = val
        else:
            i += 1

Und hier ein Beispiel, wie der Zähler geändert wird:

>>> it = counter(10)
>>> next(it)
0
>>> next(it)
1
>>> it.send(8)
8
>>> next(it)
9
>>> next(it)
Traceback (most recent call last):
  File "t.py", line 15, in <module>
    it.next()
StopIteration

Weil yield oft None zurückgibt, solltest du diesen Fall immer prüfen. Verwende seinen Wert nicht einfach in Ausdrücken, sofern du nicht sicher bist, dass die Methode send() die einzige Methode ist, mit der deine Generatorfunktion fortgesetzt wird.

Neben send() gibt es zwei weitere Methoden auf Generatoren:

throw(value) dient dazu, innerhalb des Generators eine Ausnahme auszulösen. Die Ausnahme wird von dem yield-Ausdruck ausgelöst, an dem die Ausführung des Generators angehalten ist.
close() sendet eine GeneratorExit-Ausnahme an den Generator, um die Iteration zu beenden. Beim Empfang dieser Ausnahme muss der Code des Generators entweder GeneratorExit oder StopIteration auslösen. Die Ausnahme zu fangen und irgendetwas anderes zu tun ist unzulässig und löst einen RuntimeError aus. close() wird außerdem von der Speicherbereinigung von Python aufgerufen, wenn der Generator eingesammelt wird.

Wenn du bei einer GeneratorExit Aufräumcode ausführen musst, schlage ich vor, einen try: ... finally:-Block zu verwenden, anstatt GeneratorExit zu fangen.

Die Gesamtwirkung dieser Änderungen ist, Generatoren von einseitigen Erzeugern von Informationen in Erzeuger und Verbraucher zugleich zu verwandeln.

Generatoren werden damit außerdem zu Coroutinen, einer allgemeineren Form von Unterprogrammen. Unterprogramme werden an einer Stelle betreten und an einer anderen verlassen (am Anfang der Funktion und bei einer return-Anweisung), aber Coroutinen lassen sich an vielen verschiedenen Stellen betreten, verlassen und fortsetzen (an den yield-Anweisungen).

Integrierte Funktionen¶

Sehen wir uns die integrierten Funktionen genauer an, die oft mit Iteratoren verwendet werden.

Zwei der integrierten Funktionen von Python, map() und filter(), bilden die Eigenschaften von Generatorausdrücken nach:

map(f, iterA, iterB, ...) gibt einen Iterator über die Sequenz zurück

f(iterA[0], iterB[0]), f(iterA[1], iterB[1]), f(iterA[2], iterB[2]), ....

>>> def upper(s):
...     return s.upper()

>>> list(map(upper, ['sentence', 'fragment']))
['SENTENCE', 'FRAGMENT']
>>> [upper(s) for s in ['sentence', 'fragment']]
['SENTENCE', 'FRAGMENT']

Dieselbe Wirkung lässt sich natürlich mit einer Listen-Comprehension erreichen.

filter(predicate, iter) gibt einen Iterator über alle Sequenzelemente zurück, die eine bestimmte Bedingung erfüllen, und wird von Listen-Comprehensions genauso nachgebildet. Ein Prädikat ist eine Funktion, die den Wahrheitswert einer Bedingung zurückgibt. Zur Verwendung mit filter() muss das Prädikat einen einzelnen Wert nehmen.

>>> def is_even(x):
...     return (x % 2) == 0

>>> list(filter(is_even, range(10)))
[0, 2, 4, 6, 8]

Das lässt sich auch als Listen-Comprehension schreiben:

>>> list(x for x in range(10) if is_even(x))
[0, 2, 4, 6, 8]

enumerate(iter, start=0) zählt die Elemente im iterierbaren Objekt ab und gibt 2-Tupel zurück, die den Zählstand (ab start) und jeweils ein Element enthalten.

>>> for item in enumerate(['subject', 'verb', 'object']):
...     print(item)
(0, 'subject')
(1, 'verb')
(2, 'object')

enumerate() wird oft verwendet, wenn man eine Liste durchläuft und die Indizes festhält, an denen bestimmte Bedingungen erfüllt sind:

f = open('data.txt', 'r')
for i, line in enumerate(f):
    if line.strip() == '':
        print('Blank line at line #%i' % i)

sorted(iterable, key=None, reverse=False) sammelt alle Elemente des iterierbaren Objekts in einer Liste, sortiert die Liste und gibt das sortierte Ergebnis zurück. Die Argumente key und reverse werden an die Methode sort() der gebauten Liste weitergegeben.

>>> import random
>>> # Generate 8 random numbers between [0, 10000)
>>> rand_list = random.sample(range(10000), 8)
>>> rand_list
[769, 7953, 9828, 6431, 8442, 9878, 6213, 2207]
>>> sorted(rand_list)
[769, 2207, 6213, 6431, 7953, 8442, 9828, 9878]
>>> sorted(rand_list, reverse=True)
[9878, 9828, 8442, 7953, 6431, 6213, 2207, 769]

(Eine ausführlichere Erörterung des Sortierens steht unter Sortiertechniken.)

Die integrierten Funktionen any(iter) und all(iter) sehen sich die Wahrheitswerte des Inhalts eines iterierbaren Objekts an. any() gibt True zurück, wenn irgendein Element im iterierbaren Objekt ein wahrer Wert ist, und all() gibt True zurück, wenn alle Elemente wahre Werte sind:

>>> any([0, 1, 0])
True
>>> any([0, 0, 0])
False
>>> any([1, 1, 1])
True
>>> all([0, 1, 0])
False
>>> all([0, 0, 0])
False
>>> all([1, 1, 1])
True

zip(iterA, iterB, ...) nimmt aus jedem iterierbaren Objekt ein Element und gibt sie in einem Tupel zurück:

zip(['a', 'b', 'c'], (1, 2, 3)) =>
  ('a', 1), ('b', 2), ('c', 3)

Es baut keine Liste im Speicher auf und erschöpft nicht alle Eingabe-Iteratoren, bevor es zurückkehrt. Die Tupel werden stattdessen nur dann gebaut und zurückgegeben, wenn sie angefordert werden. (Der Fachbegriff für dieses Verhalten ist verzögerte Auswertung.)

Dieser Iterator ist dafür gedacht, mit iterierbaren Objekten verwendet zu werden, die alle dieselbe Länge haben. Haben die iterierbaren Objekte unterschiedliche Längen, hat der entstehende Strom dieselbe Länge wie das kürzeste iterierbare Objekt.

zip(['a', 'b'], (1, 2, 3)) =>
  ('a', 1), ('b', 2)

Du solltest das allerdings vermeiden, weil aus den längeren Iteratoren ein Element genommen und verworfen werden kann. Das heißt, dass du die Iteratoren nicht weiterverwenden kannst, weil du Gefahr läufst, ein verworfenes Element zu überspringen.

Das Modul itertools¶

Das Modul itertools enthält eine Reihe häufig verwendeter Iteratoren sowie Funktionen, um mehrere Iteratoren zu verbinden. Dieser Abschnitt stellt den Inhalt des Moduls anhand kleiner Beispiele vor.

Die Funktionen des Moduls fallen in einige weite Klassen:

Funktionen, die auf Grundlage eines bestehenden Iterators einen neuen Iterator erzeugen.
Funktionen, die die Elemente eines Iterators als Funktionsargumente behandeln.
Funktionen, die Teile der Ausgabe eines Iterators auswählen.
Eine Funktion, die die Ausgabe eines Iterators gruppiert.

Neue Iteratoren erzeugen¶

itertools.count(start, step) gibt einen unendlichen Strom gleichmäßig verteilter Werte zurück. Du kannst wahlweise die Startzahl angeben, die standardmäßig 0 ist, und den Abstand zwischen den Zahlen, der standardmäßig 1 ist:

itertools.count() =>
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
itertools.count(10) =>
  10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...
itertools.count(10, 5) =>
  10, 15, 20, 25, 30, 35, 40, 45, 50, 55, ...

itertools.cycle(iter) speichert eine Kopie des Inhalts eines übergebenen iterierbaren Objekts und gibt einen neuen Iterator zurück, der seine Elemente vom ersten bis zum letzten zurückgibt. Der neue Iterator wiederholt diese Elemente unendlich.

itertools.cycle([1, 2, 3, 4, 5]) =>
  1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...

itertools.repeat(elem, [n]) gibt das übergebene Element n-mal zurück oder endlos, wenn n nicht angegeben ist.

itertools.repeat('abc') =>
  abc, abc, abc, abc, abc, abc, abc, abc, abc, abc, ...
itertools.repeat('abc', 5) =>
  abc, abc, abc, abc, abc

itertools.chain(iterA, iterB, ...) nimmt eine beliebige Zahl iterierbarer Objekte als Eingabe und gibt alle Elemente des ersten Iterators zurück, dann alle Elemente des zweiten und so weiter, bis alle iterierbaren Objekte erschöpft sind.

itertools.chain(['a', 'b', 'c'], (1, 2, 3)) =>
  a, b, c, 1, 2, 3

itertools.islice(iter, [start], stop, [step]) gibt einen Strom zurück, der ein Abschnitt des Iterators ist. Mit einem einzelnen Argument stop gibt es die ersten stop Elemente zurück. Gibst du einen Startindex an, bekommst du stop-start Elemente, und gibst du einen Wert für step an, werden Elemente entsprechend übersprungen. Anders als beim Abschneiden von Zeichenketten und Listen in Python kannst du für start, stop oder step keine negativen Werte verwenden.

itertools.islice(range(10), 8) =>
  0, 1, 2, 3, 4, 5, 6, 7
itertools.islice(range(10), 2, 8) =>
  2, 3, 4, 5, 6, 7
itertools.islice(range(10), 2, 8, 2) =>
  2, 4, 6

itertools.tee(iter, [n]) vervielfältigt einen Iterator. Es gibt n unabhängige Iteratoren zurück, die alle den Inhalt des Quell-Iterators zurückgeben. Gibst du keinen Wert für n an, ist die Vorgabe 2. Iteratoren zu vervielfältigen erfordert, einen Teil des Inhalts des Quell-Iterators zu speichern. Das kann also erheblich Speicher verbrauchen, wenn der Iterator groß ist und einer der neuen Iteratoren stärker verbraucht wird als die anderen.

itertools.tee( itertools.count() ) =>
   iterA, iterB

where iterA ->
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

and   iterB ->
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...

Funktionen auf Elemente anwenden¶

Das Modul operator enthält eine Reihe von Funktionen, die den Operatoren von Python entsprechen. Beispiele sind operator.add(a, b) (addiert zwei Werte), operator.ne(a, b) (dasselbe wie a != b) und operator.attrgetter('id') (gibt ein aufrufbares Objekt zurück, das das Attribut .id holt).

itertools.starmap(func, iter) geht davon aus, dass das iterierbare Objekt einen Strom von Tupeln zurückgibt, und ruft func mit diesen Tupeln als Argumenten auf:

itertools.starmap(os.path.join,
                  [('/bin', 'python'), ('/usr', 'bin', 'java'),
                   ('/usr', 'bin', 'perl'), ('/usr', 'bin', 'ruby')])
=>
  /bin/python, /usr/bin/java, /usr/bin/perl, /usr/bin/ruby

Elemente auswählen¶

Eine weitere Gruppe von Funktionen wählt anhand eines Prädikats eine Teilmenge der Elemente eines Iterators aus.

itertools.filterfalse(predicate, iter) ist das Gegenteil von filter() und gibt alle Elemente zurück, für die das Prädikat falsch zurückgibt:

itertools.filterfalse(is_even, itertools.count()) =>
  1, 3, 5, 7, 9, 11, 13, 15, ...

itertools.takewhile(predicate, iter) gibt Elemente zurück, solange das Prädikat wahr zurückgibt. Sobald das Prädikat falsch zurückgibt, zeigt der Iterator das Ende seiner Ergebnisse an.

def less_than_10(x):
    return x < 10

itertools.takewhile(less_than_10, itertools.count()) =>
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9

itertools.takewhile(is_even, itertools.count()) =>
  0

itertools.dropwhile(predicate, iter) verwirft Elemente, solange das Prädikat wahr zurückgibt, und gibt dann die restlichen Ergebnisse des iterierbaren Objekts zurück.

itertools.dropwhile(less_than_10, itertools.count()) =>
  10, 11, 12, 13, 14, 15, 16, 17, 18, 19, ...

itertools.dropwhile(is_even, itertools.count()) =>
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

itertools.compress(data, selectors) nimmt zwei Iteratoren und gibt nur jene Elemente von data zurück, für die das entsprechende Element von selectors wahr ist. Es hält an, sobald einer der beiden erschöpft ist:

itertools.compress([1, 2, 3, 4, 5], [True, True, False, False, True]) =>
   1, 2, 5

Kombinatorische Funktionen¶

itertools.combinations(iterable, r) gibt einen Iterator zurück, der alle möglichen r-Tupel-Kombinationen der in iterable enthaltenen Elemente liefert.

itertools.combinations([1, 2, 3, 4, 5], 2) =>
  (1, 2), (1, 3), (1, 4), (1, 5),
  (2, 3), (2, 4), (2, 5),
  (3, 4), (3, 5),
  (4, 5)

itertools.combinations([1, 2, 3, 4, 5], 3) =>
  (1, 2, 3), (1, 2, 4), (1, 2, 5), (1, 3, 4), (1, 3, 5), (1, 4, 5),
  (2, 3, 4), (2, 3, 5), (2, 4, 5),
  (3, 4, 5)

Die Elemente innerhalb jedes Tupels bleiben in derselben Reihenfolge, in der iterable sie zurückgegeben hat. So steht in den obigen Beispielen die Zahl 1 zum Beispiel immer vor 2, 3, 4 oder 5. Eine ähnliche Funktion, itertools.permutations(iterable, r=None), hebt diese Einschränkung der Reihenfolge auf und gibt alle möglichen Anordnungen der Länge r zurück:

itertools.permutations([1, 2, 3, 4, 5], 2) =>
  (1, 2), (1, 3), (1, 4), (1, 5),
  (2, 1), (2, 3), (2, 4), (2, 5),
  (3, 1), (3, 2), (3, 4), (3, 5),
  (4, 1), (4, 2), (4, 3), (4, 5),
  (5, 1), (5, 2), (5, 3), (5, 4)

itertools.permutations([1, 2, 3, 4, 5]) =>
  (1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5),
  ...
  (5, 4, 3, 2, 1)

Gibst du keinen Wert für r an, wird die Länge des iterierbaren Objekts verwendet. Alle Elemente werden also permutiert.

Beachte, dass diese Funktionen alle möglichen Kombinationen nach Position erzeugen und nicht verlangen, dass der Inhalt von iterable eindeutig ist:

itertools.permutations('aba', 3) =>
  ('a', 'b', 'a'), ('a', 'a', 'b'), ('b', 'a', 'a'),
  ('b', 'a', 'a'), ('a', 'a', 'b'), ('a', 'b', 'a')

Das identische Tupel ('a', 'a', 'b') kommt zweimal vor, aber die zwei „a“-Zeichenketten stammen von verschiedenen Positionen.

Die Funktion itertools.combinations_with_replacement(iterable, r) lockert eine andere Einschränkung: Elemente können sich innerhalb eines Tupels wiederholen. Begrifflich wird ein Element für die erste Position jedes Tupels ausgewählt und dann zurückgelegt, bevor das zweite Element ausgewählt wird.

itertools.combinations_with_replacement([1, 2, 3, 4, 5], 2) =>
  (1, 1), (1, 2), (1, 3), (1, 4), (1, 5),
  (2, 2), (2, 3), (2, 4), (2, 5),
  (3, 3), (3, 4), (3, 5),
  (4, 4), (4, 5),
  (5, 5)

Elemente gruppieren¶

Die letzte Funktion, die ich erörtere, itertools.groupby(iter, key_func=None), ist die komplizierteste. key_func(elem) ist eine Funktion, die für jedes vom iterierbaren Objekt zurückgegebene Element einen Schlüsselwert berechnen kann. Gibst du keine Schlüsselfunktion an, ist der Schlüssel einfach jedes Element selbst.

groupby() sammelt alle aufeinanderfolgenden Elemente aus dem darunterliegenden iterierbaren Objekt, die denselben Schlüsselwert haben, und gibt einen Strom von 2-Tupeln zurück, die einen Schlüsselwert und einen Iterator für die Elemente mit diesem Schlüssel enthalten.

city_list = [('Decatur', 'AL'), ('Huntsville', 'AL'), ('Selma', 'AL'),
             ('Anchorage', 'AK'), ('Nome', 'AK'),
             ('Flagstaff', 'AZ'), ('Phoenix', 'AZ'), ('Tucson', 'AZ'),
             ...
            ]

def get_state(city_state):
    return city_state[1]

itertools.groupby(city_list, get_state) =>
  ('AL', iterator-1),
  ('AK', iterator-2),
  ('AZ', iterator-3), ...

where
iterator-1 =>
  ('Decatur', 'AL'), ('Huntsville', 'AL'), ('Selma', 'AL')
iterator-2 =>
  ('Anchorage', 'AK'), ('Nome', 'AK')
iterator-3 =>
  ('Flagstaff', 'AZ'), ('Phoenix', 'AZ'), ('Tucson', 'AZ')

groupby() geht davon aus, dass der Inhalt des darunterliegenden iterierbaren Objekts schon nach dem Schlüssel sortiert ist. Beachte, dass die zurückgegebenen Iteratoren ebenfalls das darunterliegende iterierbare Objekt verwenden. Du musst daher die Ergebnisse von iterator-1 verbrauchen, bevor du iterator-2 und seinen zugehörigen Schlüssel anforderst.

Das Modul functools¶

Das Modul functools enthält einige Funktionen höherer Ordnung. Eine Funktion höherer Ordnung nimmt eine oder mehrere Funktionen als Eingabe und gibt eine neue Funktion zurück. Das nützlichste Werkzeug in diesem Modul ist die Funktion functools.partial().

Bei Programmen im funktionalen Stil willst du manchmal Varianten bestehender Funktionen bauen, bei denen einige der Parameter schon gefüllt sind. Betrachte eine Python-Funktion f(a, b, c). Du willst vielleicht eine neue Funktion g(b, c) bauen, die f(1, b, c) entspricht – du füllst also einen Wert für einen der Parameter von f() ein. Das nennt man „partielle Funktionsanwendung“.

Der Konstruktor von partial() nimmt die Argumente (function, arg1, arg2, ..., kwarg1=value1, kwarg2=value2). Das entstehende Objekt ist aufrufbar, du kannst es also einfach aufrufen, um function mit den eingefüllten Argumenten aufzurufen.

Hier ein kleines, aber realistisches Beispiel:

import functools

def log(message, subsystem):
    """Write the contents of 'message' to the specified subsystem."""
    print('%s: %s' % (subsystem, message))
    ...

server_log = functools.partial(log, subsystem='server')
server_log('Unable to open socket')

functools.reduce(func, iter, [initial_value]) führt eine Operation kumulativ auf allen Elementen des iterierbaren Objekts aus und lässt sich daher nicht auf unendliche iterierbare Objekte anwenden. func muss eine Funktion sein, die zwei Elemente nimmt und einen einzelnen Wert zurückgibt. functools.reduce() nimmt die ersten zwei Elemente A und B, die der Iterator zurückgibt, und berechnet func(A, B). Es fordert dann das dritte Element, C, an, berechnet func(func(A, B), C), verbindet dieses Ergebnis mit dem vierten zurückgegebenen Element und fährt fort, bis das iterierbare Objekt erschöpft ist. Gibt das iterierbare Objekt überhaupt keine Werte zurück, wird ein TypeError ausgelöst. Ist der Anfangswert angegeben, wird er als Startpunkt verwendet und func(initial_value, A) als erste Berechnung ausgeführt.

>>> import operator, functools
>>> functools.reduce(operator.concat, ['A', 'BB', 'C'])
'ABBC'
>>> functools.reduce(operator.concat, [])
Traceback (most recent call last):
  ...
TypeError: reduce() of empty iterable with no initial value
>>> functools.reduce(operator.mul, [1, 2, 3], 1)
6
>>> functools.reduce(operator.mul, [], 1)
1

Wenn du operator.add() mit functools.reduce() verwendest, addierst du alle Elemente des iterierbaren Objekts. Dieser Fall ist so verbreitet, dass es dafür eine besondere integrierte Funktion gibt: sum().

>>> import functools, operator
>>> functools.reduce(operator.add, [1, 2, 3, 4], 0)
10
>>> sum([1, 2, 3, 4])
10
>>> sum([])
0

Bei vielen Verwendungen von functools.reduce() ist es allerdings klarer, einfach die naheliegende for-Schleife zu schreiben:

import functools
# Instead of:
product = functools.reduce(operator.mul, [1, 2, 3], 1)

# You can write:
product = 1
for i in [1, 2, 3]:
    product *= i

Eine verwandte Funktion ist itertools.accumulate(iterable, func=operator.add). Sie führt dieselbe Berechnung aus, gibt aber nicht nur das Endergebnis zurück: accumulate() gibt einen Iterator zurück, der auch jedes Teilergebnis liefert:

itertools.accumulate([1, 2, 3, 4, 5]) =>
  1, 3, 6, 10, 15

itertools.accumulate([1, 2, 3, 4, 5], operator.mul) =>
  1, 2, 6, 24, 120

Das Modul operator¶

Das Modul operator wurde früher erwähnt. Es enthält eine Reihe von Funktionen, die den Operatoren von Python entsprechen. Diese Funktionen sind in Code im funktionalen Stil oft nützlich, weil sie dir das Schreiben trivialer Funktionen ersparen, die eine einzige Operation ausführen.

Einige der Funktionen in diesem Modul sind:

Mathematische Operationen: add(), sub(), mul(), floordiv(), abs(), …
Logische Operationen: not_(), truth().
Bitweise Operationen: and_(), or_(), invert().
Vergleiche: eq(), ne(), lt(), le(), gt() und ge().
Objektidentität: is_(), is_not().

Eine vollständige Liste steht in der Dokumentation des Moduls operator.

Kleine Funktionen und der lambda-Ausdruck¶

Beim Schreiben von Programmen im funktionalen Stil brauchst du oft kleine Funktionen, die als Prädikate dienen oder Elemente auf irgendeine Weise verbinden.

Wenn es eine passende integrierte Funktion von Python oder eine Modulfunktion gibt, musst du überhaupt keine neue Funktion festlegen:

stripped_lines = [line.strip() for line in lines]
existing_files = filter(os.path.exists, file_list)

Wenn die Funktion, die du brauchst, nicht existiert, musst du sie schreiben. Ein Weg, kleine Funktionen zu schreiben, ist der lambda-Ausdruck. lambda nimmt eine Reihe von Parametern und einen Ausdruck, der diese Parameter verbindet, und erzeugt eine anonyme Funktion, die den Wert des Ausdrucks zurückgibt:

adder = lambda x, y: x+y

print_assign = lambda name, value: name + '=' + str(value)

Eine Alternative ist, einfach die def-Anweisung zu verwenden und eine Funktion auf die üblichen Weise festzulegen:

def adder(x, y):
    return x + y

def print_assign(name, value):
    return name + '=' + str(value)

Welche Alternative ist zu bevorzugen? Das ist eine Stilfrage. Mein üblicher Weg ist, lambda zu vermeiden.

Ein Grund für meine Vorliebe ist, dass lambda bei den Funktionen, die es festlegen kann, recht beschränkt ist. Das Ergebnis muss sich als einzelner Ausdruck berechnen lassen, du kannst also keine mehrwegigen if... elif... else-Vergleiche oder try... except-Anweisungen haben. Wenn du versuchst, in einer lambda-Anweisung zu viel zu tun, landest du bei einem überkomplizierten Ausdruck, der schwer zu lesen ist. Schnell, was tut der folgende Code?

import functools
total = functools.reduce(lambda a, b: (0, a[1] + b[1]), items)[1]

Du kannst es herausfinden, aber es braucht Zeit, den Ausdruck zu entwirren, um zu erkennen, was vorgeht. Eine kurze verschachtelte def-Anweisung zu verwenden macht die Dinge etwas besser:

import functools
def combine(a, b):
    return 0, a[1] + b[1]

total = functools.reduce(combine, items)[1]

Am besten wäre es aber, wenn ich einfach eine for-Schleife verwendet hätte:

total = 0
for a, b in items:
    total += b

Oder die integrierte Funktion sum() und einen Generatorausdruck:

total = sum(b for a, b in items)

Viele Verwendungen von functools.reduce() sind klarer, wenn man sie als for-Schleifen schreibt.

Fredrik Lundh hat einmal die folgenden Regeln vorgeschlagen, um Verwendungen von lambda umzubauen:

Schreibe eine lambda-Funktion.
Schreibe einen Kommentar, der erklärt, was dieses lambda eigentlich tut.
Betrachte den Kommentar eine Weile und denke dir einen Namen aus, der das Wesentliche des Kommentars einfängt.
Wandle das lambda mit diesem Namen in eine def-Anweisung um.
Entferne den Kommentar.

Mir gefallen diese Regeln wirklich, aber du darfst gern anderer Meinung sein, ob dieser lambda-freie Stil besser ist.

Änderungsverlauf und Dank¶

Dieses HOWTO wurde ursprünglich von A. M. Kuchling geschrieben. Der Autor möchte den folgenden Personen für Vorschläge, Korrekturen und Hilfe zu verschiedenen Entwürfen dieses Artikels danken: Ian Bicking, Nick Coghlan, Nick Efford, Raymond Hettinger, Jim Jewett, Mike Krell, Leandro Lameiro, Jussi Salmela, Collin Winter, Blake Winton.

Version 0.1: veröffentlicht am 30. Juni 2006.

Version 0.11: veröffentlicht am 1. Juli 2006. Tippfehler behoben.

Version 0.2: veröffentlicht am 10. Juli 2006. Die Abschnitte zu Genexps und Listcomps zu einem zusammengeführt. Tippfehler behoben.

Version 0.21: Weitere Quellen ergänzt, die auf der Mailingliste tutor vorgeschlagen wurden.

Version 0.30: Ergänzt einen Abschnitt über das Modul functional, geschrieben von Collin Winter, ergänzt einen kurzen Abschnitt über das Modul operator, ein paar weitere Änderungen.

Quellen¶

Allgemein¶

Structure and Interpretation of Computer Programs von Harold Abelson und Gerald Jay Sussman mit Julie Sussman. Das Buch findest du unter https://mitpress.mit.edu/sicp. In diesem Klassiker der Informatik erörtern die Kapitel 2 und 3 die Verwendung von Sequenzen und Strömen, um den Datenfluss innerhalb eines Programms zu organisieren. Das Buch verwendet für seine Beispiele Scheme, aber viele der in diesen Kapiteln beschriebenen Entwurfsansätze lassen sich auf Python-Code im funktionalen Stil anwenden.

https://defmacro.org/2006/06/19/fp.html: Eine allgemeine Einführung in die funktionale Programmierung, die Java-Beispiele verwendet und eine ausführliche historische Einleitung hat.

https://en.wikipedia.org/wiki/Functional_programming: Allgemeiner Wikipedia-Eintrag, der funktionale Programmierung beschreibt.

https://en.wikipedia.org/wiki/Coroutine: Eintrag zu Coroutinen.

https://en.wikipedia.org/wiki/Partial_application: Eintrag zum Begriff der partiellen Funktionsanwendung.

https://en.wikipedia.org/wiki/Currying: Eintrag zum Begriff des Curryings.

Python-spezifisch¶

https://gnosis.cx/TPiP/: Das erste Kapitel von David Mertz‘ Buch Text Processing in Python erörtert im Abschnitt „Utilizing Higher-Order Functions in Text Processing“ funktionale Programmierung für die Textverarbeitung.

Mertz hat außerdem eine dreiteilige Artikelserie über funktionale Programmierung für die DeveloperWorks-Seite von IBM geschrieben. Siehe Teil 1, Teil 2 und Teil 3.

Python-Dokumentation¶

Dokumentation zum Modul itertools.

Dokumentation zum Modul functools.

Dokumentation zum Modul operator.

PEP 289: „Generator Expressions“

PEP 342: „Coroutines via Enhanced Generators“ beschreibt die neuen Generator-Eigenschaften in Python 2.5.