Algebarski tipovi podataka
Do sada smo videli kako možemo kreirati nove tipove koristeći newtype
konstrukciju. U ovoj glavi predstavićemo jedan opštiji način kreiranja novih tipova. Prva razlika u ovom načinu kreiranja tipova je ta što se umesto ključne reči newtype
koristi data
. Definicije tipa T
sada će počinjati sadata T = ...
, a umesto ...
sada ćemo imati više konstruktora.
Tipove ćemo kreirati od postojećih tipova koristeći dve operacije: proizvod i sumu. Ove operacije odgovaraju pojmovima Dekartovog proizvoda i unije u teoriji skupova. Kao što ćemo uvideti, sličnost se ne završava na tome: proizvod i suma tipova poštuju zakone iz algebre skupova (ali i mnoge zakone algebre prirodnih brojeva). Upravo zbog toga se i ovako dobijeni tipovi nazivaju algebarski tipovi podataka.
Proizvod
Proizvod dva tipa A
i B
je tip čije vrednosti odgovaraju kombinacijama vrednosti tipova A
i B
. Proizvod tipova u Haskelu se jednostavno konstruiše na sledeći način:
data P = MkP A B
P
je naziv definisanog proizvoda, MkP
je konstuktor.Svaka vrednost gore definisanog tipa P
, je oblika MkP a b
gde su a :: A
i b :: B
neke vrednosti. Podudaranje oblika dozvoljava da vrednosti tipa P
"dekonstuišemo" na ovaj način.
Vektor dvodimenzionalne ravni možemo definsati kao proizvod tipova Float
i Float
na sledeći način:
data Vektor2D = Vektor Float Float deriving (Show)
Vrednosti se konstrišu sa konstruktorom:
ghci> v = Vektor 2 1
Konstruktor se koristi i za dekonstrukciju vrednosti sa tehnikom podudaranja oblika:
duzinaVektora :: Vektor -> Float duzinaVektora (Vektor x y) = sqrt (x**2 + y**2)
ghci> duzinaVektora v 2.23606797749979
Nije nužno postaviti iste tipove u proizvod, niti ih mora biti dva.
Naredni tip prestavlja jednu osobu (njeno ime, godine, i to da li je državljanin Srbije):
data Osoba = Osoba String Int Bool deriving (Show)
newtype
konstrukcijom, tip i konstruktor imaju isto imePri radu sa tipom Osoba
takođe koristimo podudaranje oblika. Ako želimo da "izvučemo" ime iz osobe, možemo napisati narednu funkciju:
imeOsobe :: Osoba -> String imeOsobe (Osoba ime _ _) = ime
Prethodna funkcija odgovara onome što u objektno orijentisanim jezicima nazivamo getter (metoda kojom se pristupa nekom atributu objekta). Lako je implementirati i setter, tj. funkciju koja menja jednu vrednost u proizvodu:
promeniIme :: String -> Osoba -> Osoba promeniIme novoIme (Osoba _ godine drzavljanin) = Osoba novoIme godine drzavljanin
Zadatak 1. Napisati getere i setere za sva polja vrednosti tipa Vektor
i Osoba
.
Proizvod tipova može da sadrži i samo jedan tip. U tom slučaju porozvod je ekvivalentan newtype
konstrukciji koju smo ranije upoznali.
Uređene \(n\)-torke kao proizvodi tipova
Pažljiv čitalac će uvideti da smo koncept proizvoda tipova već imali kod uređenih \(n\)-torki. I zaista tip Osoba
iz prethodnog primera je u nekom smislu ekvivalentan tipu ([Char], Int, Bool)
1. Svaku vrednost tipa Osoba
možemo konvertovati u vrednost tipa ([Char], Int, Bool)
i obrnuto2.
Sličnost nije slučajna, uređene \(n\)-torke jesu proizvodi tipova. Na primer, uređen par je apstraktni tip definisan sa data (,) a b = (,) a b
. Slično su definisane i druge uređene \(n\)-torke data (,,) a b c = (,,) a b c
, data (,,,) a b c d = (,,,) a b c d
i tako dalje. Primetimo da tipovi i konstruktori imaju isto ime!
Haskel kompajler da se ovaj konstruktor upotrebljava na malo drugačiji način, pa možemo pisati (1, 'a')
umesto (,) 1 'a'
.
Koliko god ovo delovalo čudno, možemo se zaista uveriti da (,)
jeste jedno ime koje dele konstruktor tipa i konstruktor vrednosti:
ghci> :t (,) (,) :: a -> b -> (a, b) ghci> :k (,) (,) :: * -> * -> *
Jedinični tip
Konstrukcija proizvoda tipova ima oblik K T1 T2 T3 ... Tn
, gde su T1
, ... Tn
neki tipovi, a K
konstruktor. U specijalnom slučaju možemo napraviti proizvod čiji konstruktor ne uzima ni jedan dodatni tip:
data T = K
Konstruktor K
je funkcija arnosti 0, odnsno konstanta tipa T
. Drugim rečima, tip T
sadrži samo jednu vrednost a to je K
. Zbog toga za T
takođe kažemo da je jedinični tip baš kao za ()
. Zapravo, tip ()
je takođe definisan kao prazan proizvod:
data () = ()
Suma
Suma dva tipa A
i B
je tip koji sadrži vrednosti koje odgovaraju svim vrednosti tipova A
i B
. Suma tipova se vrši navođenjem više konstruktora razdvojenih vertikalnom crtom. Svaki od konstruktora predstavlja konstruktor proizvoda, i može imati proizvoljno mnogo argumenata.
Tip SlovoIliBroj
koji sadrži i slova i brojeve može se konstruisati kao
data SlovoIliBroj = Slovo Char | Broj Int deriving (Show)
Sada postoje dva konstruktora koja konstrišu vrednosti:
ghci> a1 = Slovo 'a' ghci> a2 = Broj 2 ghci> :t a1 a1 :: SlovoIliBroj ghci> :t a2 a2 :: SlovoIliBroj
a1
i a2
imaju isti tip, iako predstavljaju razlčite oblike podataka.Konstruktore koristimo i sa podudaranjem oblika. Svaka vrednost tipa SlovoIliBroj
može biti li oblika Slovo x
ili oblika Broj x
:
daLiJeSlovo :: SlovoIliBroj -> Bool daLiJeSlovo (Slovo x) = True daLiJeSlovo (Broj x) = False
Moguće je "sabrati" više tipova od jednom, odnosno navesti više od dva konstruktora.
Sledeći tip označava dužinu u različitim mernim jednicama
data Duzina = Metar Float | Milja Float | SvetlosnaSekunda Float deriving (Show)
Za tip Duzina
možemo da definišemo ovakvu funkciju konverzije:
uMetre :: Duzina -> Duzina uMetre (Milja x) = Metar (1609.344 * x) uMetre (SvetlosnaSekunda x) = Metar (299792458 * x) uMetre x = x
Tip Duzina
predstavlja uniju tri Float
tipa. Ali iako su tipovi u sumi isti, ova unija je disjunktna. Drugim rečima vrednosti Metar 1
, Milja 1
i SvetlosnaSekunda 1
su međusobno potpuno razlčite vrednosti, iako se svaka od ovih vrednosti dobiila primenom konstruktora na 1 :: Int
Suma jediničnih tipova
Ovakva konstrukcija nije mnogo korisna sama po sebi, ali je veoma korisna kada se koristi unutar suma. Na primer, sada lako (i logično) možemo da predstavimo tipove sa konačno mnogo članova (takozvane enumeracije):
data Pol = Musko | Zensko
ZnakKarte
sadrži 4 vrednosti), ali su dobijeni sumom jedničnih tipova.data ZnakKarte = Herc | Karo | Tref | Pik
data MojeBoje = Crna | Bela | Crvena | Plava | Zelena | Zuta
Možda tip
Sada ćemo kreirati tip MozdaBroj
kojim možemo da predstavimo ili jedan Float
broj ili izostanak bili kakve smislene vrednosti3. Ovaj tip ćemo konstrusati kao sumu tipova Float
i jediničnog tipa Nista
:
data MozdaBroj = SamoBroj Float | Nista
Tip MozdaBroj
je koristan kad god hoćemo da radimo u programu sa nekim vrednostima koje možda nisu ni zadate.
Ako očitvamo temperaturu s nekog senzora, onda je dobro to očitavanje predstaviti Float
vrednošću. U nekim situacijama naš senzor ne mora vraćati očitanu tempraturu (usled nekih hardverskih problema, itd...), i tada treba koristiti specijalnu vrednost koja označava da do očitavanja temperature nije ni došlo. Nezgodno bi bilo koristiti vrednost 0 (ili neku drugu vrednost) jer se tada ne mogu razlikovati ispravna očitavanja temperature 0°C od neispravnih.
Stoga je u ovom slučaju zgodno koristiti MozdaBroj
tip za prezentovnje očitavanja senzora. Vrednost poput SamoBroj 2
označava da je temperatura zaista 2°C, dok vrednost Nista
označava da do očitavanja nije došlo.
Sa MozdaBroj
vrednostima nije lako raditi kao sa Float
vrednostima, ali nije ni preteško napisati funkcije koje su nam potrebne:
apsolutnaRazlika :: MozdaBroj -> MozdaBroj -> MozdaBroj apsolutnaRazlika (SamoBroj x) (SamoBroj y) = SamoBroj $ abs $ x - y apsolutnaRazlika _ _ = Nista
SamoBroj i
kad god prosledimo dve vrednosti istog oblika. U svim drugim slučajevima, barem jedna od prosleđenih vrednosti će biti Nista
, i stoga smisla vratiti samo vrednost Nista
podeli :: MozdaBroj -> MozdaBroj -> MozdaBroj podeli (SamoBroj x) (SamoBroj y) = if y == 0 then Nista else SamoBroj $ x / y podeli _ _ = Nista
y == 0
vraćamo Nista
. Kao i u prethonoj funkciji, ako je jedan od argumenata Nista
, vrednost Nista
i vraćamo.Slično tipu MozdaBroj
možemo konstruisati tip MozdaNiska
:
data MozdaNiska = SamoNiska String | Nista
Konstrukcija tipa je MozdaNiska
je u potpunosti analogna konstrukciji tipa MozdaBroj
. Jasno je da je ovakva konstukcija korisna za bilo koji tip, stoga možemo definisati naredni apstraktni tip
data Mozda t = Samo t | Nista
Upravo ovako je definisan apstraktni tip Maybe
koji je dostupan u Prelude-u:
data Maybe t = Just t | Nothing
Zadaci
Zadatak 2. Kreirati algebarski tip podataka Vektor
koji predstavlja vektor u trodimenzionalnom prostoru (Koristiti Float
tip za koordinate). Kreirati funkcije za sabiranje vektora, množenje vektora skalarem, skalarnog množenja vektora, vektorskog množenja vektora i računanja dužine vektora.
Zadatak 3. Kreirati algebarski tip Valuta
koji može da predstavi neke valute (npr, RSD, EUR, USD) i funkcije koje vrše koverziju između ovih valuta. Kreirati algebarski tip Svota
koji sadrži jednui vrednost tipa Float
i vrednost tipa Valuta
. Kreirati algabarski tip Banka
koji predstavlja nekoliko domaćih banaka. Kreirati tip Racun
koji sadži vrednost tipa Int
(broj računa) i vrednost tipa Banka
(predstavlja banku u kojoj je otvoren račun). Tip Racun
se koristi samo za identifikaciju, i nema u sebi podatke o promeni računa. Kreirati algebarski tip Transakcija
koji sadrži vrednost tipa Svota
, a zatim dve vrednosti tipa Racun
koje predstavljaju račun sa kog se šalje odnosno na koji se šalje novac. Kreirati jednu proizvoljanu listu Transakcija
od 5 članova ili više. Kreirati funkciju promenaNaRacunu:: Racun -> Transakcija -> Svota
koja računa promenu stanja računa nakon svih izvršenih transakcija. Pretpostaviti da račun može da prime svote novca u bilo kojoj valuti. Krajnju promenu iskazati u evrima.
Zadatak 4. Kreirati tip Tacka
koji predstavlja tačku u dvodimenzionalnoj ravni. Kreirati tip Figura
koji može da predstavi pravugaonik, krug, trougao, i proizvoljni pravilni mnogougao u ravni. Kreirati funkcije povrsina :: Figura -> Float
i obim :: Figura -> Obim
koje redom računaju površinu i obim figura. Kreirati funkciju transliraj :: (Float, Float) -> Figura -> Figura
koja translira (pomera) figuru. Kreirati funkciju skaliraj :: Float -> Figura -> Figura
koja skalira figuru za uneti faktor.
Zadatak 5. Kreirati tip KompleksanBroj
. Implemenitari funkcije koje sabiraju, oduzimaju, množe i dele kompleksne brojeve.
Zadatak 6. Kreirati tip Matrica
koji predstavlja matricu dimenzija 3x3. Kreirati funkcije koje sabiraju matrice, skalirraju matricu, i računaju determinantu matrice. Kreirati tip Vektor
koji predstavlja vektor trodimenzionalno prostora. Kreirati funkciju koja množi matricu i vektor.