Informatika2-2012/Kukaba12

A lap 2012. május 1., 10:56-kori változata

Funkcionális programozás python-ban

Programozási paradigmák

Egy probléma megoldásához többféleképp közelíthetünk. Az, hogy a problémát hogyan bontjuk részekre, meghatározza a használható/andó programnyelvi elemeket. Ennek megfelelően a programnyelvi elemeknek négy fő típusát szokás megkülönböztetni:

• Parancsközpontú (imperative), vagy vele majdnem azonos értelemben használt eljárásközpontú (procedurális, procedural)
  • algoritmikus gondolkodás, receptszerű programozás, ,,tedd ezt, majd ezt,..."
  • A Neumann-elvű számítógép ötletére épül
  • Számítási lépések időben egymás utáni elvégzése (parancsok végrehajtása)
  • Tipikus parancsok: értékadás, eljárás meghívása,
  • Az eljárások megváltoztatják a program kontrollstruktúráinak állapotát
• Objektumközpontú (objektumorientált, object-oriented)
  • Az emberek közti interakciókat és a való világ jelenségeit modellezi
  • A fogalmakat osztályok, a jelenségeket objektumok valósítják meg
• Függvényközpontú (funkcionális, functional)
  • A függvények matematikai elméletére épül,
  • A függvények értéket adnak vissza, de nincs mellékhatásuk, nincsenek változók
  • A program függvényhívásokból áll
  • A parancsközpontúnál egyszerűbb struktúra, könnyebben bizonyítható a program helyessége, könnyebben tesztelhető, debug-olható
• Logikai, vagy a nála általánosabb értelemben használt deklaratív (logic, declarative)
  • A program végrehajtása az axiómáknak és a következtetési szabályoknak (deklarációknak) megfelelő lehetőség(ek) megkeresésből áll
  • Matematikai logikai alapú
  • Szűkebb alkalmazási lehetőségek

Függvényközpontú programozás

A függvényközpontú programozás klasszikus elemei a Pythonban

A lambda kifejezések névtelen függvények, alakjuk:

lambda paraméterek: kifejezés

ahol a paraméterek egy esetleg üres lista, a kifejezés pedig egy elágazást, ciklust, return vagy yield utasítást nem tartalmazó (de esetleg feltételes) kifejezés lehet. Csak nagyon egyszerű (félsoros) függvényekre használjuk!

lambda x: x ** 2
lambda x: "pozitív" if x > 0 else "nem pozitív"
lambda x, y: x + y

A ciklusok elkerülésére három egyszerű ,,klasszikus függvény szolgál:

• megfeleltetés -- egy függvény egy bejárható (iterable) objektum minden elemére hat: map()

map(lambda x: x ** 2, [1, 2, 3, 4])  # [1, 4, 9, 16]
map(lambda x, y: x + y, [1, 2, 3, 4], [0, 10, 100, 1000]) 
                                # [1, 12, 103, 1004]
map(lambda x, y: x ** y, itertools.repeat(2)[1, 2, 3, 4], [0, 10, 100, 1000]) 
                                # [1, 12, 103, 1004]

• szűrés -- egy bejárható objektumnak csak azokat az elemeit tartjuk meg, amelyre egy függvény True értéket ad: filter()

filter(lambda x: x > 0, [-1, 2, -3, 4])  # [2, 4]

• redukálás: reduce() (3.0-tól a standard könyvtárból törölve: functools.reduce())

reduce(lambda x, y: x + y, [1, 2, 3, 4]))  # 10

Listaértelmezések (list comprehensions)

A fenti három függvény helyettesítésére szolgál a lista elemeinek a matematikában szokásos halmazmegadási módjára emlékeztető leírása, amelyben ciklus-szerű és feltétel-szerű nyelvi elem is szerepelhet. Alakjuk azonnal érthető:

