Funktionale Programmierung in Python

Techniken

Closures

innere Funktionen, die den Aufrufkontext konserviert

Python 2.*

mit Python 2.* ist nur der lesende Zugriff auf die Variablen im umgebenden, nicht globalen Scope möglich
Beispiel: lesende Closure

>>> def addWith(first):

...    def innerFunction(second):
...       return  first + second

...    return innerFunction
...
>>> a10=addWith(10)

>>> a15=addWith(15)
>>> a10(30)
40
>>> a15(30)

45
>>> a10(130)
140
>>>

Python unterstützt keine schreibenden Zugriff auf den umgebenden Scope
Beispiel: schreibende Closure

>>> def counter(start):

...     def memorizeCount():
...             start+=1
...             return start

...     return memorizeCount
...
>>> c=counter(10)

>>> c()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>

  File "<stdin>", line 3, in memorizeCount

UnboundLocalError: local variable 'start' referenced before assignment

der Ausdruck start+=1 definiert die lokale Variable start ein
da sie keinen Wert besitzt, kann dieser auch nicht inkrementiert werden

Python 3.*

mit Python 3.0 wurde das Schlüsselwort nonlocal eingeführt, mit der die innere Funktionen den umgebenden, nicht globalen Scope schreibend, referenzieren kann erweiterte Umsetzung von Closures
Beispiel: schreibende Closure

>>> def counter(start):

...     def memorizeCount():
...       nonlocal start
...       start+=1
...       return start

...     return memorizeCount
...
>>> a=counter(10)

>>> b=counter(-5)
>>> a(),b()
(11, -4)

>>> a(),b()
(12, -3)
>>> a(),b()

(13, -2)

lambda Funktionen

Lambda Funktion in Python: Eine Funktion, die eine beliebige Anzahl von Argument annimmt und den Wert eines Ausdrucks zurückgibt.

lambda Funktionen werden, da sie keinen Namen besitzen, auch gerne als anonyme Funktionen bezeichnet
Syntax: lambda a,b,.. : expr
Beispiel: lesende Closure

>>> def addWith_(first):
...     return lambda second: first + second

...
>>> a10=addWith_(10)
>>> a15=addWith_(15)

>>> a10(30)
40
>>> a15(30)
45
>>> a10(130)

140

Beispiel: Erzeugen eines Filter

def makefilter(keep):

    """ Return a function that takes a string and returns a copy of that
        string consisting only of the characters in 'keep'.
    """
    import string
    # make a string of all chars, and one of all those NOT in 'keep'
    allchars = string.maketrans('', '')

    delchars = ''.join([c for c in allchars if c not in keep])

    # return the function
    return lambda s,a=allchars,d=delchars: s.translate(a, d)

in Aktion:

>>> onlyVocals=makefilter("aeiou")

>>> onlyVocals("Only for testing purpose.")
'oeiuoe'
>>> onlyUpper=makefilter(string.ascii_uppercase)

>>> onlyUpper("A Few CamelCap Words.")
'AFCCW'

Generatoren

Charakteristisch für funktionale Programmiersprachen ist das Verarbeiten von Listen. Generatoren lassen Listen leicht entstehen.

yield Funktion

Producer

