Liste

Liste u Haskelu su homegene strukture podataka, što znači da mogu sadržati vrednosti samo jednog tipa (npr. samo brojeve ili samo logičke vrednosti). Liste se konstruišu navođenjem vrednosti unutar uglastih zagrada, npr. [x1, x2, x3, x4, x5].

Funkcije za rad sa listama

U prethodnim lekcijama već smo se upoznali sa nekim funkcijama za rad sa listama:

  1. (++) :: [a] -> [a] -> [a] spaja dve liste
  2. length :: [a] -> Int vraća dužinu liste
  3. elem :: Eq a => a -> [a] -> Bool ispituje da li se element nalazi u listi
  4. reverse :: [a] -> [a] obrće poredak elemena u listi
  5. head :: [a] -> a vraća prvi element liste. Ako je lista prazna dolazi do izuzetka
  6. init :: [a] -> a vraća sve elemente osim poslednjeg. Ako je lista prazna dolazi do izuzetka
  7. tail :: [a] -> a vraća sve elemente osim prvog. Ako je lista prazna dolazi do izuzetka
  8. last :: [a] -> a vraća poslednji element. Ako je lista prazna dolazi do izuzetka

Primetimo da sve navedene funkcije osim funkcije elem, mogu se koristiti sa listom proizvoljnog tipa. Funkcija elem se može koristiti samo sa instancama Eq klase1.

Prelude obezbeđuje još neke funkcije za rad sa listama karaktera:

  1. words :: [Char] -> [[Char]] deli nisku na listu niska pri čemu se prelom vrši na belinama. Na primer: words "a bb ccc " daje ["a", "bb", "ccc"]. Samo ime funkcije ukazuje da se od jedne nikse dobijaju "reči".
  2. unwords :: [[Char]] -> [Char] spaja listu niski u jedinstvenu nisku dodavajući razmak između. Na primer: unwords ["boža", "zvani", "pub"] nam daje "boža zvani pub".
  3. lines :: [Char] -> [[Char]] rastavlja nisku na linije, vršeći prelom na karakteru za novi red '\n'.
  4. unlines :: [[Char]] -> [Char] spaja listu niski u jedinstvenu nisku, dodavajući '\n' između.

Ovde je zgodno napomenuti kako se u Haskel kodu mogu navesti niske u više redova. Neophodno je na kraju i početku svake linije koja pripada nisci dodati znak \, osim u prvoj i poslednjoj na mestima gde je ":

pesma :: [Char]
pesma = "Ti, međutim, rasteš, uz zornjaču jasnu,\
\sa Avalom plavom, u daljini, kao breg.\
\Ti treperiš, i kad ovde zvezde gasnu,\
\i topiš, ko Sunce, i led suza, i lanjski sneg." 

Ipak, ovako definisana niska neće sadržati karaktere za novi red! Neophodno ih je ručno dodati na svakom mestu:

pesma :: [Char]
pesma = "Ti, međutim, rasteš, uz zornjaču jasnu,\n\
\sa Avalom plavom, u daljini, kao breg.\n\
\Ti treperiš, i kad ovde zvezde gasnu,\n\
\i topiš, ko Sunce, i led suza, i lanjski sneg.\n" 

Ako u GHCi interpreteru evaluiramo vrednost pesma, niska će se ispisati unutar dvostrukih navodnika u jednoj (ali dugačkoj) liniji terminala2. Probajte i uverite se sami. Zbog toga je zgodno iskoristi metod putStr koji sadržaj ispisuje u terminal onako kao bismo i očekivali:

ghci> putStr pesma
Ti, međutim, rasteš, uz zornjaču jasnu,
sa Avalom plavom, u daljini, kao breg.
Ti treperiš, i kad ovde zvezde gasnu,
i topiš, ko Sunce, i led suza, i lanjski sneg.

Rasponi

Neretko se javlja potreba da se konstruiše lista poput liste prirodnih brojeva od \(1\) do \(n\) ili liste brojeva od \(-n\) do \(n\) itd... Iako nije teško implementirati rekurzivne funkcije koje vraćaju ovakve liste, Haskel jezik poseduje sintaksu za raspone3 koja značajno olakšava konstrukciju ovakvih lista. Raspon se konstruiše navođenjem prvog i poslednjeg elementa liste, između kojih se postavljaju dve (spojene) tačke. Naredni primeri ilustruju sintaksu raspona:

ghci> a = [1 .. 10]
ghci> a
[1,2,3,4,5,6,7,8,9,10]
ghci> [-3 .. 3]
[-3,-2,-1,0,1,2,3]
ghci> [10 .. 1]
[]
Ako je poslednji element manji od prvog, tada će biti konstruisana prazna lista.

Sa rasponima je moguće konstruisati i liste u kojima je korak različit od \(1\). U tom slučaju, potrebno je navesti i drugi član liste na osnovu koga će korak biti izračunat.

ghci> [1, 3 .. 11]
[1,3,5,7,9,11]
ghci> [0, 10 .. 100]
[0,10,20,30,40,50,60,70,80,90,100]
ghci> [1, 5 .. 11]
[1,5,9]
Primetimo u poslednjem primeru da lista uključuje sve brojeve aritmetičke progresije manje 11. Dakle, gornja granica respona ne mora biti uključena u listu.

Navođenjem koraka progresije moguće je lako konstruisati liste i koje su opadajuće:

ghci> [10, 9 .. 1]
[10,9,8,7,6,5,4,3,2,1]

Rasponi se takođe mogu koristiti i sa racionalnim brojevima:

ghci> [1.0 .. 5.0]
[1.0,2.0,3.0,4.0,5.0]
ghci> [1.0, 1.5 .. 5.0]
[1.0,1.5,2.0,2.5,3.0,3.5,4.0,4.5,5.0]

Ipak, treba biti pažljiv pri korišćenju raspona racionalnih brojeva, jer se računska greška4 može brzo ukazati

ghci> [0.1, 0.3 .. 1]
[0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]

Opsezi dozvoljavaju samo definisanje aritmetičkih progresija. Za definisanje geometrisjke (ili neke druge progresije), korisnik će morati sam da implementira odgovarajuće funkcije.

Međutim, rasponi mogu da se koriste i sa tipovima koji nisu numerički. Na primer, rasponi karaktera su često korisni

ghci> ['A' .. 'W']
"ABCDEFGHIJKLMNOPQRSTUVW"
ghci> ['a' .. 'd']
"abcd"
ghci> ['a', 'c' .. 'w']
"acegikmoqsuw"
Lista karaktera je naravno niska te se ['a', 'b', 'c', 'd'] prikazuje kao "abcd" u terminalu.

Da bi neki tip mogao da se koristi sa rasponima, mora pripadati tipskoj klasi Enum. Ova klasa sadrži sve tipove čije vrednosti se mogu enumersati. Svaki tip a iz Enum klase mora da implementira funkcije fromEnum :: a -> Int i toEnum :: Int -> a koje redom kodiraju i dekodiraju vrednosti tog tipa kroz cele brojeve. Vrednosti dobijene ovim kodiranjem korsite se za konstrukciju opsega.

Primer 1.

Tip Char pripada klasi Enum. Funkcija fromEnum primenjena na karakter vraća poziciju tog karaktera u Unicode tabeli.

ghci> fromEnum 'a'
97
ghci> toEnum 100 :: Char
'd'
Kako je toEnum tipa Int -> a kompajler ne može zaključiti tip izraza toEnum 100 (na koji instancu Enum klase se ovaj izraz odnosi?). Zbog toga je neophodno eksplicitno deklaristai tip izraza. Više o ovome kasnije...

Kada napišemo raspon poput ['a', 'c' .. 'g'], taj raspon se tumači kao raspon [fromEnum 'a', fromEnum 'c' .. fromEnum 'g'], odnosno kao [97, 99 .. 103]. Time se dobija lista [97,99,101,103] koja se primenom funkcije toEnum na svaki od elemenata transformiše u listu "aceg".

Zadatak 1. Napisati funkciju velikoSlovo :: Char -> Bool koja proverava da li je uneto slovo veliko latinično.

Možemo iskoristi funkciju elem koja proverava da li element pripada listi.

velikoSlovo :: Char -> Bool
velikoSlovo c = elem c ['A' .. 'W'] 

Podudaranje oblika liste

Tehnika podudaranja oblika je veoma korisna pri radu sa listama. Tada lako možemo da uhvatimo praznu, jednočlanu, dvočlanu listu, itd... ili da rastavimo listu na glavu i rep.

Primer 2.

Funkciju koja proverava da li je lista celih brojeva prazna5, možemo definisati na sledeći način:

prazan :: [Int] -> Bool
prazan [] = True
prazan x = False
Slučaj prazne liste je uhvaćen sa oblikom [], dok su svi ostali slučajevi obuhvaćeni generičkim promenljivom x.