[kifejezés for elem in bejárható_objektum]
[kifejezés for elem in bejárható_objektum if feltétel]
[kifejezés for elem in bejárható_objektum1 if feltétel1
           for elem in bejárható_objektum2 if feltétel2
           for elem in bejárható_objektumN if feltételN]

Megadjuk a megfeleltetés és szűrés fenti első két példája e szintaktika szerinti változatát:

[x ** 2 for x in [1, 2, 3, 4]]  # [1, 4, 9, 16]
[x for x in [-1, 2, -3, 4] if x > 0]

A harmadik esetre Guido van Rossum azt mondja, hogy tipikusan csak asszociatív függvényekre használjuk, mint + vagy *.

sum([1, 2, 3, 4])   # 10

A Google is azt javasolja, hogy map, filter, reduce helyett használjunk listaértelmezéseket vagy for ciklust, jobban olvasható.

Az egymásba ágyazott ciklusok is helyettesíthetőek listaértelmezéssel.

for x in (1,2,3):
    for y in [1,2,3,4]:
        if x < y:
            print (x, y, x*y),
# (1, 2, 2) (1, 3, 3) (1, 4, 4) (2, 3, 6) (2, 4, 8) (3, 4, 12)

E helyett írható a következő kód:

[(x, y, x * y) for x in (1,2,3) for y in [1,2,3,4] if x < y]
# [(1, 2, 2), (1, 3, 3), (1, 4, 4), (2, 3, 6), (2, 4, 8), (3, 4, 12)]

Egy példa: a nyolc királynő

Feladat: Hányféleképp lehet nyolc királynőt föltenni egy sakktáblára, hogy semelyik kettő ne üsse egymást?

Azt tudjuk, hogy az ilyen bástyaelhelyezések száma 8! = 40320. A királynők azonban átlósan is üthetik egymást.

Az i-edik és j-edik sorban lévő királynő pontosan akkor üti egymást, ha abs(i - j) != abs(x[i] - x[j]). Így a megoldás:

from itertools import permutations
for x in permutations(range(8)):
    if all([i == j or abs(i - j) != abs(x[i] - x[j]) 
        for i in range(8) for j in range(8)]):
        print x

Generátorkifejezések

A listaértelmezésekhez hasonló szintaktikával (szögletes helyett kerek zárójelekkel) generátorkifejezés is konstruálható. Ez tehát a next() függvény meghívásakor számítja ki a következő elemet. Szintaktikája:

(kifejezés for elem in bejárható_objektum)
(kifejezés for elem in bejárható_objektum if feltétel)
(kifejezés for elem in bejárható_objektum1 if feltétel1
           for elem in bejárható_objektum2 if feltétel2
           for elem in bejárható_objektumN if feltételN)

A alábbi generátorkifejezés mindig a következő négyzetszámot adja:

>>> y = (x**2 for x in range(10))
>>> print y
<generator object <genexpr> at 0xb740bb6c>
>>> y.next()
0
>>> y.next()
1
>>> y.next()
4
>>> y.next()
9
.......
>>> y.next()
64
>>> y.next()
81
>>> y.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

A következő két program ekvivalens, az egyikben generátorkifejezéssel, a másodikban yield segítségével adunk meg olyan függvényt, mely az első n négyzetszámot generáló függvényt ad vissza.

>>> def kovetkezo_negyzet(n):
...     for x in range(n):
...         yield x ** 2
... 
>>> y = kovetkezo_negyzet(3)
>>> print y
<generator object kovetkezo_negyzet at 0xb740ba7c>
>>> y.next()
0
>>> y.next()
1
>>> y.next()
4
>>> y.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

A második változat generátorkifejezéssel:

>>> def kovetkezo_negyzet(n):
...     return (x ** 2 for x in range(n)) 
... 
>>> y = kovetkezo_negyzet(3)
>>> print y
<generator object <genexpr> at 0xb740baa4>
>>> y.next()
0
>>> y.next()
1
>>> y.next()
4
>>> y.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration