Funkcijsko programiranje u Pythonu

© 2005 Igor Pozgaj

Sadržaj

Što je funkcijsko programiranje
Liste
Funkcije
Rekurzija
Lambda izrazi
map()
filter()
reduce()
Primjeri

1. Što je funkcijsko programiranje

Danas su u programiranju dominantne dvije programske paradigme. Prva od njih i povijesno gledajući najstarija je imperativna (ili proceduralna) paradigma. Druga koja je danas vjerojatno najzastupljenija te koja se najčešče spominje je objektno orijentirana programska paradigma. Uz ove dvije paradigme, često se, a pomalo i nepravedno, zanemaruju programski jezici zasnovani na ponešto neuobičajenijim pristupima programiranju. To su programski jezici koji koriste funkcijsko programiranje te programiranje zasnovano na logici. Svrha ovog vrlo kratkog teksta je upoznati čitatelja sa najosnovnijim elementima funkcijskog programiranja koristeći sve popularniji programski jezik Python. Iako Python nije striktno gledajući funkcijski jezik, njegove mogućnosti za rad sa listama te ugrađeni idiomi funkcijskih jezika čine ga vrlo pogodnim za demonstriranje osnovnih načela u takvom pristupu programiranju. Znanje Pythona potrebno za razumjevanje ovog teksta svodi se na poznavanje najosnovnijih konstrukata jezika tako da svatko tko je imalo radio u Pythonu ne bi trebao imati problema sa razumijevanjem ičega iz ovog teksta.

Imperativna (tj. proceduralna) programska paradigma je jednostavna - program se sastoji od niza deklaracija, naredbi pridruživanja te poziva predefiniranih kao i vlastitih potprograma. Potprogrami omogućuju smisleno strukturiranje programa. Ovo je prirodan i vrlo pristupačan način programiranja i stoga je razumljivo da je upravo takav pristup korišten u prvim popularnim programskim jezicima poput Fortrana ili C-a. Problem sa ovakvim pristupom programiranju je sve veća kompleksnost današnjih programa: što je program veći - teže ga je održavati.

Kod objektno orijentiranog programiranja (OOP) program se sastoji od skupa objekata koji međusobno komuniciraju. Objekt je programski entitet koji je sposoban primati, obrađivati i slati poruke (poruke su programski najčešće realizirane običnim funkcijskim pozivima i callback funkcijama). Objektno orijentirani model je izuzetno pogodan za opisivanje današnjih sustava koji se najčešće sastoje od jasno odvojenih, samostalnih cjelina koje međusobno komuniciraju i razmjenjuju obrađene podatke. Jedan od takvih primjera koji se najčešće navodi je grafičko korisničko sučelje (GUI).

Temelj funkcijskog programiranja te funkcijske programske paradigme leži u izrazima i evaluacijama. Ta dva pojma se mogu smatrati centralnim objektima promatranja u funkcijskom programiranju. Program se sastoji on niza izraza i evaluacija, a nakon svake evaluacije smo bliže rješenju (potrebno je obaviti još evaluacija) ili smo došli do konačnog rješenja. Prilikom evaluacije se primjenjuju razne tehnike poput rekurzije i ugnježđivanja funkcija. Ovakav programski model je pogodan za efikasan opis raznih matematičkih izraza te algoritima. Pošto većina takvih izraza koristi liste i skupove, funkcijski jezici su najčešće orijentirani na rad sa listama.

Jedan od najpoznatijih te najstarijih programskih jezika koji podržavaju funkcijsko programiranje je LISP (List Procesor) te razni jezici nastali po uzoru na njega (jedna od poznatijih je Scheme). LISP je funkcijski jezik, ali u njemu je moguće koristiti i drukčije programske paradigme, na primjer objektnu. S druge strane, postoje jezici koji su striktno funkcijski i ne podržavaju druge programske paradigme. Takav je na primjer programski jezik Haskell. Programski jezik Python podrzava čak tri programske paradigme: objektno orijentirano, imperativno te funkcijsko programiranje. Neki od ostalih poznatih programskih jezika koji su funkcijski ili podržavaju funkcijsko programiranje su: ML, Erlang, Logo...

2. Liste

