Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

PROGRAMIRANJE U HASKELLU

Ak.god. 2011/12.

LEKCIJA 6: rekurzivne funkcije

v1.2

(c) 2011 Jan Šnajder

==============================================================================

> import Data.Char
> import Data.List

Rekurzija: funkcija poziva samu sebe.

U funkcijskim jezicima mnogo problema rješavamo rekurzivno. Ideja: problem
razlomiti na jednostavnije podprobleme i pokušati riješiti te podprobleme.

Najjednostavniji slučaj zovemo "osnovnim slučajem".

Tipičan primjer je izračun faktorijele:

> fact :: Num a => a -> a
> fact x = if x==0 then 1 else x * fact (x-1)

Ili, bolje:

> fact' :: Num a => a -> a
> fact' 0 = 1
> fact' x = x * fact' (x-1)

Drugi tipičan primjer je izračun Fibonaccijevog broja:

> fib 0 = 0
> fib 1 = 1
> fib n = fib (n-1) + fib (n-2)

(Ova definicija nije baš jako dobra. Znate li zašto?)

Haskellaši su vrlo ponosni na definiciju quicksorta:

> quicksort :: (Ord a) => [a] -> [a]
> quicksort [] = []
> quicksort (x:xs) = quicksort ys ++ [x] ++ quicksort zs
>   where ys = [y | y <- xs, y <= x]
>         zs = [z | z <- xs, z  > x]

U nastavku se fokusiramo na rekurziju po podatkovnoj strukturi. Tipično je to
lista ili stablo. Takvu rekurziju nazivamo "strukturna rekurzija". Strukturna
rekurzija služi za obradu podatkovne strukture (koju bi u imperativnom jeziku
radili pomoću petlje). 

Osnovna ideja: spuštanje po strukturi način da je postepeno rastavljamo pomoću
podudaranja uzoraka.

> sum' :: Num a => [a] -> a
> sum' []     = 0
> sum' (x:xs) = x + sum' xs

> length' :: [a] -> Int
> length' []     = 0
> length' (_:xs) = 1 + length' xs

> incList :: Num a => [a] -> [a]
> incList []     = []
> incList (x:xs) = x + 1 : incList xs

Ovo posljednje znamo napraviti puno kraće pomoću sažetog zapisa liste. (Kako?)

> concat' :: [[a]] -> [a]
> concat' []       = []
> concat' (xs:xss) = xs ++ concat' xss

> maximum' :: Ord a => [a] -> a
> maximum' [x]    = x
> maximum' (x:xs) = x `max` maximum' xs

(Što se događa ako ovu funkciju pozovemo s praznom listom?)

Koja je vremenska složenost gornjih funkcija (osim 'fib')?

Za liste duljine 'n', vremenska složenost je O(n).

Primijetite da u gornjim funkcijama postoji nekakav obrazac koji se ponavlja:

foo ...                             <-- osnovni slučaj
foo (x:xs) = f x `operator` foo xs  <-- općenit slučaj 

=== VJEŽBA 1 =================================================================

1.1.
- Napišite rekurzivnu funkciju za produkt elemenata liste.
  product' :: Num a => [a] -> a

1.2.
- Napišite rekurzivnu funkciju 'headsOf' koja uzima listu listi i vraća listu
  glava.  
  headsOf :: [[a]] -> [a]

==============================================================================

Rekurzivna funkcija može naravno imati više argumenata. Argumente koje ne
mijenjamo (koji su isti u svakom rekurzivnom pozivu) služe samo za čuvanje
stanja (tzv. varijable konteksta):

> addToList :: Num a => a -> [a] -> [a]
> addToList _ []     = []
> addToList n (x:xs) = x + n : addToList n xs

Naravno, ako treba, možemo varijable u svakom rekurzivnom pozivu mijenjati:

> incIncList :: Num a => a -> [a] -> [a]
> incIncList _ []     = []
> incIncList n (x:xs) = x + n : incIncList (n+1) xs

Što ako želimo napisati funkciju koja povećava elemente liste, ali uvijek tako
da inkrement za prvi element bude 0, za drugi 1, itd?

