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.
Vаž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 elmenta 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 konstruisti 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 elment 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 mormo 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 apstrakti), te je stoga drugi parametar Lista a
a ne Lista
. Ovim je i utvrđena homegenost 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 implemenatcija 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 jedinsvenog sledbenika. Isto tako, svaki element, osim prvog, poseduje jedinstvenog prethodnika. Koliko god liste bile korisne, liste nisu uvek najbolji izbor za reprezentaju 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 predstavlajmo 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\).
Vrednost
stablo2 = Čvor 5 (Čvor 3 (Čvor 2 PraznoStablo PraznoStablo) (Čvor 4 PraznoStablo PraznoStablo)) (Čvor 6 NilInt (Čvor 8 PraznoStablo PraznoStablo))
predstalja stablo sa šest čvorova:
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 odnosа 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 karkteristika 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živajuć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 postabla (č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 korisiti 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 vrednosi drugih tipova osim Int
. Stoga je zgodno napraviti apstraktni tip Stablo :: * -> *
koji će omogućiti uopštenu konstrukciju binarnog stabla. Jedini parametar ovog apstraktong 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 elmentStabla
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 kalsu 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žnoj 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 racionalnih 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.3232) * 18) * (333 + 4.04)...\]
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 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 Float | Zbir Float Float | Proizvod Float Float
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 predstvaljaju operacije sabiranja ili množenja. Stabla poput ovih nazivamo sintaksna stabla. Sa sintaksnim stablima se mogu prezentovati matematički izrazi ali izrazi nekog programskog jezika13, 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 ++ ")"
Kako to obično biva, pisanje funckcije read
14 koja generiše vrednost tipa Izraz
na osnovu niske je znatno složenije. Generalno, problem kreiranja sintaksnog stabla na osnovu tekstualnog podatka (tj. niske), nazivamo parsiranje. Parsiranje je značajno težak problem, i mi ćemo u nekoj od narednih lekcija videti jednu od tehnika implementacije parsera15
Druga funkcija koju je najlogičnije implementirati je funkcija izračunaj :: Izraz -> Float
, koja izraz sračunava izraz u jedinsvenu 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 -> Float izračunaj (Broj a) = ako 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činjenje 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 zadatk Ako ste upoznati sa LaTeX jezikom za zapisivanje matematičke notacije, konstruišite funkciju uLatex :: MatematičkiIzraz -> String
koja daje Latex kod za dati izraz. Koristite LaTeX naredbe poput \times
, ^
, \frac
, \left(
i \right)
, i tako dalje...
Zadatak 18. Napraviti tip LogickiIzraz
koji predstavlja logičke izraze sačinjenje od logičkih vrednosti i operacija konjunkcije i disjunkcije. Uvesti tip LogickiIzraz
u Show
klasu tipova. Implementirati funkciju izracunajLogicki :: LogickiIzraz -> Bool
koja izračunava zadati logički izraz.
Zadatak 19. Za ovaj zadatak je neophodno uraditi prethodni zadatk Neka je data funkicja f :: Int -> Bool
sa f x = x \=0
. Konstruiasti funkciju konvertuj :: LogickiIzraz -> Izraz
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 . izracunajAritmeticki = izracunajLogicki . konvertuj