Liste su u Pythonu primitivni tip podataka i nije ih potrebno realizirati pomoću nekih druge strukture podataka. Prije korištenja listu je potrebno inicijalizirati. To se može napraviti na dva načina: prvi je kreiranje prazne liste, a drugi je inicijalizacija liste nekim vrijednostima:

>>> l = []
>>> l = [2, 5, 1, 3]

Liste nisu poput polja u drugim programskim jezicima i ne moraju nužno sadržavati elemente istog tipa, a uz to mogu sadržavati i druge liste:

>>> l = ['pero', 1, 2, ['ivica', 'mirko', ['crocop', 2], 2]]

Duljinu liste možemo saznati sa len(). Za prethodni primjer duljina je:

>>> len(l)
4

Na inicijaliziranoj listi dostupan je niz operacija i metoda. Na primjer, element se dodaje na kraj liste pomoću metode append()

>>> l.append(5)
>>> print l
[2, 5, 1, 3, 5]

Ispis liste smo mogli dobiti i samo navođenjem njenog imena (ovo naravno radi samo u interaktivnom načinu rada Python interpretera, dok je za ispis unutar programa potreban print).

Ukoliko je potrebno umetnuti novi član na specifično mjesto, a ne na kraj liste, onda koristimo metodu insert sintakse insert (pozicija, element). Numeriranje elemenata liste u Pythonu počinje sa nulom:

>>> l.insert (3, 7)
>>> l
[2, 5, 1, 7, 3, 5]

Metoda pop() uklanja i vraća zadnji element liste:

>>> l.pop()
5
>>> l
[2, 5, 1, 7, 3]

Indeks određenog elementa možemo dobiti na sljedeći način:

>>> l
[2, 5, 1, 7, 3]
>>> l.index(7)
3

Ako se u listi nalazi više istih elemenata, vraća se indeks prvog od njih (ovakvo ponašanje moguće je zaobići navođenjem drugog parametra u pozivu metode koji onda označava indeks od kojeg se počinje pretraživati, a ako se izostavi po definiciji je nula i pretražuje se od početka liste):

>>> l.append(7)
>>> l
[2, 5, 1, 7, 3, 7]
>>> l.index(7)
3
>>> l.index(7, 4)
5

Broj određenih elemenata u lista možemo dobiti pomoću funkcije count:

>>> l.count(7)
2

Pri uklanjanju elemenata liste, osim metode pop() možemo koristiti još dvije metode. Prva od njih služi za uklanjanje elementa iz liste po vrijednosti, a druga uklanja element po njegovom položaju (indeksu) u listi:

>>> l
[2, 5, 1, 7, 3, 7]
>>> l.remove(3)
>>> l
[2, 5, 1, 7, 7]
>>> del l[2]
>>> l
[2, 5, 7, 7]

I na kraju, dvije vrlo korisne metode su one za sortiranje i okretanje liste. Sortiranje u Pythonu je implementirano Merge sort algoritmom.

>>> l = [5, 2, 1, 4, 3]
>>> l.sort()
>>> l
[1, 2, 3, 4, 5]
>>> l.reverse()
>>> l
[5, 4, 3, 2, 1]

Kod rada sa listama u Pythonu treba imati na umu nekoliko stvari. Prva od njih je da se liste se mogu ugnježđivati:

>>> l = [1, 2, 3]
>>> l.append ([4, 5])
>>> l
[1, 2, 4, [4, 5]]

Pojedinom elementu liste možemo pristupiti putem indeksa (numeracija počinje od nule), koji mogu biti i negativni (u slučaju negativnih indeksa numeracija je takva da se numerira od kraja liste; -1 zadnji element liste, -2 predzadnji itd):

>>> l = [1, 2, 3, [4, 5]]
>>> l[3]
[4, 5]
>>> l[3][1]
5
>>> l[-1]
[4, 5]

Kod višestrukih lista potrebno je obratiti pažnju na način dodavanja elemenata u listu. Moguće je dodati kompletnu listu kao jedan element, a moguće je i dodati elemente liste svakog posebno:

>>> l = [1, 2, 3]
>>> l.extend ([4, 5])
>>> l
[1, 2, 3, 4, 5]
>>> l.append ([4, 5])
[1, 2, 3, 4, 5, [4, 5]]