incIncList' [3,2,1] => [3,3,3]

Ne želimo da korisnik uvijek mora pisati 0 kao argument.  Umjesto toga pišemo
funkciju-omotač (wrapper function):

> incIncList' :: Num a => [a] -> [a]
> incIncList' xs = inc 0 xs
>   where inc _ []     = []
>         inc n (x:xs) = x + n : inc (n+1) xs

=== VJEŽBA 2 =================================================================

2.1.
- Napišite funkciju koja svaki element liste množi s 'n' modulo 'm'.

2.2.
- Napišite funkciju 'addPredecessor' koja svakom elementu liste dodaje
  vrijednost prethodnog elementa. Prvom elementu treba dodati vrijednost 0.
  addPredecessor :: Num a => [a] -> [a] 
  addPredecessor [3,2,1] => [3,5,3]

==============================================================================

U rekurzivnom slučaju možemo provjeravati uvjete i postupati u skladu s time.
Tako možemo napraviti filtriranje liste:

> numPositives :: (Num a, Ord a) => [a] -> Int
> numPositives []     = 0
> numPositives (x:xs) | x > 0     = 1 + numPositives xs
>                     | otherwise = numPositives xs

=== VJEŽBA 3 =================================================================

3.1.
- Napišite funkciju 'equalTriplets'
  koja iz liste trojki filtrira sve trojke (x,y,z) za koje x==y==z.

3.2.
- Napišite funkciju replicate' :: Int -> a -> [a]

==============================================================================

Napišimo funkciju 'take':

> take' :: Int -> [a] -> [a]
> take' _ []     = []
> take' 0 _      = []
> take' n (x:xs) = x : take' (n-1) xs

Radi li ova funkcija ispravno za n<0 (vraća li nepromijenjenu listu)?

Kako nadograditi da, ako je n > length xs, da se ponavlja posljednji element iz xs? 
take'' 5 [1,2,3] => [1,2,3,3,3]

Kako bi takvu funkciju napravili pomoću gotovih funkcija iz Prelude ?

=== VJEŽBA 4 =================================================================

4.1.
- Napišite rekurzivnu funkciju drop' :: Int -> [a] -> [a]. 
- Proširite (napravite omotač) tako da za n<0 funkcija odbacuje elemente s
  kraja liste. Možete koristiti 'reverse'.

4.2.
- Napišite rekurzivnu funkciju 'takeFromTo n1 n2 xs'.
  takeFromTo :: Int -> Int -> [a] -> [a]

==============================================================================

Izvedba funkcije 'zip':

> zip' :: [a] -> [b] -> [(a,b)]
> zip' []     _      = []
> zip' _      []     = []
> zip' (x:xs) (y:ys) = (x,y) : zip' xs ys

Kako proširiti da povezuje samo dvojke (x,y) za koje x==y ?

Ne moramo uvijek obrađivati jedan po jedan element. Npr. funkcija koja uzima
listu i vraća parove po dva elementa:

> pairUp :: [a] -> [(a,a)]
> pairUp (x:y:xs) = (x,y) : pairUp xs
> pairUp _        = []

=== VJEŽBA 5 =================================================================

5.1.
- Napišite rekurzivnu funkciju 'eachThird' koja iz liste filtrira svaki 
  treći element.

5.2.
- Napišite rekurzivnu funkciju koja "križno" zipa dvije liste na sljedeći način:
  crossZip [1,2,3] [4,5,6] => [(1,5),(2,4)]

=== AKUMULATORSKI PARAMETAR ==================================================

Pogledajmo opet definiciju faktorijele:

> fact1 :: Num a => a -> a
> fact1 0 = 1
> fact1 x = x * fact1 (x-1)

Funkcija se izvodi ovako: idemo u dubinu dok ne "udarimo" u osnovni slučaj, a
onda gradimo rješenje vraćajući se nazad korak po korak. Zapravo rješenje
gradimo pri povratku.

Moguće je i drugačije rješenje kod kojeg idemo u dubinu, u svakom koraku dok
idemo u dubinu "akumuliramo" rješenje, i kad "udarimo" u osnovni slučaj odmah
vratimo rješenje koje smo akumulirali.