Neophodno je obuhvatiti sve moguće oblike promenljive. Ako se neki od oblika izostavi, definisana funkcija neće biti totalna, i za neke od argumenata će doći do izuzetka:

prazan' :: [Int] -> Bool
prazan' [] = True
ghci> prazan' [1, 2, 3]
*** Exception: main.hs:3:1-15: Non-exhaustive patterns in function prazan'

Na primer, ako želimo da napišemo funkciju s :: [Int] -> Int koja praznoj listi dodeljuje \(0\), jednočlanoj listi dodeljuje element te liste, dvočlanoj listi dodeljuje zbir dva elementa, a svim ostalim listama dodeljuje \(1\), korišćenjem guards sintakse dobijamo naredni kod:

s :: [Int] -> Int
s xs 
  | xs == [] = 0
  | len xs == 1 = xs !! 0
  | len xs == 2 = xs !! 0 + xs !! 1
  | otherwise = 1

Korišćenjem podudaranja oblika dobijamo elegantniji kod:

s :: [Int] -> Int
s [] = 0
s [x] = x
s [x, y] = x + y
s _ = 1

Kao što vidimo, podudaranjem oblika liste dekonstruisali smo neke moguće oblike argumenta funkcije. U trećoj liniji definisali smo funkciju u slučaju kada je njen argument jednočlana lista [x]. Imenom x ovde smo "vezali" član te jednočlane liste. Slično, u narednoj liniji koda, dekonstruisali smo dvočlane liste. U ovom slučaju, prvi element je predstavljen imenom x a drugi element imenom y.

Moguće je takođe koristi činjenicu da se lista poput [x, y, z] može predstaviti kao x:[y,z] ili x:y:[z] ili x:y:z:[]. Tako je prethodni primer moguće napisati i kao

s :: [Int] -> Int
s [] = 0
s (x:[]) = x
s (x:y:[]) = x + y
s _ = 1
Primer 3.

Funkcija koja vraća rep liste (sve element osim prvog), može se definisati na sledeći način:

rep :: [a] -> a
rep (x:xs) = xs
Operator : nadovezuje element na početak liste. Prema tome x je prvi element, a xs predstavlja ostatak liste. Primetimo da ova funkcija nije totalna jer nije definisana za slučaj prazne liste.

Zapravo, pošto nas u navedenom kodu vrednost x ne interesuje, funkciju možemo definisati i sa džokerom:

rep :: [a] -> a
rep (_:xs) = xs
Džokere bi trebalo koristiti kad god je to moguće, jer poboljšavaju čitljivost koda tako što umanjuju broj vezanih imena.

Dobro je naglasiti da pri podudaranju oblika nije moguće navesti oblik koji sadrži operator ++ (na primer ne možemo uhvatiti dvočlanu listu sa [x] ++ [y]). Razlog zašto je operator : moguće koristiti, a ++ ne, postaće jasan u jednoj od narednih lekcija.

Rekurzija nad listama

Korišćenje operatora : je posebno korisno kada želimo listu podeliti na glavu i rep, odnosno prvi element i ostatak liste.

Primer 4.

Funkciju zbir :: [Int] -> Int koja sabira sve elemete liste možemo napisati ovako:

zbir :: [Int] -> Int
zbir [] = 0
zbir (x:xs) = x + zbir xs

Gornja funkcija je rekurzivna funkcija koja sabira elemente liste tako što nepraznu listu dekonstruiše na glavu (x) i rep (xs), a zatim pozove samu sebe za pronalaženje zbira repa. Baza idukcije je slučaj prazne liste, čije je zbir naravno 0.

Zadatak 2. Implementirati funkciju proizvod :: [Int] -> Int koja pronalazi proizvod elemenata liste.

Primer 5.

Do sada smo se upoznali sa funkcijom last :: [a] -> a koja vraća poslednji element neprazne liste. Tehnikom rekuzije lako možemo da reimplementiramo ovu funkciju6. Baza rekurzije je sada jednočlana lista, jer nema smisla vraćati poslednji element prazne liste. Ako prosleđena lista nije prazna tada je njen poslednji element baš poslednji element repa te liste. Na ovaj način, sveli smo problem na rekurzivni poziv.

last' :: [a] -> a
last' [x] = x
last' (_:xs) = last xs
Pošto nas u drugom slučaju ne interesuje glava liste, iskoristili smo džoker _.