Isti efekt ima i operator konkatenacije (spajanja) lista +:

>>> [1, 3] + [4, 5]
[1, 3, 4, 5]

Na listama je definiran i operator ponavljanja *:

>>> [1, 2] * 4
[1, 2, 1, 2, 1, 2, 1, 2]

Ovdje je važno primjetiti da sljedeći kod ne radi kako bi možda očekivali na prvi pogled

>>> l = [[0, 0], [0, 0]] * 2

Iako ovo na prvi pogled izgleda u redu, sljedeće pokazuje u čemu je problem:

>>> l[1][1] = 1
>>> l
[[0, 0], [0, 1], [0, 0], [0, 1]]

Ovakvo ponašanje u radu sa višestrukim listama je posljedica toga što Python tretira liste kao referencu, tako da operator ponavljanja zapravo stvara kopije referenci a ne vrijednosti samih polja.

Pri pristupanju pojedinim elementima koristili smo indeks. Međutim često se događa želimo koristiti više elemenata liste od jednom. To se postiže korištenjem odrezaka (eng. slices). Sintaksa njihovog korištenja je sljedeća:

ime_liste[početak:kraj]

Važno je i napomenuti da je prvi argument uključiv a drugi isključiv te je dozvoljeno ispustiti jedan ili oba argumenta unutar zagrada, pri čemu je onda podrazumjevan početak odnosno kraj liste. Na primjer:

>>> l = [1, 2, 3, 4, 5]
>>> l[2:4]
[3, 4]
>>> l[2:-2]
[3]
>>> l[:3]
[1, 2, 3]
>>> l[2:]
[3, 4, 5]
>>> l[:]
[1, 2, 3, 4, 5]

Jedan od važnijih načina korištenja lista i notacije lista u Pythonu u kontekstu funkcijskog programiranja je korištenje sljedećeg oblika

[... for ... in ... if ...].

Pretpostavimo da imamo listu brojeva koje sve želimo pomnožiti sa dva. Standardni pristup (imperativni) bi uključivao iteriranje svih članova liste i njihovo množenje sa dva. Međutim, funkcijski pristup je mnogo elegantniji:

>>> lista = [2, 5, 1, 3, 6]
>>> [x * 2 for x in lista]
[4, 10, 2, 6, 12]

Ukoliko smo ovo željeli napraviti samo za one članove liste koji su veći od 2, mogli smo koristiti sljedeći izraz:

>>> lista = [2, 5, 1, 3, 6]
>>> [x * 2 for x in lista if x > 2]

Rezultat ovakve evaluacije je nova lista. Još jedan primjer mogao bi biti inkrement svih elemenata liste:

>>> a = [1, 2, 3]
>>> [a + 1 for a in brojevi]
[2, 3, 4]

3. Funkcije

Funkcije se u Pytonu definiraju na sljedeći način:

def ime_funkcije (argument1, argument2...):
	tijelo_funkcije

Bitno je napomenuti nekoliko stvari: lista argumenata može biti prazna. Tijelo funkcije ne može biti prazno i mora sadržavati barem jedan izraz (npr. pass - prazna naredba). Argumenti mogu imati i podrazumjevanje vrijednosti, a u tome slučaju moraju se nalaziti na kraju popisa argumenata funkcije . Funkcija vraća vrijednost pomoću ključne riječi return. Slijede primjeri definicije nekih funkcija kao primjer gore navedenih činjenica o funkcijama u Pythonu:

def nop():
	pass

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

def uvecaj(x, y = 1):
	return x + y

U posljednjem slučaju funkciju je moguće pozvati na dva načina:

>>> uvecaj (4)
5
>>> uvecaj (4, 2)
6

4. Rekurzija

Jedan od vrlo važnih koncepata u funkcijskom programiranju je rekurzija. Razlikujemo dvije vrste rekurzije: direktnu i indirektnu. Kod direktne rekurzije funkcija poziva samu sebe, dok se kod indirektne rekurzije dvije ili više funkcija pozivaju međusobno. Pri tome je vrlo važno paziti na to da se rekurzija jednom mora i završiti, jer će se u protivnome pozivanje odvijati u beskonačnost (dokle god to memorijski prostor rezerviran za programski stog dopušta).