> fact2 :: Num a => a -> a -> a     -- drugi argument je akumulator
> fact2 0 n = n
> fact2 x n = fact2 (x-1) (x*n)

Treba nam omotač koji će postaviti inicijalnu vrijednost (koja je jednaka
jedinici):

> fact3 :: Num a => a -> a
> fact3 n = fact2 n 1

Sve rekurzivne funkcije do sada definirali smo s "običnom" rekurzijom (bez
akumulatora). Mnoge od njih možemo napisati pomoću akumulatora. Dakle, umjesto:

> sum1 :: Num a => [a] -> a
> sum1 []     = 0
> sum1 (x:xs) = x + sum1 xs

> sum2 :: Num a => [a] -> a
> sum2 xs = sum xs 0
>   where sum []     s = s              -- 's' je akumulator
>         sum (x:xs) s = sum xs (x+s)

Ali, čemu to? Zar nije svejedno?

Nije. Definicije s akumulatorom u načelu su manje računalne složenosti
(prostorne, a nekad i vremenske).

Objašnjenje:

U načelu, ako je rekurzivni poziv dio većeg izraza, onda znači da u svakom
rekurzivnom pozivu moramo najprije rekurzivno pozvati funkciju, pa tek kad se
ona vrati onda možemo izračunati vrijednost cijelog izraza. Konceptualno, to
znači da postepeno gradimo sve veći i veći izraz, koji počinjemo smanjivati tek
kad dosegnemo osnovni slučaj. (Tehnički se to ostvaruje tako da kod rekurzivnog
poziva na stog pohranimo kontekst i povratnu adresu.) Taj izraz će rasti s
dubinom rekurzivnog poziva. Ako rekurziju imamo na samo jednom mjestu, a
izvodimo je 'n' puta, onda će prostorna složenost biti O(n).

Ako rekurzivni poziv nije dio većeg izraza, onda ne gradimo sve veći i veći
izraz (niti nije potrebno stavljati povratnu adresu na stog). Umjesto toga
možemo samo pozivati funkciju ispočetka s novim parametrima (kao GOTO s
parametrima).  Takve funkcije zovemo "repno rekurzivnima" (engl. tail
recursive). Kompajler će to detektirati i napraviti optimizaciju koda (tail
call optimization). Ne moramo ništa pohranjivati na stog pa je složenost O(1).

Dakle: 'sum1' ima prostornu složenost O(n), a 'sum2' prostornu složenost O(1).

(Ovo objašenjenje uzmite s rezervom jer kod Haskella nije baš to tako
jednostavno, pored ostaloga i zato što je Haskell lijen jezik. Zbog toga nam u
Haskellu baš i nije tako jako bitno je li funkcija repno rekurzivna. Ali za
sada nećemo ulaziti u te detalje.)

Napravimo akumulatorsku definiciju za 'maximum'. Obična verzija je:

> maximum1 :: Ord a => [a] -> a
> maximum1 []  = error "empty list"
> maximum1 [x] = x
> maximum1 (x:xs) = x `max` maximum' xs

Izvedba s akumulatorom:

> maximum2 :: (Ord a, Num a) => [a] -> a
> maximum2 [] = error "empty list"
> maximum2 xs = maximum xs 0
>   where maximum []     m = m
>         maximum (x:xs) m = maximum xs (max x m)

Loše je što smo se obvezali raditi s numeričkim tipom. Evo malo općenitije
varijante:

> maximum3 :: (Ord a, Bounded a) => [a] -> a
> maximum3 [] = error "empty list"
> maximum3 xs = maximum xs minBound
>   where maximum []     m = m
>         maximum (x:xs) m = maximum xs (max x m)

Ali mnogo je bolje:

> maximum4 :: (Ord a) => [a] -> a
> maximum4 []     = error "empty list"
> maximum4 (x:xs) = maximum xs x
>   where maximum []     m = m
>         maximum (x:xs) m = maximum xs (max x m)

Razlika je drastična kod funkcije 'reverse'. Obična rekurzivna izvedba:

> reverse1 :: [a] -> [a]
> reverse1 []     = []
> reverse1 (x:xs) = reverse1 xs ++ [x]

Prostorna složenost je O(n). Vremenska složenost je O(n^2) (zašto?).

Izvedba s akumulatorom:

> reverse2 :: [a] -> [a]
> reverse2 xs = rev xs []
>   where rev []     ys = ys
>         rev (x:xs) ys = rev xs (x:ys)

Koja je računalna složenost ove funkcije?

Prednost akumulatora je također to što je nekada lakše razmišljati na takav
način (bliže je imperativnom stilu).

No nekada uporaba akumulatora nema smisla.

Npr. kada radimo strukturnu rekurziju po listi i slijedno modificiramo elemente
na neki način. Primjer je funkcija 'incList': 

> incList1 :: Num a => [a] -> [a]
> incList1 []     = []
> incList1 (x:xs) = x + 1 : incList1 xs

Napomena: prostorna složenost ove funkcije je O(1) (konstruirana lista koja je
rezultat se ne ubraja u prostornu složenost; u prostornu složenost ubraja se
samo dodatno potreban prostor, kojeg ovdje nema).

> incList2 :: Num a => [a] -> [a]
> incList2 xs = inc xs []
>   where inc []     ys = ys 
>         inc (x:xs) ys = inc xs ((x+1):ys)

Problem je u tome što u listu možemo dodavati samo na početak. U akumulatoru
dobivamo obrnutu listu. To je bilo ok za 'reverse', ali tu nije dobro. U ovom
slučaju dakle akumulatorsko rješenje nema smisla. Njime se ionako ništa ne
dobiva (prostorna složenost obje funkcije je O(1)).

Sličan primjer je 'unzip'. Možemo probati s akumulatorima:

> unzip' :: [(a,b)] -> ([a],[b])
> unzip' zs = unz zs [] []
>   where unz []         xs ys = (xs,ys)
>         unz ((x,y):zs) xs ys = unz zs (x:xs) (y:ys)

Ovo opet nije dobro jer dobivamo obrnute liste. Mogli bismo prvo obrnuti listu,
ali to znači da nam trebaju dva prolaza po listi (jedan za obrtanje i jedan za
unzip).

Obična rekurzija:

> unzip'' :: [(a,b)] -> ([a],[b])
> unzip'' []         = ([],[])
> unzip'' ((x,y):zs) = (x:xs,y:ys)
>   where (xs,ys) = unzip'' zs

=== VJEŽBA 6 =================================================================

6.1.
- Napišite rekurzivnu definiciju s akumulatorom za
  length :: [a] -> Int

6.2
- Napišite rekurzivnu definiciju s akumulatorom za 
    maxUnzip :: [(Int,Int)] -> (Int,Int) 
  koja vraća maksimalan element na prvoj poziciji i maksimalan element na
  drugoj poziciji para, tj. radi kao:
    maxUnzip zs = (maximum xs, maximum ys)
      where (xs,ys) = unzip zs
  Javite grešku "empty list" za praznu listu.
- Napišite običnu rekurzivnu verziju (bez akumulatora).

=== KOREKURZIJA ==============================================================

Korekurzija je "dualna" rekurziji: umjesto da rekurzivnim pozivima rastavljamo
strukturu, mi je gradimo. Struktura koju gradimo može biti konačna ili
beskonačna. Naravno, zato što je Haskell lijen, neće se odmah izgraditi cijela
struktura, nego će se graditi samo onoliko koliko treba.

> ones :: [Integer]
> ones = 1 : ones

> cycle' :: a -> [a]
> cycle' x = x : cycle' x

U svakom koraku za daljnju izgradnju strukture možemo iskoristiti dio već
izgrađene strukture. 

Lista prirodnih brojeva:

> nats :: [Integer]
> nats = 0 : next nats
>   where next (x:xs) = x + 1 : next xs

Malo složenije: lista Fibonaccijevih brojeva:

> fibs :: [Integer]
> fibs = 0 : 1 : next fibs
>   where next (x:ys@(y:_)) = (x+y) : next ys