Zadatak 3. Reimplementirati funkcije za rad sa listama poput: tail, reverse, elem, unique.

Ponekad je potrebno implementirati funkcije koje su rekuzrivne po više argumenata.

Primer 6.

Često je potrebno odrediti da li je neka niska podniska druge. Tačnije, potrebna je funkcija daLiJePodnsika :: [Char] -> [Char] -> Bool koja određuje da li se prva prosleđena niska sadrži u drugoj prosleđenoj nisci. Ideja za implementaciju funkcije daLiJePodnsika je naravno tehnika rekurzije.

Pretpostavimo da su nam date dve neprazne niske igla i seno7, i da se pitamo da li se igla sadrži u nisci seno. Tada postoje dve mogućnosti:

  1. Niska igla predstavlja početak niske seno. U ovom slučaju, odgovor je na pitanje da li se igla nalazi u senu je potvrdan.
  2. Niska igla nije početak niske seno. U ovom slučaju, ako se niska igla nalazi u nisci seno, tada se mora nalaziti u repu te niske. Stoga pretragu možemo da okraničimo na rep niske seno.

Ako je niska seno prazna, tada se niska igla nalazi u njoj ako i samo ako je igla prazna niska. Da bi proverili da li je neka lista (specijalno niska) prazna, možemo iskoristiti ugrаđenu funkciju null :: [a] -> Bool

Na osnovu ove analize, implementacija daLiJePodnsika je jednostavna:

daLiJePodnsika :: [Char] -> [Char] -> Bool
daLiJePodnsika igla "" = null igla 
daLiJePodnsika igla seno =
    if daLiJePocetak igla seno
        then True
        else daLiJePodnsika igla (tail seno)

Ostaje nam još da implementiramo funkiju daLiJePocetak :: [Char] -> [Char] -> Bool koja proverava da li prva prosleđena niska predstavlja početak druge prosleđene niske. Ponovo ćemo koristiti rekurziju, ali ćemo sada vršiti rekurziju po oba argumenta.

Ako su glave obe prosleđene niske iste, tada možemo da nastavimo da poredimo repove. U suprotonom možemo da budemo sigurni da druga niska ne počinje sa prvom niskom. Baza indukcije su slučajevi u kojima je jedna od niski prazna. Ako je prva niska prazna, onda druga niska započinje prvom niskom. Ako je druga niska prazna, a prva niska nije prazna, tada znamo da se prva niska ne sadrži u drugoj nisci

daLiJePocetak :: [Char] -> [Char] -> Bool
daLiJePocetak "" _ = True
daLiJePocetak _ "" = False
daLiJePocetak (x:xs) (y:ys) =
    if x == y
        then daLiJePocetak xs ys
        else False

Primetimo da se funkcija daLiJePodlista :: Eq a => [a] -> [a] -> Bool može implementirati na gotovo isti način.

Funkcije višeg reda

Implementacijom mnogih rekurzivnih algoritama nad listama uvidećemo da se neki šabloni konstrukcije algoritama ponavljaju. Zbog toga su definisane funkcije višeg reda sa rad sa listama. Korišćenjem ovih funkcija možemo da izbegne eksplicitnu rekurziju u mnogim slučajevima.

Filter

Funkcija višeg reda filter nam omogućuje da iz neke liste izdvojimo samo elemente koji zadovoljavaju neki uslov. Tip ove funkcije je filter :: (a -> Bool) -> [a] -> [a]

Prvi argument funkcije je funkcija tipa a -> Bool koju nazivamo predikat. Predikat treba da vrati vrednost True ako element treba da ostane u listi, odnosno False ako je element potrebno ukloniti iz liste. Drugi argument funkcije je lista koju filtriramo. Rezultat je lista iz koje su uklonjeni elementi koji ne zadovoljavaju predikat.

Primer 7.

Ako želimo da "uzmemo" parne prirodne brojeve manje od 10 možemo napisati:

ghci> filter (\x -> mod x 2 == 0) [1 .. 10]
[2, 4, 6, 8, 10]
Zadatak 4. Data je lista visine :: [Float] koja predstavlja visine svih učenika jedne škole. Odrediti broj učenika viših od \(180\mathrm{cm}\). Dati rešenja sa i bez funkcije filter.
brojVisokihUcenika = length visokiUcenici
    where visokiUcenici = filter (\x -> x >= 180) visine

