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še1
Liste
Konstruisaćemo tip ListaBrojeva
čije vrednosti su liste s celobrojnim vrednostima2. 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
Listu od tri elementa 1
, 2
, 3
možemo konstruisati kao DodajBroj 1 (DodajBroj 2 (DodajBroj 3 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 zagrade3. 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
obrni
koristi u sebi drugu rekurzivnu funkciju spoji
, zbog čega ova implementacija nije najefikasnija moguća.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
Dodaj
moraju biti navedeni konkretni tipovi (a ne apstraktni), te je stoga drugi parametar Lista a
a ne Lista
. Ovim je i utvrđena homogenost liste tj. obezbeđeno je da sve vrednosti moraju biti istog tipa. Na primer, ako posmatramo tip Lista Int
tada konstruktor Dodaj
ima tip Int -> Lista Int -> Lista Int
, tj. Dodaj
može dodati samo vrednost tipa Int
na listu tipa Lista Int
. Induktivno sledi da vrednost Lista Int
sadrži samo vrednosti tipa Int
.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)
4.
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 konstruktor5, 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 stabla6.
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)
Show StabloBrojeva
i Eq StabloBrojeva
su sasvim dovoljne za nas.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\).
Naredna vrednost predstavlja stablo sa šest čvorova:
stablo2 = Čvor 5 (Čvor 3 (Čvor 2 PraznoStablo PraznoStablo) (Čvor 4 PraznoStablo PraznoStablo)) (Čvor 6 PraznoStablo (Č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 svakodnevnici7.
Prvo bi bilo zgodno napisati funkciju brojČvorova
koja određuje broj čvorova u stablu8. 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
stablo1
i stablo2
su definisana u prethodnim primerima.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 stablu9. 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.
Stablo stablo1
nije uređeno jer je vrednost u korenskom čvoru manja od vrednosti u levom podstablu.
Stablo stablo2
je uređeno jer je \(3\) veće od \(2\) a manje od \(4\), \(6\) je manje od \(8\), a \(5\) je veće \(3\), \(2\) i \(4\), i manje od \(6\) i \(8\).
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
Funkcija elementStabla
primenjena na vrednosti 8
i stablo2
će imati sledeći tok: pošto je vrednost korenskog čvora (5
) različita od 6
, funkcija će rekurzivno proveriti da li se vrednost 6
nalazi u levom podstablu. Pri toj pretrazi, funkcija ponovo rekurzivno proverava vrednosti čvorova \(3\), \(2\) i \(5\). Pošto levo podstablo ne sadrži traženu vrednost, prelazi se na desno podstablo. Prvo se proverava vrednost korena tog podstabla (čvor \(6\)), a zatim se prelazi na desno dete, gde se pronalazi tražena vrednost. Primetimo da je algoritam obišao celokupno stablo pri pretrazi.
Pogledajmo sada izvršavanje funkcije elementUređenogStabla
primenjene na iste vrednosti 8
i stablo2
(ovo stablo je uređeno, te ima smisla koristiti ovu funkciju). Pošto је tražena vrednost veća od vrednosti korenskog čvora \(5\), algoritam rekurzivno nastavlja pretragu na desnom podstablu. Vrednost 8
je takođe veća od vrednosti (sada korenskog) čvora \(6\), te se ponovo prelazi na desno podstablo. Međutim korenski čvor sada poseduje traženu vrednost, i pretraga se uspešno prekida. Primetimo da smo obišli samo dva čvora pre nego što smo prekinuli pretragu.
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)
StabloBrojeva
. Imena su namerno ostavljena ista, da bi bilo jasnije o čemu se radi.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 stabla10.
instance Functor Stablo where fmap f (Stablo a l r) = Stablo (f a) (fmap f l) (fmap f r) fmap _ PraznoStablo = PraznoStablo
Functor
klase, dovoljno je implementirati fmap
funkciju.Potrebno je uveriti se da ovako definisana fmap
funkcija zadovoljava dve zakonitosti:
- Podizanje identičke funkcije je identička funkcija, tj
fmap id = id
- 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 zakon11. 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 predstavljanje12. 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
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 i izrazi nekog programskog jezika, te je stoga ova struktura ključna za 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 bismo 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 proizvod13. 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))
show
, ovo sintaksno stablo se prikazuje na sasvim jednostavan način.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