Das Schlüsselwort yield verwandelt eine Funktion in einen Generator, der einen Iterator (vgl. Iterator Protokollzurückgibt.

der Iterator besitzt ein Gedächtnis, das mit yield abgefragt werden kann
yield liefert den Wert des Funktionsaufrufes zurück
die Ausführung der Funktion wird mit der yield Anweisung eingefroren und beim nächsten Durchlauf wieder aufgenommen
die Iteration ist mit der Abarbeitung des Funktionskörpers oder einer expliziten return Anweisung beendet die Exception StopIteration wird geworfen
die return Anweisung darf keinen Wert zurückgeben
Beispiel: Iterator über alle natürlichen Zahlen

>>> def generateNaturalNumbers():
...     i=1
...     while True:

...             yield i
...             i+=1
...
>>> n=generateNaturalNumbers()

>>> n.next()
1
>>> for i in range(100000): n.next()

... 
.
.
.
100000
100001
>>> n.next()

100002

Beispiel: Aufzählung der Ascii-Zeichen - Verknüpfung einer endlichen und unendlichen Liste

>>> import string

>>> n=generateNaturalNumbers()
>>> zip ( string.ascii_letters, n )

[('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6), ('g', 7), ('h', 8), ('i', 9), ('j', 10), ('k', 11), 

('l', 12), ('m', 13), ('n', 14), ('o', 15), ('p', 16), ('q', 17), ('r', 18), ('s', 19), ('t', 20), ('u', 21), 

('v', 22), ('w', 23), ('x', 24), ('y', 25), ('z', 26), ('A', 27), ('B', 28), ('C', 29), ('D', 30), ('E', 31), 

('F', 32), ('G', 33), ('H', 34), ('I', 35), ('J', 36), ('K', 37), ('L', 38), ('M', 39), ('N', 40), ('O', 41), 

('P', 42), ('Q', 43), ('R', 44), ('S', 45), ('T', 46), ('U', 47), ('V', 48), ('W', 49), ('X', 50), ('Y', 51), 

('Z', 52)]

Consumer

Mit Python 2.5 können Generatoren auch Werte annehmen. Damit werden Generatoren zu Coroutinen, den es ist möglich, sie an beliebigen Stellen aufzurufen, zu verlassen oder zu beenden.

für einen Generator n gilt:
- n.next(): Iterator produziert einen Wert
- n.send(): Iterator konsumiert einen Wert
- n.close(): beendet die Iteration
Beispiel: Generator als Coroutine

>>> def generateNumbers():
...     i=1
...     while True:

...             val=(yield i)
...             if (val): i=val

...             else: i+=1
...
>>> n=generateNumbers()

>>> n.next()
1
>>> n.send(1000)
1000

>>> n.next()
1001
>>> n.next()
1002
>>> n.close()

>>> n.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>

StopIteration

David Beazley, Autor von Python Essential Reference und SWIG, zeigt in seinen Präsentationen GeneratorsUK.pdf und Coroutines.pdf die Anwendung von Generatoren bis zum Entwurf eines Multitasking Betriebssystems.

Generator Expressions

"... generator expressions as a high performance, memory efficient generalization of list comprehensions [1] and generators [2]." (PEP 289)

Generator Expressions verbinden die Funktionalität von List Comprehension mit der Bedarfsauswertung von Generatoren.
Beispiel:Speicherverbrauchvergleich von list comprehension und generator expressions
- xrange ist selbst lazy

>>> listComprehension=   [i for i in xrange(1000)]

>>> generatorExpression= (i for i in xrange(1000))

>>> >>> listComprehension
[0, 1, 2, 3, 4, 5, 6, 

.
.
.
, 995, 996, 997, 998, 999]

>>> generatorExpression
<generator object <genexpr> at 0x7ff2485f6910>
>>> sys.getsizeof( listComprehension )

9032
>>> sys.getsizeof( generatorExpression )
80

Beispiel:xrange nachgebaut
- die Funktion generateOpenRange ist eine Erweiterung der Funktion generateNaturalNumbers
- sie erzeugt einen Strom von Zahlen
- sowohl der Startwert als auch die Schrittweite kann vorgegeben werden

def generateOpenRange(start=1,step=1):

  i=start
  while True:
    yield i
    i+=step

Beispiel: Generator Expression in Aktion

>>> quads= ( n*n for n in generateOpenRange(10) )

>>> quads.next(), quads.next(), quads.next(),quads.next(), quads.next()

(100, 121, 144, 169, 196)
>>> for i in ( 2**n for n in generateOpenRange(10,10) ):

...     if (i > 2**60): break
...     print i,

...
1024 1048576 1073741824 1099511627776 1125899906842624 1152921504606846976
>>> for i in itertools.islice( ( -1.0/n for n in generateOpenRange(start=-1,step=-1) ),1,10):

...     print i,
...
0.5 0.333333333333 0.25 0.2 0.166666666667 0.142857142857 0.125 0.111111111111 0.1

>>> quadNumbers= ( x for x in generateOpenRange(1000) if round( math.sqrt( x ))**2 == x )

>>> quadNumbers.next(), quadNumbers.next(), quadNumbers.next(),quadNumbers.next(), quadNumbers.next()

(1024, 1089, 1156, 1225, 1296)
>>> for i in itertools.islice(( x for x in generateOpenRange(1000) if round( math.sqrt( x ))**2 == x ),25,35):

...     print i,
...
3249 3364 3481 3600 3721 3844 3969 4096 4225 4356

>>> quadNumbersEndingIn5= ( x for x in generateOpenRange(1000,5) if round( math.sqrt( x )) **2 == x )

>>> quadNumbersEndingIn5.next(), quadNumbersEndingIn5.next(), quadNumbersEndingIn5.next(),quadNumbersEndingIn5.next(), 

quadNumbersEndingIn5.next()
(1225, 1600, 2025, 2500, 3025)

>>> for i in itertools.islice(( x for x in generateOpenRange(start=0,step=5) 

if round( math.sqrt( x )) **2 == x ),100,105):

...     print i,
...
250000 255025 260100 265225 270400

>>> itertools.islice(( x for x in generateOpenRange(start=0,step=5) 

if round( math.sqrt( x )) **2 == x ),1000,10001).next()

25000000

der letzte Ausdruck verlangt eine Erklärung
- iteriert über alle Zahlen x, die durch 5 teilbar sind:
```
generateOpenRange(start=0,step=5)
```
- filtere alle xheraus, die eine Quadratzahl sind:
```
round( math.sqrt( x )) **2 == x
```
- bilde einen Slice über die 1000 Zahl der Sequenz, und fordere die Ausgabe an:
```
itertools.islice(....),1000,1001).next()
```

built-in Funktionen

Während map, filter und zip aus einer Liste eine neue Liste erzeugen, reduziert reduce die Liste auf den Ausgabewert. Mit Python 3.0 sind map, filter und zip lazy, d.h.: sie erzeugen die resultierende Liste erst auf Bedarf. reduce wird vom built-in in die Bibliothek functools verschoben.
Diese drei Funktionen map, filter und reducerepräsentieren die drei typischen Anwendungsfälle, mit den Sequenzen verarbeitet werden. Sie sind die drei elementaren funktionalen Bausteine, die funktionle Programmiersprachen auszeichnen.

map

wende eine Funktion sukzessive auf jedes Element der Eingabesequenz an und gib die neuen Werte als Liste zurück
Beispiele:

>>> map ( lambda x: x*x, range(10))

[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

>>> import string
>>> map ( lambda x,y : str(x)+y, range(10),string.ascii_uppercase)

['0A', '1B', '2C', '3D', '4E', '5F', '6G', '7H', '8I', '9J', 'NoneK', 'NoneL', 'NoneM', 'NoneN', 'NoneO', 

'NoneP', 'NoneQ', 'NoneR', 'NoneS', 'NoneT', 'NoneU', 'NoneV', 'NoneW', 'NoneX', 'NoneY', 'NoneZ']

>>>

filter

wende Filter sukzessive auf jedes Element der Eingabesequenz an und gib nur die Element zurück, die zu True evaluieren
die filternde Funktion wird als Prädikat bezeichnet
Beispiel:

>>> filter( lambda x: x % 2 != 0, range(10))

[1, 3, 5, 7, 9]
>>> filter( lambda a : not a.startswith("None") , map(lambda x,y : str(x)+y, range(10),string.ascii_uppercase) )

['0A', '1B', '2C', '3D', '4E', '5F', '6G', '7H', '8I', '9J']

reduce

wende eine Funktion, die zwei Argumente verlangt, sukzessive auf das Ergebnis der letzten Iteration und ein Element der Eingabesequenz an
bei der ersten Iteration werden die ersten zwei Elemente der Eingabesequenz verarbeitet

>>> reduce ( lambda a,b: a*b,range(1,10))

362880
>>> import operator
>>> reduce ( operator.add ,range(10))

45
>>> reduce(operator.concat, filter( lambda a : not a.startswith("None") ,map ( lambda x,y : str(x)+y, range(10),string.ascii_uppercase)))

'0A1B2C3D4E5F6G7H8I9J'

zip

fasse Sequenzen zu einer Lister zusammen, wobei die Länge der resultierende Liste dem Minimum der Längen des Sequenzen entspricht
Beispiel: Liste von Trippels

>>> zip(range(1,4),range(101,104),range(1001,10000000))

[(1, 101, 1001), (2, 102, 1002), (3, 103, 1003)]

zip ist sehr hilfreich um aus Listen Dictionaries zu erzeugen
Beispiel: List-Dictionary-Idiom

>>> print accs
['root', 'bin', 'daemon', 'lp', 'mail', 'games', 'wwwrun', 'ftp', 'nobody', 'irc',

'at','postfix', 'man', 'news', 'uucp', 'ldap', 'pop']

>>> print ids
['0', '1', '2', '4', '8', '12', '30', '40', '65534', '39', '25', '51', '13', '9', '10', 

'76', '67']
>>> d=dict( zip( accs, ids ) )

>>> d
{'bin': '1', 'ftp': '40', 'daemon': '2', 'uucp': '10', 'postfix': '51', 'nobody': '65534', 'pop': '67', 'ldap': '76', 

'games': '12', 'at': '25', 'lp': '4', 'news': '9', 'mail': '8', 'wwwrun': '30', 'irc': '39', 'root': '0', 'man': '13'}

>>> d["man"]
'13' 
>>> d.keys()
['bin', 'ftp', 'daemon', 'uucp', 'postfix', 'nobody', 'pop', 'ldap', 'games', 'at', 'lp', 'news', 'mail', 'wwwrun', 

'irc', 'root', 'man']

list comprehension

list comprehension bietet die Funktionalität von map und filter auf einfache Weise an
die expression entspricht der map und die Bedingung der filter Funktion
Syntax: zwei äquivalente Ausdrücke

[ expression for item1 in sequence1
             for item2 in sequence2
             ...

             for itemN in sequenceN
             if condition ]

s=[]
for item1 in sequence1:

  for item2 in sequence2:
    ...
           for itemN in sequenceN:

             if condition: s.append(expression)

Seiteneffekte
- list comprehension mit Python 2.* als funktionaler syntatic sugar erzeugt Seiteneffekte !!!!
- der Wert x ist im folgenden Ausdruck nach der list comprehension im globalen Scope

grimm@laiard ~ $ /home/grimm/python/Python-2.6/python
Python 2.6 (r26:66714, Oct 16 2008, 14:40:39)

[GCC 3.4.6] on linux2
Type "help", "copyright", "credits" or "license" for more information.

>>> [ x*x for x in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

>>> print x
9

im Gegensatz zu generator expressions werden list expressions strikt ausgewertet
Beispiel: Bedarfsauswertung versus strikt Auswertung

>>> [x*x for x in range(10) if x%2 != 0]

[1, 9, 25, 49, 81]
>>> (x*x for x in range(10) if x%2 != 0)

<generator object <genexpr> at 0x7ff7876db9b0>

Das Decorate-Sort-Undecorate Idiom (auch bekannt als Schwartzian transform) hilft, um eine Liste nach einem vorgegebenen Kriterium zu sortieren.
Sortiere die numerischen Strings nach ihrem numerischen Wert.

Beispiel: Naives Sortieren

>>> strings= [ str(i) for i in range(11,6,-1) ]

>>> strings
['11', '10', '9', '8', '7']

>>> strings.sort()
>>> print strings
['10', '11', '7', '8', '9']

Beispiel: Decorate-Sort-Undecorate

>>> decorate= [ ( int(i),i) for i in strings ]

>>> decorate
[(11, '11'), (10, '10'), (9, '9'), (8, '8'), (7, '7')]

>>> decorate.sort()
>>> decorate
[(7, '7'), (8, '8'), (9, '9'), (10, '10'), (11, '11')]

>>> undecorate=[ y for x,y in decorate ]
>>> undecorate

['7', '8', '9', '10', '11']

Es gilt als guter Stil in Python, statt den built-in Funktion map und filter list comprehension zu verwenden.

Bibliotheken

functools

Durch die Methode partialerlaubt Python das teilweise evaluieren von Funktionen.

Beispiel: partial Evaluation

>>> import functools
>>> def divide(nom,denom): return nom/denom

...
>>> divide(1.0,3)
0.33333333333333331
>>> divideBy3= functools.partial(divide,denom=3)

>>> divideBy3(1.0) == divide(1.0,3)
True

itertools

Die itertools Bibliothek kombiniert functional Tools mit Iteratoren. Die Methoden imap, izip und ifilter sind die lazy Äquivalente zu den built-in Funktionen map, zip und filterund ersetzen diese mit Python 3.* . Das heißt insbesondere, das die Elemente explizit angefordert (consumiert) werden müssen.

Iteratoren erzeugen

Dieses Methoden erzeugen in der Regel einen Iterator über einen unendlichen Datenstrom.

count(n=0): Natürlichen Zahlen
cycle(seq): Wiederholung der Sequenz
chain(seq1,seq2,..): (endliche) Verkettung der Iteratoren
slice(seq,[start],stop[,end]: endlicher Slice von seq
tee(seq,n=2): vervielfältigt eine Sequenz
Beispiel: Iteratoren erzeugen

>>> import itertools
>>> intFrom5=itertools.count(5)

>>> intFrom5.next(), intFrom5.next()
(5, 6)

>>> i=itertools.cycle("123")
>>> i.next(),i.next(),i.next(),i.next()

('1', '2', '3', '1')
>>> i=itertools.chain("123",[(1,2),(3,4)])

>>> i.next(),i.next(),i.next(),i.next()

('1', '2', '3', (1, 2))

>>> list( itertools.islice( itertools.count(),2,20,4) )

[2, 6, 10, 14, 18]
>>> iters= itertools.tee(range(5),3)

>>> first,second,third=list(iters)
>>> list(first),list(second),list(third)

([0, 1, 2, 3, 4], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4])

Durch Anwendung der Funktion list auf einen endlichen Datenstrom, erzwinge ich die strikte Auswertung des Datenstroms.

Funktion auf die Elemente anwenden

Beispiel: imap

>>> itertools.imap (operator.add, [1,2,3],[3,2,1])

<itertools.imap object at 0x7f956f8bb4d0>
>>> for i in itertools.imap (operator.add, [1,2,3],[3,2,1]): print i,

...
4 4 4

Elemente filtern

Neben dem built-in Äquivalent ifilter, gibt es die zwei Haskell Varianten takewhile und dropwhile, die abhängig von dem Prädikat die Elemente einer iterierbaren Sequenz zurückgeben.

für die Sequenz seq gilt:
- takewhile(predicate, seq): gib die Element solange zurück, solange das Prädikat zu True evaluiert
- dropwhile(predicate, seq): entferne die Elemente solange, solange das Prädikate zu True evaluiert
Beispiel: takewhile/dropwhile Vergleich

>>> def lessThan20(x): return ( x < 20 )

...
>>> for i in itertools.takewhile(lessThan20,range(10,31)): print i,

...
10 11 12 13 14 15 16 17 18 19

>>> for i in itertools.dropwhile(lessThan20,range(10,31)): print i,

...
20 21 22 23 24 25 26 27 28 29 30

>>> list(itertools.takewhile(lessThan20,range(10,31))) + list(itertools.dropwhile(lessThan20,range(10,31)))

[10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]

Elemente gruppieren

groupby(iter,key_func=None):gruppiert alle Elemente aus iter entsprechend ihrem key
- der Schlüssel sind per Default die iterierten Elemente
- die Liste iter muß entsprechend dem Schlüssel sortiert sein
- leider ist itertools.groupby sehr schwierig anzuwenden
Beispiel: brain melting with groupby

>>> import itertools

>>> testing="00001234445"
>>> for key, group in itertools.groupby(testing):

...     for test in group:
...             print test
...     print "------"

...
0
0
0
0
------
1
------
2

------
3
------
4
4
4
------
5
------

>>> things = [("animal", "bear"), ("animal", "duck"), ("plant", "cactus"), ("vehicle", "speed boat"), ("vehicle", "school bus")]

>>>
>>> for key, group in itertools.groupby(things, lambda x: x[0]):

...    for thing in group:
...       print "A %s is a %s." % (thing[1], key)

...    print " "
...
A bear is a animal.
A duck is a animal.

A cactus is a plant.

A speed boat is a vehicle.

A school bus is a vehicle.

Ausblick

Auch mit Python 3.0 wurden Pythons funktionale Elemente verbessert. So sind die built-in Funktionen map, filter und lambda durch ihr Äquivalente in der itertools Bibliothek aus Python 2.* ersetzt worden. Diese wenden nun Bedarfsauswertung statte strikte Auswertung an.
Darüber hinaus findet keine Verschmutzung des globalen Scopes mittels list comprehension mehr statt.