Zadatak 5. Svaka osoba je predstavljena sa uređenim parom tipa ([Char], Int) koji sadrži ime osobe i njene godine. Implementirati funkciju punoletne :: [([Char], Int)] -> [([Char], Int)] koja iz liste osoba eliminiše maloletne osobe. Dati rešenja sa i bez funkcije filter.

Zadatak 6. Reimplementirati funkciju filter.

Iskoristićemo tehniku rekurzije. Ako funkciju filter' p primenimo na praznu listu, tada je logično da dobijemo praznu listu bez obzira na predikat p. Ovaj slučaj predstavlja bazu rekurzije.

Ako lista nije prazna, tada je možemo rastaviti na glavu x i rep xs. Ako je p x tačno, tada se x nalazi na početku liste koju vraćamo, a u suprotnom ne. Za ostatak liste xs iskoristićemo rekurzivni poziv, da bismo isfiltrirali xs.

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' p (x:xs) = if p x then x : filter p xs else filter p xs
Pošto nas u baznom slučaju ne interesuje predikat, iskoristili smo džoker _.

Map

Još jedna funkcija višeg reda koja se često koristi sa listama je map. Funkcija map primenjuje neku drugu funkciju na svaki element liste i vraća listu dobijenih vrednosti. Tip funkcije map je: map :: (a -> b) -> [a] -> [b]

Prvi argument funkcije je funkcija tipa a -> b, a drugi argument je lista tipa [a]. Rezultat je lista tipa [b] koji je nastao od prosleđene liste primenom prosleđene funkcije na svaki element liste.

Primer 8.

Ako želimo da kvadriramo svaki element liste [1, 2, 3, 4], možemo napisati program

ghci> map (\x -> x^2) [1, 2, 3, 4]
[1, 4, 9, 16]
Zadatak 7. Reimplementirati funkciju map.

Iskoristićemo ponovo tehniku rekurzije. Funkcija map' treba da primeni neku funkciju f na svaki element liste l. Ako je lista l prazna, tada je i map f l prazna lista. Ovaj slučaj predstavlja bazu rekurzije.

Ako lista nije prazna, tada ćemo na glavu liste x primeniti funkciju f, čime dobijamo prvi element tražene liste. Za dobijanje ostatka liste, rekurzvno ćemo pozvati map' f nad repom liste xs.

map' :: (a -> b) -> [a] -> [b]
map' _ [] = []
map' f (x:xs) = f x ++ map' f xs 

Fold

Funkcija foldr koristi prosleđenu binarnu funkciju da bi prosleđenu listu "presavila" (fold) u jednu vrednost. Tip funkcije foldr je foldl :: (a -> b -> b) -> b -> [a] -> b

Prvi argument funkcije foldl je binarna funkcija tipa a -> b -> b. Drugi argument je početna vrednost, a treći argument je lista koju želimo da "presavijemo". Funkcija foldr "prolazi" kroz datu listu s desna na levo (otuda foldr) pozivajući nad svakim argumentom datu binarnu funkciju. Za svaki taj poziv, rezultat poziva nad prethodnim argumentom se koristi kao drugi argument binarne funkcije. Inicijalna vrednost se koristi kao drugi argument pri prvom pozivu (a to je poziv nad poslednjim elementom u listi).

Primer 9.

Komplikovano objašnjenje će postati jasnije kroz naredni primer. Uz pomoć foldr možemo da saberemo sve elemente jedne liste. Definišimo

f = \a b -> a + b

Ako foldr pozovemo nad praznom listom, dobićemo samo početnu vrednost:

ghci> foldr f 0 []
0

Ako foldr pozovemo nad jednočlanom listom, dobićemo rezultat primene funkcije f nad jedinim elementom liste i inicijanom vrednošću (tj. f 1 0):

ghci> foldr f 0 [1]
1

U slučaju dvočlane liste, funkcija f biče dva puta pozvana. Pri drugom pozivu biće iskorišćena povratna vrednost prvog poziva (tj. f 2 (f 1 0)):

ghci> foldr f 0 [2, 1]
3

Za listu od više elemenata imamo:

ghci> foldr f 0 [5, 4, 3, 2, 1]
15

Prethodih izraz je ekvivalentan izrazu f 5 (f 4 (f 3 (f 2 (f 1 0)))) koji je naravno ekvivalentan izrazu 5 + (4 + (3 + (2 + (1 + 0))))

