Liste

Liste u Haskelu su strukture podataka koje predstavljaju linearno uređenu kolekciju proizvoljno mnogo vrednosti istog tipa. Liste se konstruišu navođenjem vrednosti unutar uglastih zagrada. Na primer, zapis [5, 8, 13, 21, 34] predstavlja listu od pet elemenata. Međutim, zapis poput navedenog, predstavlja samo skraćeni oblik zapisa 5:(8:(13:(21:(34:[])))). Operacija : nadovezuje element na početak neke postojeće liste i predstavlja jedan od konstruktora vrednosti liste, odnosno funkcije kojom se konstruiše neka lista. Drugi konstruktor vrednosti liste je konstruktor prazne liste koji se označava sa []. Važno je napomenuti da su ovo jedini konstruktori vrednosti liste, i da se svaka druga funkcija koja vraća neku listu svodi na neki način na upotrebu ova dva konstruktora. Takođe, ova činjenica povlači i da je svaka lista prazna (dobijena konstruktorom prazne liste), ili poseduje prvi član (odnosno, nastala je nadovezivanjem neke vrednosti na postojeću listu).

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 elemenata 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 se sve navedene funkcije, osim funkcije elem, mogu koristiti sa listom proizvoljnog tipa jer poseduju parametarski polimorfan tip. Funkcija elem može se koristiti samo sa instancama Eq klase¹.

Prelid obezbeđuje neke korisne 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 ":

stih :: [Char]
stih = "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 dodati na svakom mestu:

stih :: [Char]
stih = "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 stih, niska će se ispisati unutar dvostrukih navodnika u jednoj (ali dugačkoj) liniji terminala². 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 stih
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.

brojReči :: [Char] -> Int
brojReči x = length (words x)

Rasponi

