Rekurzivni tipovi podataka

Rekurzivni tipovi podataka su tipovi čije vrednosti mogu "sadržati u sebi" vrednosti istog tipa. Ovakva apstraktna karakterizacija ne znači trenutno mnogo. Zbog toga ćemo u nastavku upoznati se sa dva najznačajnija rekurzivna tipa, a to su liste i stabla. Kroz primere, uvidećemo da su rekurzivni tipovi podataka pogodni za predstavljanje vrednosti neograničene složenosti.

Važno je napomenuti da su rekurzivni tipovi specijalni slučaj algebarskih tipova podataka (koje smo već upoznali). Ono što izdvaja rekurzivne tipove podataka je to što se u definiciji tipa nalazi tip koji se definiše¹

Liste

Konstruisaćemo tip ListaBrojeva čije vrednosti su liste s celobrojnim vrednostima². Tip ListaBrojeva mora sadržati vrednost prazne liste, liste sa jednim elementom, liste sa dva elementa, liste sa tri elementa itd... Prazna lista se može predstaviti sa nularnim konstruktorom. Lista sa jednim elementom se može predstaviti sa unarnim konstruktorom, lista sa dva elementa sa binarnim konstruktorom, i tako dalje... Uzimajući ova razmatranja u obzir, dolazimo do naivne ideje o konstrukciju tipa ListaBrojeva kao sume konstruktora različite arnosti:

data ListaBrojeva =
    PraznaListaBrojeva
    | Lista1 Int
    | Lista2 Int Int
    | Lista3 Int Int Int
    | Lista4 Int Int Int Int 

Odmah uočavamo problem: s definicijom poput navedene nikad ne možemo obuhvatiti sve liste. Koliko god mi konstruktora napravili, uvek će postojati potreba za još dužom listom tj. za konstruktorom još veće arnosti. Zbog toga moramo iskoristiti rekurzivnu konstrukciju. Lista može biti prazna lista, ili može biti lista koja je nastala spajanjem nekog elementa na početak već postojeće liste. Zbog toga, i tip lista konstruišemo kao sumu dva konstruktora: jedan konstruktor predstavlja praznu listu, dok drugi konstruktor nadovezuje element na listu manje dužine:

data ListaBrojeva = DodajBroj Int ListaBrojeva | PraznaListaBrojeva

Da bi smo prikazivali vrednosti tipa ListaBrojeva u konzoli, pridružićemo tip ListaBrojeva klasi Show:

instance Show ListaBrojeva where
    show xs = "<" ++ prikaži xs ++ ">"
        where
            prikaži PraznaListaBrojeva = ""
            prikaži (DodajBroj y PraznaListaBrojeva) = show y
            prikaži (DodajBroj y ys) = show y ++ ", " ++ prikaži ys

Vrednosti tipa ListaBrojeva prikazujemo tako što elemente liste navodimo između znakova < i > koji podsećaju na izlomljene zagrade³. Za prikazivanje samih elemenata liste koristimo pomoćnu rekurzivnu funkciju prikaži. Sada možemo elegantno prikazivati vrednosti tipa ListaBrojeva u interaktivnom okruženju:

ghci> x = DodajBroj 1 (DodajBroj 2 (DodajBroj PraznaListaBrojeva) 
ghci> x
<1, 2, 3>

Zgodno je implementirati mnoge funkcije za rad sa tipom ListaBrojeva. Kako je i sama priroda tipa rekurzivna, i ove funkcije će biti (uglavnom) rekurzivne.

Dužinu liste je lako pronaći. Dužina prazne liste je 0, a dužina liste nastale dodavanjem broja na listu xs je za jedan veća od dužine liste xs.

dužina :: ListaBrojeva -> Int
dužina PraznaListaBrojeva = 0
dužina (DodajBroj _ xs) = 1 + dužina xs  

Funkcija spoji spaja dve liste vršeći rekurziju po prvoj listi.

spoji :: ListaBrojeva -> ListaBrojeva -> Lista
spoji PraznaListaBrojeva xs = xs
spoji (DodajBroj x xs) ys = DodajBroj x (spoji xs ys)

Funkcija obrni obrće redosled elemenata liste

obrni :: ListaBrojeva -> ListaBrojeva
obrni PraznaListaBrojeva = PraznaListaBrojeva
obrni (DodajBroj x xs) = spoji (obrni xs) x 

Zadatak 1. Kreirati tip ListaBrojeva1 čije vrednosti su neprazne liste celobrojnih vrednosti.

Zadatak 2. Kreirati tip ListaBrojeva2 čije vrednosti su liste celobrojnih vrednosti koje imaju barem dva člana.

Zadatak 3. Implementirati funkciju parni :: ListaBrojeva -> ListaBrojeva koja uklanja neparne elemente iz liste.

Zadatak 4. Implementirati funkciju primeni :: (Int -> Int) -> ListaBrojeva -> ListaBrojeva koja primenjuje prosleđenu funkciju na svaki element liste.

Apstraktni tip lista

Tip ListaBrojeva sadrži samo liste celobrojnih vrednosti. Jasno je da sa sličnom konstrukcijom mogu se definisati i drugi tipovi lista:

data ListaChar = DodajChar Char ListaChar | PraznaListaChar

data ListaBool = DodajBool Bool ListaBool | PraznaListaBool

Ovakvim pristupom za svaki tip moramo definisati odgovarajući tip lista, što nije praktično. Zbog toga, definisaćemo jedan apstraktan tip podataka Lista :: * -> * čiji parametar označava tip vrednosti sadržanih u listi. Definicija liste ostaje gotovo ista, ali se umesto konkretnog tipa pojavljuje tipski parametar a:

data Lista a = Dodaj a (Lista a) | PraznaLista

Sa apstraktnim tipom se lako mogu predstaviti liste vrednosti bilo kog tipa. Na primer, sada Lista Int predstavlja tip koji odgovara tipu ListaBrojeva od malopre, a Lista Bool odgovara tipu ListaBool od malopre. Primetimo da sada konstruktori Dodaj, PraznaLista imaju isto ime za sve tipove, što dodatno olakšava zapis.

ghci> x = Dodaj 'a' (Dodaj 'b' PraznaLista)
ghci>:t x
Lista Char
ghci> y = Dodaj True (Dodaj False PraznaLista)
ghci>:t y
Lista Bool

Definicije funkcija dužina, spoji, obrni ostaju gotovo iste, ali se tipovi menjaju tako da se u njima pojavljuje tipska promenljiva. Na ovaj način ove funkcije postaju polimorfne i mogu se koristiti sa svim tipovima lista:

dužina :: Lista a -> Int
dužina PraznaLista = 0
dužina (Dodaj _ xs) = 1 + dužina xs  

spoji :: Lista a -> Lista a -> Lista
spoji PraznaLista xs = xs
spoji (Dodaj x xs) ys = Dodaj x (spoji xs ys)

obrni :: Lista a -> Lista a
obrni PraznaLista = PraznaLista
obrni (Dodaj x xs) = spoji (obrni xs) x 

Zadatak 5. Za tip Lista a implementirati funkcije koje odgovaraju funkcijama filter, map, zip i fold.

Novi tip je takođe zgodno dodati u klasu Show. Implementacija funkcije show će biti potpuno ista kao implementacija te funkcije za tip ListaBrojeva. Ali sada moramo bi malo pažljiviji sa klasnim ograničenjima. Za svaki tip T, implementacija show :: Lista T -> String koristi u sebi implementaciju funkcije show :: T -> String, te je neophodno postaviti uslov o tipu T pri dekleraciji instance Show (Lista T)⁴.

instance Show a => Show (Lista a) where
    show xs = "<" ++ prikaži xs ++ ">"
        where
            prikaži PraznaLista = ""
            prikaži (Dodaj y PraznaLista) = show y
            prikaži (Dodaj y ys) = show y ++ ", " ++ prikaži ys

Zadatak 6. Uvesti tipove Lista a u klase Eq i Ord, Functor i Applicative.

Liste u Haskelu

U Haskelu liste su implementirane upravo onako kako smo i mi to gore uradili:

data [] a = [] | a : ([] a) 

Sa navedenim kodom je definisan jedan apstraktni tip [] :: * -> *. Pod istim imenom je definisan i konstruktor prazne liste []. Drugi konstruktor je konstruktor "dodavanja" :. Kako se ime : sastoji od specijalnog znaka, a ne slova, taj konstruktor je infiksni konstruktor⁵, te se navodi između argumenata.

Haskell kompajler dozvoljava da se tip [] a zapiše kao [a]. Ovaj izuzetak u Haskell sintaksi značajno poboljšava čitljivost tipova. Takođe, izuzetak postoji i konstrukciji samih vrednosti, te se vrednost a:b:c:[], može zapisati i kao [a, b, c] i slično.

Stabla

Za liste se kaže da su linearne strukture podataka, jer elementi na prirodan način čine niz. Svaki element liste, osim poslednjeg, poseduje jedinstvenog sledbenika. Isto tako, svaki element, osim prvog, poseduje jedinstvenog prethodnika. Koliko god liste bile korisne, liste nisu uvek najbolji izbor za reprezentaciju podataka.

Stablo je rekurzivna struktura podataka sačinjena od čvorova, u kojoj svaki čvor sadrži vrednost i nekoliko manjih stabala (od kojih neka mogu biti prazna). Specijalno, binarno stablo je stablo u kom svaki čvor sadrži vrednost i dva manja stabla⁶.

Tip binarnog stabla koje sadrži u sebi vrednosti tipa Int možemo kreirati na sledeći način: prazno stablo ćemo kreirati sa nularnim konstruktorom PraznoStablo, dok ćemo čvorove kreirati sa konstruktorom Čvor. Konstruktor Čvor zavisi od tri parametara: vrednosti tipa Int, kao i od dve vrednosti tipa StabloBrojeva:

data StabloBrojeva =
    PraznoStablo
    | Čvor Int StabloBrojeva StabloBrojeva
    deriving (Show, Eq)

Primer 2.

Vrednost

stablo1 = Čvor 1
    (Čvor 2 PraznoStablo PraznoStablo)
    (Čvor 3 PraznoStablo PraznoStablo)

predstavlja naredno stablo sa tri čvora:

Ovo stablo je sačinjeno od čvora koji sadrži vrednost \(1\) kao i dva manja stabla. Ta dva manja stabla su sačinjena od po jednog čvora koji sadrži vrednost \(2\), odnosno \(3\). Ovi čvorovi u sebi sadrže prazna stabla (koje ne predstavljamo na slikama).

Za čvor \(1\) kažemo da je roditelj čvorova \(2\) i \(3\), dok za čvorove \(2\) i \(3\) često kažemo i da su deca čvora \(1\). Za jedinstveni čvor koji se nalazi na samom vrhu stabla, ovde je to \(1\), kažemo da je koren stabla. Za čvorove koji nemaju decu kažemo da su listovi stabla: u ovom stablu to su \(2\) i \(3\).

Primer 3.

Naredna vrednost predstavlja stablo sa šest čvorova:

stablo2 = Čvor 5
    (Čvor 3
        (Čvor 2 PraznoStablo PraznoStablo)
        (Čvor 4 PraznoStablo PraznoStablo))
    (Čvor 6
        NilInt
        (Čvor 8 PraznoStablo PraznoStablo))

U ovom stablu, \(5\) je koren, a čvorovi \(2\), \(4\) i \(8\) su listovi. Primetimo da u stablu čvor \(6\) ima samo jedno dete.

Stabla su pogodne strukture podataka za modelovanje mnogih odnosa koje srećemo u svakodnevnici⁷.

Prvo bi bilo zgodno napisati funkciju brojČvorova koja određuje broj čvorova u stablu⁸. Naravno, funkciju ćemo implementirati rekurzivno, podudaranjem vrednosti po konstruktorima. Broj čvorova u praznom stablu je \(0\). Broj čvorova u stablu Čvor a l r je za jedan veći od zbira broja čvorova u podstablima l i r:

brojČvorova :: StabloBrojeva -> Int
brojČvorova PraznoStablo = 0
brojČvorova (Čvor _ l r) = 1 + brojČvorova l + brojČvorova r

ghci> brojČvorova stablo1
3
ghci> brojČvorova stablo2
6

Još jedna numerička karakteristika je visina stabla koja predstavlja najveći broj koraka od korena stabla do nekog lista. Drugim rečima, visina stabla predstavlja broj "generacija" prisutnih u stablu. Visinu stabla ćemo takođe izračunati rekurzivno: visina praznog stabla je \(0\), a visina stabla Čvor a l r je maksimum visina stabala l i r uvećan za jedan:

visinaStabla :: StabloBrojeva -> Int
visinaStabla PraznoStablo = 0
visinaStabla (Čvor _ l r) = 1 + max (visinaStabla l) (visinaStabla r)

ghci> visinaStabla stablo1
2
ghci> visinaStabla stablo2
3

Korisna je i funkcija koja proverava da li se neka vrednost nalazi u stablu⁹. Strategija za pretragu je sledeća: ako čvor sadrži vrednost koju tražimo, tada se pretraga završava. U suprotnom, pretragu nastavljamo rekurzivno, pretražujući oba stabla:

elementStabla :: Int -> StabloBrojeva -> Bool
elementStabla _ PraznoStablo = False
elementStabla v (Čvor a l r)
    | v == a = True
    | v /= a = elementStabla v l || elementStabla v r

ghci> elementStabla 6 stablo1
False
ghci> elementStabla 6 stablo2
True

Zadatak 7. Implementirati funkciju zbir :: StabloBrojeva -> Int koja sabira vrednosti svih čvorova u stablu.

Zadatak 8. Implementirati funkciju dupliraj :: StabloBrojeva -> StabloBrojeva koja duplira vrednost svakog čvora, dok samu strukturu stabla ne menja.

Zadatak 9. Implementirati funkciju najveći :: StabloBrojeva -> Int koja pronalazi najveći element u stablu.

Uređena stabla

Stabla u kojima vrednost u svakom čvoru je veća od svake vrednosti u odgovarajućem levom podstablu, i manja od svake vrednosti odgovarajućem desnom podstablu, nazivamo uređena stabla.

Zadatak 10. Napisati funkciju uređeno :: StabloBrojeva -> Bool koje proverava da li je stablo uređeno.

Uređene stabla su veoma korisna jer se neki algoritmi mogu efikasno implementirati. Na primer, prilikom pretrage uređenog stabla često je potrebno izvršiti značajno manje poređenja: ako tražimo neku vrednost \(m\) u stablu čiji korenski čvor je \(n\) tada je dovoljno nastaviti pretragu samo u levom (odnosno desnom) podstablu ako je \(m < n\) (odnosno ako je \(m > n\)). Oslanjajući se na činjenicu da je korenski čvor veći (odnosno manji) od svih vrednosti u levom (odnosno desnom) podstablu, možemo ignorisati jedno od podstabala. Kôd za pretragu uređenog podstabla je sledeći:

elementUređenogStabla :: Int -> StabloBrojeva -> Bool
elementUređenogStabla v (Čvor a l r)
    | v == a = True
    | v <  a = elementUređenogStabla v l
    | v >  a = elementUređenogStabla v r  

Kao što vidimo iz prethodnog primera, pretraga uređenog stablo može biti značajno efikasnija nego pretraga neuređenog stabla. Zaista, ako je dato stablo koje poseduje \(n\) generacija, tada to stablo može posedovati \[2^0 +2^1 + 2^2 + \cdots + 2^n = 2^{n+1} - 1\] čvorova. Pretraga ovakvog stabla bi u najgorem slučaju zahtevala \(2^{n+1} - 1\) rekurzivnih poziva funkcije (računajući i prvi poziv), jer je neophodno da algoritam obiđe sve čvorove da bi dao definitivan odgovor. Sa druge strane, ako je to stablo uređeno, tada je u najgorem slučaju dovoljno izvršiti samo \(n\) rekurzivnih poziva.

Zadatak 11. Implementirati funkciju najvećiUređeno :: StabloBrojeva -> Int koja pronalazi najveći element u uređenom stablu.

Apstraktni tip stabla

Naravno, u čvorovima stabla korisno je postavljati i vrednosti drugih tipova osim Int. Stoga je zgodno napraviti apstraktni tip Stablo :: * -> * koji će omogućiti uopštenu konstrukciju binarnog stabla. Jedini parametar ovog apstraktnog tipa, biće tip koji označava tip vrednosti sadržane u čvoru. Gore navedenu rekurzivnu definiciju je potrebno neznatno izmeniti:

data Stablo a = PraznoStablo | Čvor a (Stablo a) (Stablo a)
    deriving (Show, Eq)

Funkcije poput brojČvorova i visinaStabla imaju potpuno istu definiciju ali im se tip neznatno menja:

brojČvorova :: Stablo a -> Int
brojČvorova PraznoStablo = 0
brojČvorova (Čvor _ l r) = 1 + brojČvorova l + brojČvorova r

visinaStabla :: Stablo a -> Int
visinaStabla PraznoStablo = 0
visinaStabla (Čvor _ l r) = 1 + max (visinaStabla l) (visinaStabla r)

Funkcija elementStabla mora koristiti operator (==) :: Eq a => a -> a -> a. Stoga je potrebno da i tip funkcije elementStabla bude ograničen Eq klasom. Osim toga, definicija funkcije je potpuno ista:

elementStabla :: Eq a => a -> Stablo a -> Bool
elementStabla _ PraznoStablo = False
elementStabla v (Čvor a l r)
    | v == a = True
    | v /= a = elementStabla v l || elementStabla v r

Ako želimo da govorimo i o uređenim stablima, tada se moramo ograničiti na klasu Ord.

Zadatak 12. Implementirati funkciju uređeno :: Ord a => Stablo a -> Bool koje proverava da li je stablo uređeno.

Zadatak 13. Implementirati funkciju elementUređenogStabla :: Ord a => a => Stablo a -> Bool koje proverava da li vrednost pripada uređenom stablu.

Stabla kao funktori

U jednoj od prethodnih lekcija obradili smo funktore. Funktor je apstraktni tip T :: * -> * koji dozvoljava implementaciju funkcije mapiranja fmap :: (a -> b) -> T a -> T b, koja zadovoljava određene osobine. Na primeru lista i možda-tipova, uvideli smo da o fmap možemo misliti kao o funkciji koja primenjuje prosleđenu funkciju na svaku vrednost tipa a sadržanoj u vrednosti tipa T a, pri čemu se sama struktura vrednosti tipa T a čuva.

I goredefinisani tip Stablo :: * -> * može biti instanca klase Functor. Primetimo prvo da Stablo je odgovarajuće vrste * -> *. Zatim, ako razmislimo o tome šta fmap radi na primeru drugih funktora, lako se dolazi do ideje da fmap primenjuje datu funkciju na vrednost u svakom čvoru stabla¹⁰.

instance Functor Stablo where
    fmap f (Stablo a l r) = Stablo (f a) (fmap f l) (fmap f r)
    fmap _ PraznoStablo   = PraznoStablo

Potrebno je uveriti se da ovako definisana fmap funkcija zadovoljava dve zakonitosti:

1. Podizanje identičke funkcije je identička funkcija, tj fmap id = id
2. Podizanje kompozicije je kompozicija podizanja, tj. fmap (g. f) = fmap g . fmap f.

Zakone možemo dokazati totalnom indukcijom po visini stabla. Na primer, dokažimo prvi zakon¹¹. Baza indukcije su stabla visine \(0\), a to su prazna stabla. Funkcija fmap id primenjena na vrednost PraznoStablo je po definiciji PraznoStablo. Dalje, za induktivni korak pretpostavimo da tvrđenje važi za sva stabla čija visina je ne veća od \(n\) i dokažimo da onda važi i za stabla visine \(n+1\). Neka je Stablo a l r stablo visine \(n+1\). Funkcija fmap id primenjena na vrednost Stablo a l r je po definiciji Stablo (id a) (fmap id l) (fmap id r) = Stablo a (fmap id l) (fmap id r). Kako su l i r stabla visine ne veće od \(n\), po induktivnoj pretpostavci važi da je fmap id l = l i fmap id r = r. Prema tome, primena funkcije fmap id na vrednost Stablo a l r daje istu tu vrednost. Indukcijom sledi da ovo važi za sva stabla, pa je fmap id zaista id :: Stablo a -> Stablo a.

Zadatak 14. Klasa Functor definiše i operator <$ kao fmap . const. Šta u kontekstu instance Functor Stablo, radi operator <$?

Zadatak 15. Kreirati tip TernarnoStablo :: * -> * koji predstavlja stablo u kom svaki element ima tri direktna potomka. Implementirati funkcije za rad sa ovim tipom. Instancirati Functor TrenarnoStablo

Aritmetički izrazi

Česta primena rekurzivnih tipova podataka je predstavljanje izraza (bilo matematičkih izraza, bilo izraza nekog programskog jezika). Izrazi su vrednosti koji koje mogu biti neograničeno složenosti, zbog čega su rekurzivni tipovi zaista neophodni za njihovo predstavljanje¹². Na primer, ako posmatramo izraze koji su sačinjeni samo od prirodnih brojeva, sabiranja i množenja, tada lako možemo naći neograničeno mnogo izraza, pri čemu složenost svakog izraza je proizvoljno velika, npr: \[1+1,\] \[22 * (1 + 6),\] \[((10+32) * 18) * (333 + 4)...\]

Da bismo našli pogodan način predstavljanja matematičkih izraza, za primer pogledajmo rekurzivnu strukturu izraza \[(17 + 3) * (10 * (1 + 1)).\] Navedeni izraz predstavlja zbir dva manja izraza \(17 + 3\) i \(10 * (1 + 1)\). Prvi od tih izraza je zbir dva broja, dok je drugi proizvod broja i još manjeg izraza \(1 + 1\). Na ovom primeru vidimo da su izrazi sačinjeni od manjih izraza ili brojeva koji se kombinuju uz pomoć dve operacije.

Navedeno razmatranje nas dovodi do rekurzivne definicije tipa Izraz. Vrednosti tipa Izraz konstruisaćemo na tri načina. Prvo, svaki prirodan broj za sebe čini izraz. Drugo, ako su data dva izraza, onda je i njihov zbir izraz. Treće, ako su data dva izraza onda je i njihov proizvod izraz:

data Izraz =
    Broj Int
    | Zbir Izraz Izraz
    | Proizvod Izraz Izraz

Primer 6.

Sada izraz \(22 * (1 + 6)\) možemo da predstavimo sa vrednošću: Proizvod (Broj 22) (Zbir (Broj 1) (Broj 6)). Ova vrednost se može predstaviti i kao naredno stablo:

Kao što vidimo vrednosti tipa Izraz se mogu shvatiti kao stabla, čiji listovi su brojevi, dok ostali čvorovi predstavljaju operacije sabiranja ili množenja. Stabla poput ovih nazivamo sintaksna stabla. Sa sintaksnim stablima se mogu prezentovati matematički izrazi ali izrazi nekog programskog jezika¹³, i predstavljaju ključni koncept programe poput kompajlera i interpretera.

Naravno, novodefinisani tip želimo da uvedemo u neke klase. Najkorisnije je implementirati funkciju show, koja je će izraz predstaviti u obliku na koji smo do sada navikli.

instance Show Izraz where
    show (Broj a) = show a
    show (Zbir a b) = "(" ++ show a ++ "+" ++ show b ++ ")"
    show (Proizvod a b) = "(" ++ show a ++ "*" ++ show b ++ ")"

Druga funkcija koju je najlogičnije implementirati je funkcija izračunaj :: Izraz -> Int, koja izraz sračunava izraz u jedinstvenu vrednost. Funkciju implementiramo rekurzivno: sračunavanjem broja se dobija taj isti broj, dok se sračunavanjem zbira (proizvoda) dva izraza dobija zbir (proizvod) vrednosti koje su dobijene sračunavanjem odgovarajućih podizraza:

izračunaj :: Izraz -> Int
izračunaj (Broj a) = a
izračunaj (Zbir a b) = izračunaj a + izračunaj b
izračunaj (Proizvod a b) = izračunaj a * izračunaj b

Zadatak 16. Kreirati tip MatematičkiIzraz čije vrednosti mogu da prezentuju matematičke izraze sačinjene od nepoznate \(x\), realnih brojeva, operacija sabiranja, oduzimanja, množenja, deljenja i stepenovanja kao i funkcija poput sinusa i kosinusa. Napisati funkciju koja izračunava ove izraze u zavisnosti od vrednosti nepoznate. Implementirati funkciju koja računa izvod matematičkog izraza.

Zadatak 17. Za ovaj zadatak je neophodno uraditi prethodni zadatak Ako ste upoznati sa LaTeX jezikom za zapisivanje matematičke notacije, konstruišite funkciju uLatex :: MatematičkiIzraz -> String koja daje LaTeX kôd za dati izraz. Koristite LaTeX naredbe poput \times, ^, \frac, \left( i \right), i tako dalje...

Zadatak 18. Definisati tip LogičkiIzraz koji predstavlja logičke izraze sačinjene od logičkih vrednosti i operacija konjunkcije i disjunkcije. Uvesti tip LogickiIzraz u Show klasu tipova. Implementirati funkciju izracunajLogički :: LogičkiIzraz -> Bool koja izračunava zadati logički izraz.

Zadatak 19. Za ovaj zadatak je neophodno uraditi prethodni zadatak Neka je data funkcija f :: Int -> Bool sa f x = x \=0. Konstruisati funkciju konvertuj :: Izraz -> LogičkiIzraz koja logički izraz prevodi u aritmetički izraz tako što sabiranje prevodi u disjunkciju, množenje u konjunkciju a brojeve u skladu sa datom funkcijom f. Na primer, izraz 2 * (7 + 0) se konvertuje u \(\top\land(\top\lor\bot).\) Da li važi f . izračunaj = izracunajLogički . konvertuj

Parsiranje matematičkih izraza

Gore smo definisali instancu Show Izraz na sasvim jednostavan način. Kako to obično biva, obrnuti proces je značajno komplikovaniji za implementaciju. Međutim, tehnika aplikativnih parsera koju smo predstavili u lekciji o funktorima, može nam pomoći u ovom slučaju. Sa parserom kog budemo konstruisali, moći ćemo da iz niske pročitamo vrednost Izraz.

Pre nego što počnemo sa definisanjem parsera, moramo tačno definisati oblik niska koje ćemo parsirati. Na primer, složeni parseri izraza mogu ispravno parsirati izraze poput "2 + 5" ili "2*-7+6" jer su napravljeni tako da ignorišu beline (razmake), da vode računa o prioritetu operacija, podržavaju unarni operator negacije, itd... Da bi maksimalno skratili naredne redove, mi nećemo kreirati ovako složeni parser. Parser koji budemo konstruisali moći će da parsira samo one izraze koji su nastali sa funkcijom show :: Izraz -> String tj, izraze sačinjene isključivo od cifara i znakova +, -, (, ), pri čemu se oko svakog podizraza nalaze zagrade (osim oko samih brojeva).

Kako je i sama struktura tipa Izraz rekurzivna, i parser tipa Parser Izraz biće rekurzivan. Posebno ćemo konstruisati parser izrazBroj koji parsira brojeve, parser izrazZbir koji parsira zbir dva manja izraza, i parser izrazProizvod koji parsira proizvod dva manja izraza.

Pretpostavimo da su navedeni parseri definisani. Jedan izraz može biti broj, proizvod ili zbir manjih izraza. Zbog toga, da bi parsirali izraz, prvo ćemo pokušati da parsiramo broj. Ako to ne uspemo, onda ćemo pokušati da parsiramo zbir, a ako ni to ne uspemo pokušaćemo da parsiramo proizvod¹⁴. Sa kombinatorom ili lako dobijamo željeni parser:

izraz :: ParserIzraz
izraz = izrazBroj `ili` izrazZbir `ili` izraz 

Ostaje još definisati izrazBroj, izrazZbir i izrazProizvod. Parser izrazBroj ćemo lako definisati pomoću parsera broj :: Parser Int kog posedujemo od ranije. Sve što je potrebno je da parsiranu vrednost (koja je tipa Int), transformišemo u vrednost tipa Izraz, što se naravno postiže podizanjem konstruktora Broj :: Int -> Izraz na nivo funktora Parser:

izrazBroj :: Parser Izraz
izrazBroj = fmap Broj broj

Parser izrazZbir mora da funkcioniše na sledeći način: prvo je neophodno parsirati simbol za levu zagradu, zatim je potrebno parsirati levi sabirak, pa simbol plus, desni sabirak, i na kraju simbol desne zagrade. Rezultati parsiranja simbola nisu bitni (ako su uspešni), a rezultate parsiranja levog i desnog sabirka moramo ukombinovati u vrednost oblika Zbir x y :: Izraz. Naravno, u tome će nam pomoći podizanje konstruktora Zbir. Takođe, kako su oba sabirka izrazi sami za sebe, potrebno ih je parsirati sa izraz parserom. Ovo uspostavlja rekurziju.

izrazZbir :: Parser Izraz
izrazZbir =
    simbol '(' *>
    (Zbir <$> (izraz <* simbol '+') <*> izraz)
    <* simbol ')' 

Parsiranje proizvoda je u potpunosti analogno parsiranju zbira:

izrazProizvod :: Parser Izraz
izrazProizvod = 
    simbol '(' *>
    (Proizvod <$> (izraz <* simbol '*') <*> izraz)
    <* simbol ')' 

Testiranjem se uveravamo da parser funkcioniše:

ghci> parsiraj izraz "(1+2)"
Just ("",(1+2))
ghci> parsiraj izraz "((10+2)*32)"
Just ("",((10+2)*32))

Samo jedan korak nas deli od implementacije primitivnog kalkulatora. Sve što je potrebno uraditi je primeniti funkciju izračunaj na rezultat parsiranja. Ali, kako je rezultat parsiranja tipa Maybe (String, Izraz), neophodno je proći funkcijom izračunaj kroz Maybe i (String, ).

parsirajIzračunaj :: String -> Maybe Int
parsirajIzračunaj s = fmap (izračunaj . snd) (parsiraj izraz s)

ghci> parsirajIzračunaj "(2+(4*3))"
Just 14