Uz funkciju foldr koristi se i foldl koja "presavija" listu sa leva. Naravno, kada koristimo komutativnu operaciju, dobijamo isti rezultat sa foldl i foldr funkcijama. Za nekomutativne operacije rezultati će se uglavnom razlikovati:

ghci> g = \a b -> a / b
ghci> foldl g 1 [1, 2, 3]
0.16666 -- (1 / 2) / 3
ghci> foldr g 1 [1, 2, 3]
1.5 -- 1 / (2 / 3)

Zadatak 8. Naći \(n\)-tu parcijalnu sumu harmonijskog reda. Tačnije, napisati funkciju tipa Int -> Float koja u zavisnosti od parametra \(n\) računa sumu \[\sum^{n}_{i=1} \frac{1}{i}.\]

Zadatak 9. Reimplementirati funkciju map koristeći funkciju foldl.

Zadatak 10. Reimplementirati funkciju filter koristeći funkciju foldl.

Zip

Za uparivanje dve liste član-po-član u listu parova koristi se funkcija zip :: [a] -> [b] -> [(a, b)]. Pritom dužina liste parova je jednaka dužini kraćoj od prosleđenih lista.

Primer 10.

Funkcija zip se često koristi za "numerisanje" članova neke liste. Tako možemo lako numerisati listu dana u nedelji:

ghci> dani = ["Pon", "Uto", "Sre", "Čet", "Pet", "Sub", "Ned"]
ghci> dani2 = zip [1 .. 7] dani
ghci> dani2
[(1,"Pon"),(2,"Uto"),(3,"Sre"),(4,"Čet"),(5,"Pet"),(6,"Sub"),(7,"Ned")]

Kada nad listom parova dobijenih zip funkcijemo primenjujemo map funkciju, tada je zgodinije koristiti funkciju zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]. Funkcija zipWith kombinuje dve liste element-po-element koristeći prosleđenu funkciju.

Primer 11.

(Nastavak prethodnog primera) Listu numerisanih dana možmo pretvoriti u listu niski na sledeći način

ghci> f (a, b) = show a ++ ". " ++ b
ghci> numerisaniDani = map f dani2
ghci> numerisaniDani
["1. Pon","2. Uto","3. Sre","4. Čet","5. Pet","6. Sub","7. Ned"]
ghic> head numerisaniDani
"1. Pon"
Funkcija f spaja broj i nisku u nisku. Primetimo da smo ovde koristili poklapanje oblika za definisanje funkcije.

Ali, ako nam je potrebna samo vrednost numerisaniDani a ne i dani2, možemo preskočiti korak u kom kreiramo vrednost dani2, i iskoristiti funkciju zipWith:

ghci> numerisaniDani = zipWith f [1 .. 7] dani

Zadatak 11. Reimplementirati funkciju zipWith koristeći rekurziju.

Zadatak 12. Reimplementirati funkciju zip koristeći funkciju zipWith.

Zadatak 13. Reimplementirati funkciju zipWith koristeći funkcije zip i map.

Cezarova šifra

Po rimskom istoričaru Svetoniju, Julije Cezar je šifrovao vojne poruke tako što bi slovo A zamenio slovom D, slovo B slovom E, slovo C slovom F, i tako dalje, zamenjujući svako slovo latinskog alfabeta sa slovom koje se nalazi tri mesta nakon tog slova. Na primer, reč CLEOPATRA bi pri ovom šifrovanju postala FOHRSDYVD8. Onaj ko bi primio poruku, dešifrovao bi poruku tako što bi uradio sličnu zamenu, ali ovog puta zamenjujući svako slovo sa slovom koje se u alfabetu nalazi tri mesta pre. Iako Cezar nije prvi iskoristio ovakvu šifru, danas šifra nosi ime po njemu. Štaviše, pod istim imenom nazivaju se šifre koje "pomeraju" slova za \(n\) mesta, gde \(n\) ne mora biti baš \(3\).

Za implementaciju Cezarove šifre prvo ćemo konstruisati listu parova odgovarajućih karaktera (svaki par će sadržati slovo i šifrovano slovo). To možemo učiniti sa zip funkcijom

šifra :: [(Char, Char)]
šifra = zip ['A' .. 'Z'] ['D' .. 'Z']

Navedenim kodom smo uparili listu ['A' .. 'Z'] sa listom ['D' .. 'Z']. Time dobijamo listu koja redom sadrži parove ('A','D'), ('B','E'), ('C','F'), itd.. Međutim, kako ['A' .. 'Z'] ima 26, a ['D' .. 'Z'] samo 23 člana, lista šifra će imati samo 23 člana, i slova 'X', 'Y' i 'Z' neće imati para.

