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:

1. Schreibe eine lambda-Funktion.

2. Schreibe einen Kommentar, der erklärt, was dieses lambda eigentlich
   tut.

3. Betrachte den Kommentar eine Weile und denke dir einen Namen aus,
   der das Wesentliche des Kommentars einfängt.

4. Wandle das lambda mit diesem Namen in eine def-Anweisung um.

5. 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.
