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, npr. [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 postojaću vrednost).
Funkcije za rad sa listama
U prethodnim lekcijama već smo se upoznali sa nekim funkcijama za rad sa listama:
(++) :: [a] -> [a] -> [a]
spaja dve listelength :: [a] -> Int
vraća dužinu listeelem :: Eq a => a -> [a] -> Bool
ispituje da li se element nalazi u listireverse :: [a] -> [a]
obrće poredak elemena u listihead :: [a] -> a
vraća prvi element liste. Ako je lista prazna dolazi do izuzetkainit :: [a] -> a
vraća sve elemente osim poslednjeg. Ako je lista prazna dolazi do izuzetkatail :: [a] -> a
vraća sve elemente osim prvog. Ako je lista prazna dolazi do izuzetkalast :: [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
klase1.
Prelid obezbeđuje neke korisne funkcije za rad sa listama karaktera:
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".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"
.lines :: [Char] -> [[Char]]
rastavlja nisku na linije, vršeći prelom na karakteru za novi red'\n'
.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 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 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.
Zadatak 1. Napisati funkciju brojReči :: [Char] -> Int
koja broji reči u nisci.
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 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] []
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]
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ška može lako ukazati4
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"
['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 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.
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'
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 deklarisati 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 2. 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']
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.
Funkciju zbir :: [Int] -> Int
koja sabira sve elemente liste možemo napisati ovako:
zbir :: [Int] -> Int zbir xs = if null xs then 0 else head xs + zbir (tail xs)
Uslovom null xs
se proverava da li je lista prazna. Ako jeste, tada vraćamo 0
. U suprotnom, vrednost prvog elementa dodajemo na zbir repa liste.
Tehnika podudaranja oblika liste je posebno korisna za implementaciju rekurzivnih algoritama. Sa ovom tehnikom, kôd algoritma često postaje elegantniji:
Funkciju zbir
možemo napisati i ovako:
zbir :: [Int] -> Int zbir [] = 0 zbir (x:xs) = x + zbir xs
Zadatak 3. Implementirati funkciju proizvod :: [Int] -> Int
koja pronalazi proizvod elemenata liste.
Po ugledu na prethodne primere, lako dolazimo do rešenja
proizvod :: [Int] -> Int proizvod [] = 1 proizvod (x:xs) = x * proizvod xs
Osim promene same operacije, promenili smo i povratnu vrednost za praznu listu. Za svaki drugi izbor vrednosti proizvod []
, dobio bi se pogrešan rezultat. Štaviše, u slučaju da smo definisali proizvod [] = 0
, tada bi proizvod svake liste bio 0
.
Do sada smo se upoznali sa funkcijom last :: [a] -> a
koja vraća poslednji element neprazne liste. Tehnikom rekurzije lako možemo da reimplementiramo ovu funkciju5. 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
_
.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.
Često je potrebno odrediti da li je neka niska podniska druge. Tačnije, potrebna je funkcija daLiJePodniska :: [Char] -> [Char] -> Bool
koja određuje da li se prva prosleđena niska sadrži u drugoj prosleđenoj nisci. Ideja za implementaciju funkcije daLiJePodniska
je naravno tehnika rekurzije.
Pretpostavimo da su nam date dve neprazne niske igla
i seno
6, i da se pitamo da li se igla
sadrži u nisci seno
. Tada postoje dve mogućnosti:
- Niska
igla
predstavlja početak niskeseno
. U ovom slučaju, odgovor je na pitanje da li se igla nalazi u senu je potvrdan. - Niska
igla
nije početak niskeseno
. U ovom slučaju, ako se niskaigla
nalazi u nisciseno
, tada se mora nalaziti u repu te niske. Stoga pretragu možemo da ograničimo na rep niskeseno
.
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 funkciju null :: [a] -> Bool
iz prelida.
Na osnovu ove analize, implementacija daLiJePodniska
je jednostavna:
daLiJePodniska :: [Char] -> [Char] -> Bool daLiJePodniska igla "" = null igla daLiJePodniska igla seno = if daLiJePočetak igla seno then True else daLiJePodniska igla (tail seno)
Ostaje nam još da implementiramo funkciju daLiJePočetak :: [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 suprotnom 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
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
Primetimo da se funkcija daLiJePodlista :: Eq a => [a] -> [a] -> Bool
može implementirati na gotovo isti način.
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 izbegne 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.
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 9. Data je lista visine :: [Float]
koja predstavlja visine svih učenika jedne škole. Odrediti broj učenika viših od \(180\mathrm{cm}\).
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
.
Zadatak 11. 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
_
.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ži7 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]
koji je nastao od prosleđene liste primenom prosleđene funkcije na svaki element liste.
Ako želimo da kvadriramo svaki element liste [1, 2, 3, 4]
, možemo napisati
ghci> map (\x -> x^2) [1, 2, 3, 4] [1, 4, 9, 16]
Zadatak 12. 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, rekurzivno ćemo pozvati map' f
nad repom liste xs
.
map' :: (a -> b) -> [a] -> [b] map' _ [] = [] map' f (x:xs) = f x : map' f xs
Fold
Funkcije foldl
i foldr
koriste prosleđenu binarnu funkciju da bi "presavile" listu u jednu vrednost. Razlika između foldl
i foldr
funkcije je tome što foldl
poničinje od početka liste (levog kraja), dok foldr
počinje od desnog kraja.
Tip funkcije foldr
je foldl :: (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 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). Komplikovano objašnjenje će postati jasnije kroz primere.
Uz pomoć foldr
možemo sabrati sve elemente jedne liste. Binarna funkcija koju ćemo koristiti je funkcija koja sabira argumente s = \a b -> a + b
.
Ako foldr
pozovemo nad praznom listom, dobićemo početnu vrednost:
ghci> foldr s 0 [] 0
Ako foldr
pozovemo nad jednočlanom listom, dobićemo rezultat primene funkcije s
nad jedinim elementom liste i inicijalnom vrednošću (tj. s 1 0
):
ghci> foldr s 0 [1] 1 ghci> foldr f 0 [2, 1] 3
U slučaju dvočlane liste, prosleđena funkcija biće dva puta pozvana. Pri drugom pozivu biće iskorišćena povratna vrednost prvog poziva. Drugim rečima, krajnji rezultat se dobija kao s 2 (s 1 0)
Za listu od više elemenata imamo:
ghci> foldr s 0 [5, 4, 3, 2, 1] 15
Prethodih izraz je ekvivalentan izrazu s 5 (s 4 (s 3 (s 2 (s 1 0))))
koji je naravno ekvivalentan izrazu 5 + (4 + (3 + (2 + (1 + 0))))
Naravno, isti rezultat se dobija i sa foldl
funkcijom. Izraz foldl s 0 [5, 4, 3, 2, 1]
svodi se na izraz (((((0 + 5) + 4) + 3) + 2) + 1)
.
Nije neophodno da rezultati primene foldl
i foldr
funkcija budu isti:
ghci> g = \a b -> a / b ghci> foldl g 1 [1, 2, 3] 0.16666 ghci> foldr g 1 [1, 2, 3] 1.5
(1 / 2) / 3
, dok se drugi izraz svodi na 1 / (2 / 3)
.Zadatak 13. 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 14. Reimplementirati funkciju map
koristeći funkciju foldl
.
Zadatak 15. Reimplementirati funkciju filter
koristeći funkciju foldl
.
Zadatak 16. 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.
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 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.
(Nastavak prethodnog primera) Listu numerisanih dana možemo 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"
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 17. Reimplementirati funkciju zipWith
koristeći rekurziju.
Zadatak 18. Reimplementirati funkciju zip
koristeći funkciju zipWith
.
Zadatak 19. 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 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 š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
k = 'A'
, tada će filter
u listi sifrovano
ostaviti samo uređene parove čija je prva koordinata 'A'
, a to je samo par ('A', 'D')
. Dakle, šifrovano
ć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 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"
' '
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ć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 20. 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 21. Koristeći prethodni zadatak, implementirati Cezarovu šifru sa proizvoljnim pomerajem \(n\).
Zadatak 22. 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 23. Napisati program koji vraća listu prvih \(n\) Fibonačijevih brojeva.
Zadatak 24. 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 25. 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 26. 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 27. 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 28. Napisati funkciju kodiraj :: String -> [(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)] -> String
.
Zadatak 29. 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 30. Implementirati funkciju srednjaVrednost :: [Float] -> Float
koja računa srednju vrednost liste. Implementirati funkciju disperzija :: [Float] -> Float
koja računa disperziju vrednosti liste.
Zadatak 31. 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.