Da bismo prevazišli problem, na kraj liste ['D' .. 'Z'] dodaćemo karaktere ['A', 'B', 'C']. Na ovaj način 'X' će se šifrovati u (upariti sa) 'A', 'Y' u 'B' i 'Z' u 'C'.

šifra :: [(Char, Char)]
šifra = zip ['A' .. 'Z'] (['D' .. 'Z'] ++ ['A', 'B', 'C'])
ghci> šifra
[('A','D'),('B','E'),('C','F'),('D','G'),('E','H'),('F','I'),('G','J'),('H','K'),('I','L'),
('J','M'),('K','N'),('L','O'),('M','P'),('N','Q'),('O','R'),('P','S'),('Q','T'),('R','U'),
('S','V'),('T','W'),('U','X'),('V','Y'),('W','Z'),('X','A'),('Y','B'),('Z','C')]

Sada listu sifra možemo da iskoristimo da šifrujemo pojedinačne karaktere. Ideja je sledeća: za dati karakter k :: Char, iz liste sifra uzećemo par čija prva koordinata je jednaka vrednosti k. Šifrovan karakter će biti druga koordinata tog para. Za pronalazak odgovarajućeg para, koristimo funkciju filter.

šifrujKarakter :: Char -> Char
šifrujKarakter k = snd (head šifrovano)
  where
    šifrovano = filter (\par -> fst par == k) šifra
Na primer, ako je k = 'A', tada će filter u listi sifrovano ostaviti samo uređene parave čija je prva koordinata 'A', a to je samo par ('A', 'D'). Dakle, sifrovano će biti lista [('A', 'D')]. Prvom i jedinom elementu te liste ćemo pristupiti sa funkcijom head, a drugoj koordinati tog elementa ćemo pristupiti sa funkcijom snd. Time dobijamo šifrujKarakter 'A' = 'D'.

Funkcija šifrujKarakter šifruje velika slova engleske abecede. Ali, ako pozovemo šifrujKarakter nad karakterima 'a', '9' ili 'ш', doći će do katastrofalinih rezultata. Naime, u takvim slučajevima lista sifrovano će biti prazna, a pokušaj pristupa prvom članu prazne liste (head šifrujKarakter) će dovesti do prekida programa. Zbog toga, pre pristupa elementu liste šifrovano moramo proveriti da li je lista prazna. Ako jeste prazna, onda ćemo vratiti prosleđeni karakter, a u suprotnom ćemo vratiti šifrovan karakter.

šifrujKarakter :: Char -> Char
šifrujKarakter k
  | null sifrovano = k
  | otherwise      = snd (head šifrovano)
  where
    šifrovano = filter (\par -> fst par == k) šifra

Šifrovana niska dobija se primenom funkcije šifrujKarakter na svaki karakter te niske:

šifruj :: [Char] -> [Char]
šifruj niska = map šifrujKarakter niska
ghci> šifruj "NAPAD NA GALE VECERAS U OSAM"
"QDSDG QD JDOH YHFHUDV X RVDP"
Pošto se razmak ' ' ne nalazi u listi šifra, važi šifrujKarakter ' ' = ' '. Samim tim, prilikom šifrovanja razmaci se čuvaju.

Funkcija koja dešifruje poruku je potpuno analogna funkciji koja je šifruje, samo što je uloga koordinata obrnuta. Pretragu vršimo po drugoj koordinati, a vraćmo prvu:

dešifrujKarakter :: Char -> Char
dešifrujKarakter k
  | null dešifrovano = k
  | otherwise      = fst (head dešifrovano)
  where
    dešifrovano = filter (\par -> snd par == k) šifra

dešifruj :: [Char] -> [Char]
dešifruj niska = map dešifrujKarakter niska

Zadatak 14. Implementirati Cezarovu šifru sa proizvoljnim pomerajem \(n\).