Neretko se javlja potreba da se konstruiše lista poput liste prirodnih brojeva od \(1\) do \(n\) ili liste brojeva od \(m\) do \(n\) itd... Iako nije teško implementirati rekurzivne funkcije koje vraćaju ovakve liste, Haskel jezik poseduje sintaksu za raspone³ 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]
[]

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]

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ška može lako 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 geometrijske (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"

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 enumerisati. 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 koriste se za konstrukciju opsega.

ghci> fromEnum 'a'
97
ghci> toEnum 100 :: Char
'd'

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".

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

Rekurzija nad listama

Liste imaju prirodnu rekurzivnu strukturu. Svaka lista osim prazne je nastala nadovezivanjem nekog elementa na početak neke kraće liste. Mnogi algoritmi za rad sa listama se mogu implementirati rekurzijom po dužini liste. Baza rekurzije čini slučaj prazne liste, dok rekurzivni korak predstavlja svođenje problema na isti problem za kraću listu.

zbir :: [Int] -> Int
zbir xs =
    if null xs
    then 0
    else head xs + zbir (tail xs)

Tehnika podudaranja oblika liste je posebno korisna za implementaciju rekurzivnih algoritama. Sa ovom tehnikom, kôd algoritma često postaje elegantniji:

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

proizvod :: [Int] -> Int
proizvod [] = 1
proizvod (x:xs) = x * proizvod xs

last' :: [a] -> a
last' [x] = x
last' (_:xs) = last xs

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

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

daLiJePodniska :: [Char] -> [Char] -> Bool
daLiJePodniska igla "" = null igla 
daLiJePodniska igla seno =
    if daLiJePočetak igla seno
        then True
        else daLiJePodniska igla (tail seno)

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

Zadatak 5. Definisati funkciju dupliraj :: Num a => [Int] -> [Int] koja duplira svaki element liste brojeva. Redosled dupliranih vrednosti treba da odgovara redosledu vrednosti u originalnoj listi. Na primer dupliraj [2, 3, 4] je [4, 6, 8], a dupliraj [] je [].

Zadatak 6. Definisati funkciju dužine :: [[Char]] -> [Int] koja listu niski preslikava u listu brojeva, pri čemu svaki broj predstavlja dužinu niske. Pritom, redosled brojeva je isti kao redosled odgovarajućih niski. Na primer, dužine ["Pop","Ćira","i","pop","Spira"] je [3,4,1,3,5].

Zadatak 7. Definisati funkciju parni :: [Int] -> [Int] koje listu brojeva preslikava u listu brojeva koja je dobijana uklanjanjem svih neparnih brojeva iz početne liste. Na primer, parni [1,2,3,4] je [2,4].

Zadatak 8. Definisati funkciju zbirCifara :: Int -> Int koja određuje zbir cifara broja zapisanog u dekadnom zapisu. Koristeći ovu funkciju, naći sve prirodne brojeve \(n\) manje od \(100\), takve da je zbir cifara broja \(n^2\) deljiv sa \(5\).

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 izbegnemo eksplicitnu rekurziju u mnogim slučajevima.

Filter

Funkcija višeg reda filter :: (a -> Bool) -> [a] -> [a] iz liste izdvaja samo elemente koji zadovoljavaju neki uslov.

Prvi argument funkcije je funkcija tipa a -> Bool koju nazivamo predikat. Predikat treba da vrati vrednost True ako element treba da se nađe u povratnoj listi. Drugi argument funkcije je lista koju filtriramo. Rezultat je lista iz koje su uklonjeni elementi koji ne zadovoljavaju predikat, pri čemu poredak elemenata ostaje isti.

ghci> filter (\x -> mod x 2 == 0) [1 .. 10]
[2, 4, 6, 8, 10]

brojVisokihUčenika = length visokiUčenici
    where visokiUčenici = filter (\x -> x >= 180) visine

Zadatak 10. 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.

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ [] = []
filter' p (x:xs) = if p x then x : filter p xs else filter p xs

Map

Još jedna funkcija višeg reda koja se često koristi sa listama je map :: (a -> b) -> [a] -> [b]. Funkcija map primenjuje datu funkciju na svaki element liste i vraća listu dobijenih vrednosti tj. važi⁷ map f [x₁, x₂, ... xₙ] = [f x₁, f x₂, ... f xₙ].

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

ghci> map (\x -> x^2) [1, 2, 3, 4]
[1, 4, 9, 16]

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

Fold

Funkcije foldl i foldr koriste neku binarnu funkciju da bi "presavile" složenu vrednost (poput liste) u jednu vrednost. Ove funkcije se mogu koristiti sa tipovima koji pripadaju Foldable klasi, a liste su osnovni primer takvih tipova. Zapravo, upravo je implementacija funkcija foldr neophodna za instanciranje Foldable klase⁸. Nadalje, možemo zaboraviti na Foldable klasu, i posmatrati funkcije foldl i foldr samo kroz kontekst lista.

Razlika između foldl i foldr funkcije je tome što foldl počinje od početka liste (levog kraja), dok foldr počinje od desnog kraja.

Pogledajmo prvo funkciju foldr. Tip funkcije foldr je⁹ foldr :: (a -> b -> b) -> b -> [a] -> b. Prvi argument funkcije foldr 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 pozivajući nad svakim elementom datu binarnu funkciju. Za svaki taj poziv, rezultat poziva nad prethodnim elementom 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). Komplikovano objašnjenje će postati jasnije kroz naredne primere.

ghci> foldr saberi 0 []
0

ghci> foldr saberi 0 [1]
1

ghci> foldr saberi 0 [2, 1]
3

ghci> foldr saberi 0 [3, 2, 1]
6

U prethodnim primerima, obe funkcije su dale isti rezultat jer smo koristili funkciju saberi koja je simetrična po parametrima (tj. saberi a b daje isti rezultat kao saberi b a). Ali nije neophodno da rezultati primene foldl i foldr funkcija budu isti:

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

Često je zgodno da umesto posebne inicijalne vrednosti, iskoristimo prvi (ili poslednji) element liste. Tada nam mogu pomoći funkcije foldl1 :: (a -> a -> a) -> [a] -> a i foldr1 :: (a -> a -> a) -> t a -> a koje se razlikuju od foldl i foldr funkcija po tome što nemaju i inicijalnu vrednost kao jedan od parametara.

