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
Ovde, 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.

Primer 1.

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.

Primer 2.

Naredni tip prestavlja jednu osobu (njeno ime, godine, i to da li je državljanin Srbije): 

data Osoba = Osoba String Int Bool deriving (Show)
Ovde, kao i u nekim prethodnim primerima sa newtype konstrukcijom, tip i konstruktor imaju isto ime

Pri 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 () = ()
Ovo je još jedan primer gde konstruktor i tip imaju isto ime.

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.

Primer 3.

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
Vrednosti 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.

Primer 4.

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
tipovi nisu jedinični (npr. 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.

Primer 5.

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
Fuknkcija će vratiti vrednost oblika 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
Neke funkije sy takve, da i dve "dobre" vrednosti, mogu da daju "lošu" vrednost. Deljenje nulom nije definisano, pa slučaju kada je 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.