Zadatak 15. Vižnerova šifra (po francuskom kriptografu Blezu de Vižneru) predstavlja uopštenje Cezarove šifre. Za Vižnerovu šifru, potrebno je odabrati ključ koji će se koristiti prilikom šifrovanja i dešifrovanja. Ključ je jedna reč, čija slova određuju pomeraje za Cezarovu šifru. Uzmimo ponovo prethodni primer tajne poruke "NAPAD NA GALE VECERAS U OSAM", a za ključ uzmimo "RIM". Pri Vižnerovom šifrovanju, prvi karakter poruke, 'N', će se šifrovati sa Cezarovom šifrom sa pomerajem \(18\), jer je prvi karakter ključa, 'R', osamnaesto slovo u abecedi. Drugi karakter će se šifrovati sa pomerajem \(9\) (jer je 'I' deveto slovo abecede), a treći sa pomerajem \(13\) (jer je 'M' trinaesto slovo abecede). Pošto smo stigli do kraja ključa, ključ koristimo ispočetka, i četvrto slovo poruke, 'A' šifrujemo sa pomerajem \(18\). Ovaj proces nastavljavmo, ponavljajući ključ, sve dok ne stignemo do kraja poruke. Implementirati Vižnerovu šifru.

Zadaci

Zadatak 16. Napisati program koji vraća listu prvih \(n\) Fibonačijevih brojeva.

Zadatak 17. Svi prirodni brojevi manji od 10 koji su deljivi sa \(3\) ili \(5\) su \(3\), \(5\), \(6\) i \(9\). Njihov zbir je \(23\). Naći zbir svih prirodnih brojeva manjih od \(100\) koji su deljivi sa \(3\) ili \(5\).

Zadatak 18. Palindromski broj je prirodan broj koji se čita isto i sa leva i sa desna. Najveći palindromski broj koji je proizvod dva dvocifrena broja je \(9009\), jer je \[9009 = 91 \cdot 99.\] Naći najveći palindromski broj koji je proizvod dva trocifrena broja.

Zadatak 19. Implementirati funkciju dekartovProzivod koja vraća "Dekartov proizvod dve liste". Na primer: dekartovProzivod [1, 2, 3] ['a', 'b'] daje [(1,'a'),(2,'a'),(3,'a'),(1,'a'),(2,'b'),(3,'b')].

Zadatak 20. Naći sve početke date liste. Na primer poceci [1, 2, 3] bi trebalo da nam vrati [[], [1], [1, 2], [1, 2, 3]].

Zadatak 21. Napisati funkciju kodiraj :: String -> [(Char, Int)] koja kodira nisku tako što je predstavlja kao listu uređenih parova karatera i prirodnih brojeva. Broj označava dužinu uzastopnog ponavljanja datog karaktera. Na primer: kodiraj "aaaabb" daje [('a', 4), ('b', 2)], a kodiraj "Google" daje [('G', 1), ('o', 2), ('g', 1), ('l', 1), ('e', 1)]. Napisati i funkciju dekodiraj :: [(Char, Int)] -> String.

Zadatak 22. Napisati funkciju rotiraj :: Int -> [a] -> [a] koja "rotira" listu tako što svaki element pomera za n mesta u levo, pri čemu se elementi sa kraja liste vraćaju na početak: rotiraj 1 "ABCD" daje "BCDA", a rotiraj 2 "ABCD" daje "CDAB", itd...

Pomoć: Implementirati pomoćnu funkciju koja rotira listu za jedan element. Opštu funkciju implementirati rekurzijom po broju rotiranja koristeći pomoćnu funkciju.

Zadatak 23. Implementirati funkciju srednjaVrednost :: [Float] -> Float koja računa srednju vrednost liste. Implementirati funkciju disperzija :: [Float] -> Float koja računa disperziju vrednosti liste.

Zadatak 24. Data je lista prirodnih brojeva sa \(n>0\) članova. Element na poziciji \(k \le n\) predstavlja cenu neke akcije na berzi u \(k\)-tom danu. Potrebno je u jednom od ponuđenih dana kupiti akciju, a zatim u nekom od narednih dana (uključujići i dan kupovine) i prodati akciju. Naravno, cilj je ostvariti što veći profit (profit računamo kao razliku prodajne i kupovne cene). Napisati funkciju profit :: [Int] -> Int koja uzima cene akcija tokom vremena, i vraća najveći profit koji je moguće ostvariti trgovinom akcija. Akcija se može samo jednom kupiti i prodati, prodaja se mora odviti nakon kupovine ili istog dana. Pretpostaviti da prosleđena lista nije prazna. Na primer profit [7,1,5,3,6,4] = 5 jer kupovinom drugog dana i prodajom petog dana ostvarujemo profit \(6 - 1 = 5\). Ne možemo ostvariti dobit \(7 - 1 = 5\) jer se prodaja mora ostvariti nakon kupovine.