najmanji :: Ord a => [a] -> a
najmanji xs = foldl1 min xs

ghci> najmanji [3, 4, 1, 2]
1

Da bi ste shvatili prednost foldl1 i foldr1 funkcija, pokušajte da implementirate funkciju iz prethodnog primera koristeći foldl ili foldr. Uvidećete da izbor inicijalne vrednosti nije uvek trivijalna stvar. Obratite pažnju da lista može da sadrži i negativne vrednosti.

Zadatak 13. Implementirati funkciju najveći :: Ord a => [a] -> a koja vraća najveći element liste. Pretpostaviti da lista neće biti prazna.

Zadatak 14. Implementirati funkciju svi :: [Bool] -> Bool, koja vraća True samo ako su svi elementi u prosleđenoj listi tačni. Navesti implementaciju i sa foldl i sa foldl1 funkcijom.

Zadatak 15. Implementirati funkciju baremJedan :: [Bool] -> Bool koja vraća True ako je barem jedan element u prosleđenoj listi tačan.

Zadatak 16. 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}.\]

cifreUbroj :: [Int] -> Int
cifreUbroj [] = 0
cifreUbroj [x] = x
cifreUbroj xs = (cifreUbroj (init x)) * 10 + (last x)

uBroj :: [Char] -> Int
uBroj s = cifreUbroj (map uCifru s)

Zadatak 18. Napisati funkciju daLiJeBroj :: [Char] -> Bool koja provera da li je data niska validan zapis prirodnog broja (tj. sastoji se samo od cifara).

Zadatak 19. Napisati funkciju daLiJeCeoBroj :: [Char] -> Bool koja provera da li je data niska validan zapis celog broja (tj. sastoji se od cifara sa eventualnim znakom - na početku).

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

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

Zadatak 22. Reimplementirati funkciju id :: [a] -> [a] 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 koja se dobija kao rezultat je jednaka dužini kraćoj od prosleđenih lista.

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 na rezultat zip funkcije primenjujemo map funkciju, tada je zgodnije koristiti funkciju zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]. Funkcija zipWith kombinuje dve liste element-po-element koristeći prosleđenu funkciju.

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"

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

Zadatak 23. Reimplementirati funkciju zipWith koristeći rekurziju.

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

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

Primer: 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 FOHRSDYVD¹². 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 šifra 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

Funkcija šifrujKarakter šifruje velika slova engleske abecede. Ali, ako pozovemo šifrujKarakter nad karakterima 'a', '9' ili 'ш', doći će do katastrofalnih rezultata. Naime, u takvim slučajevima lista šifrovano ć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 šifrovano = 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"

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ćamo 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 26. Implementacija Cezarove šifra koju smo prezentovali gore je dobra za demonstraciju rada sa listama u Haskelu, ali nije mnogo efikasna. Umesto da za svako slovo pretražujemo listu šifra, možemo iskoristiti fromEnum :: Enum a => a -> Int i toEnum :: Enum a => Int -> a funkcije da bi konvertovali slova u ASCII vrednosti i obrnuto. Koristeći navedene funkcije, kao i funkciju ostataka mod, dati alternativnu definiciju funkcije šifrujKarakter.

Zadatak 27. Koristeći prethodni zadatak, implementirati Cezarovu šifru sa proizvoljnim pomerajem \(n\).

Zadatak 28. 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 nastavljamo, ponavljajući ključ, sve dok ne stignemo do kraja poruke. Implementirati Vižnerovu šifru.

Zadaci

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

Zadatak 30. 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 31. 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 32. Implementirati funkciju dekartovProizvod koja vraća "Dekartov proizvod dve liste". Na primer: dekartovProizvod [1, 2, 3] ['a', 'b'] daje [(1,'a'),(2,'a'),(3,'a'),(1,'a'),(2,'b'),(3,'b')].

Zadatak 33. 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 34. Napisati funkciju kodiraj :: [Char] -> [(Char, Int)] koja kodira nisku tako što je predstavlja kao listu uređenih parova karaktera 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)] -> [Char].

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

Zadatak 37. 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čujuć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.