Školski primjer za definiranje rekurzije su faktorijele. Faktorijela se definira induktivno na sljedeći način:

0! = 1
1! = 1 * 0! = 1
2! = 2 * 1! = 2 * 1
3! = 3 * 2! = 3 * 2 * 1

Tako bi na primjer bilo:

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

Matematički ovo možemo zapisati na sljedeći način:

n! = n * (n-1)     i      0! = 1

Odavde sljedi direktna implementacija u Pythonu

def fact (n):
	if n == 0:
		return 1
	return n * fact(n-1)

>>> fact(10)
3628800

Još jedan primjer bi mogao biti i provjeravanje da li se određeni element nalazi u listi (ovo je naravno samo akademski primjer, za to se inače koristi ugrađeni Pythonov operator in):

def is_in (lista, x):
	if (lista == []):
		return 0
	if (x == lista[0]):
		return 1
	return is_in (lista[1:], x)

Međutim, treba biti iznimno oprezan kada je rekurzija dobar izbor. Dok bi u gornja dva primjera korištenje rekurzije bilo prihvatljivo, u sljedećem primjeru sa Fibonaccijevim brojevima rekurzija daje katastrofalno spori algoritam eksponencijalne složenosti:

Fibonaccijevi brojevi su definirani rekurzivno na sljedeći način:

F(1) = F(2) = 1
F(n) = F(n-1) + F (n-2)         za n > 2

U Pythonu to izgleda ovako:

def F(n):
	if n == 1 or n == 2:
		return 1
	return F(n-1) + F(n-2)

Iako ovo na prvi pogleda izgleda korektno (a i je korektno), ovakvo je računanje Fibonaccijevih brojeva iznimno neefikasno. Dok bi se računanjem u npr. for petlji rezultat za veće brojeve dobio gotovo trenutno, rekurzijom bi morali pričekati nekoliko godina (moguće i stoljeća). Probajte na primjer razmisliti koliko bi se puta računao F(5) kod poziva F(50).

5. Lambda izrazi

Lambda izrazi služe za definiranje kratkih anonimnih funkcija. Takve funkcije obično služe za definiciju drugih funkcija, oblikovanje novih funkcija tijekom izvođenja programa te za kraći zapis drugih izraza u funkcijskom programiranju. Sintaksa lambda izraza je sljedeća:

lambda popis_varijabli: izraz

Sljedeći primjer prikazuje definiciju funkcije pomoću lambda izraza:

>>> f = lambda x: x*x
>>> f
 at 0x40365f0c>
>>> f(5)
25

Slijedi i jedan kompliciraniji primjer. Funkciju iz prethodnog poglavlja za inkrement u kojoj smo koristili opcionalne parametre napisat ćemo ponovno sa lambda izrazima:

def napravi_inkrement_funkciju (n):
return lambda x: x + n

>>> f = napravi_inkrement_funkciju (10)
>>> f(1)
11

Lambda izraz može sadržavati i više varijabli. Na primjer, za slučaj tri varijable:

diskriminanta = lambda a, b, c: b * b - 4 * a * c

Prava efikasnost lambda izraza dolazi do izražaja kod korištenja funkcija map, reduce i filter koje su opisane u sljedećim poglavljima.

6. map()

map() je funkcija koja preuređuje (mapira) svaki element liste koristeći navedenu funkciju. Na primjer, u zadanoj listi potrebno je sve elemente pomnožiti sa dva:

>>> lista = range (10)
>>> lista
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> map (lambda x: x*2, lista)
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

Ovdje do izražaja dolazi prava snaga lambda izraza jer bi bilo suvišno i zamorno definirati novu funkciju samo za ovakvu primjenu. Još jedan primjer iz stvarnog svijeta bi bio sljedeći: često se u aplikacijama koje koriste puno matematičkih proračuna koriste lookup tablice. Na primjer, umjesto da se svaki puta koristi FPU za računanje funkcije sinus, možemo prije izvođenja glavnog dijela programa izračunati sve potrebne vrijednosti, a kasnije samo čitati njihove vrijednosti iz liste:

>>> import math
>>> sinusi = range (360)
>>> sinusi = map (lambda x: math.sin (x), sinusi)

Prema prijedlogu novog nacrta programskog jezika Python (Python 3000), ova funkcija će kako stvari sada stoje biti izbačena iz definicije jezika. Razlog tome leži u činjenici da istu funkcionalnost kao

map [funkcija, lista]

ima i operacija sa listom:

[funkcija (element) for element in lista]

Koji od prethodna dva zapisa je elegantniji i ljepši ostavljam na prosudbu čitatelju - tvorci Pythona su se ionako već odlučili za ovaj drugi. Nova definicija jezika kako stvari sada stoje neće biti usvojena tako brzo, tako da možete koristiti oba zapisa bez bojazni o portabilnosti programa.

7. filter()

Funkcija filter() služi za uklanjanje (filtriranje) pojedinih elemenata iz liste. Kao i funkcija map, filter prima dva parametra. Prvi je funkcija koja se primjenjuje, a drugi je lista na koju se ta funkcija primjenjuje. Ukoliko funkcija vrati True, element ostaje u listi, inače se izbacuje. Česti primjer je izbacivanje parnih brojeva iz liste:

>>> lista = range (10)
>>> filter (lambda x: x%2, lista)
[1, 3, 5, 7, 9]

Kao i funkcija map, i ova funkcija će biti izbačena kod sljedeće velike preinake Pythona. Tako smo sljedeći primjer mogli zapisati i na ovaj način:

>>> [x for x in range (10) if x%2]
[1, 3, 5, 7, 9]

8. reduce()

Kao i prethodne dvije funkcije i ova prima dva parametra: funkciju i listu. Međutim, funkcija koja se poziva unutar reduce() mora primati dva parametra. Zatim se ta funkcija primjenjuje na posljednja dva elementa liste, ta dva elementa se zamjenjuju rezultatom evaluacije funkcije, te se proces nastavlja dok u listi ne ostane samo jedan element. Ovo vjerojatno zvuči komplicirano, ali namjena reduce() se može vidjeti na sljedeća dva primjera. Prvi primjer je pronalaženje maksimalnog elementa u listi:

>>> lista = [2, 5, 1, 3]
>>> reduce (lambda x,y: max(x,y), lista)
5

Naravno, mogli smo odmah dobiti traženi element sa:

>>> max (lista)
5

no to nije smisao gornjega primjera. Sljedeći bi primjer bio "naći zbroj svih elemenata liste":

>>> lista = [2, 5, 1, 3]
>>> reduce (lambda x,y : x+y, lista)
11

Na ovome primjeru ćemo detaljno pokazati kako reduce radi: lambda izraz će vratiti zbroj parametara koje je primila. Privremena lista koja nastaje tijekom evaluacije reduce() izraza izgleda ovako:

[2, 5, 1, 3]
[2, 5, 4]
[2, 9]
[11]

Pošto je 11 jedini preostali element u listi, reduce() gra vraća kao rezultat evaluacije. Važno je napomenuti da sve tri navedene funkcije (map, filter i reduce) ostavljaju listu koja je navedeno kao parametar netaknutim (vraćaju novu listu).

I ovu funkcija će biti izbačena u sljedećoj velikoj preinaci Pythona.

9. Primjeri

Jedan od često korištenih primjera za demonstraciju funkcijskog programiranja je Quicksort. Podsjetimo se kako izgleda quicksort algoritam:

1. izaberi stožerni element u listi
2. podijeli listu na dvije podliste 
3. u prvu podlistu stavi sve elemente liste manje od stozernog elementa
4. u drugu podlistu stavi sve elemente liste vece od stozernog elementa
5. Ponavljaj korake 1 do 4 za dobivene podliste sve dok ne dobiješ praznu listu

Radi jednostavnosti, pretpostavit ćemo da je stožerni element prvi element liste. Quicksort u Pythonu koristeći funkcijsko programiranje izgleda ovako:

def quicksort (lista):
if lista==[]: return []
	return qsort([x for x in L[1:] if x< L[0]]) + L[0:1] + \ 
		qsort([x for x in L[1:] if x>=L[0]])

Jeste li ikada vidjeli elegantnije i kraće napisani quicksort? :)