Algebarski tipovi podataka

Do sada smo videli kako možemo kreirati nove tipove koristeći newtype konstrukciju. U ovoj lekciji 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 konstruktor.

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 "dekonstruiš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 Vektor = 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: 

dužinaVektora :: Vektor -> Float
dužinaVektora (Vektor x y) = sqrt (x**2 + y**2)

ghci> dužinaVektora 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 dozvoljava da se ovaj konstruktor upotrebljava na malo drugačiji način, pa se može 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 vrednostima tipova A i B. Suma tipova može se shavati kao unija dva tipa. 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 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 sa podudaranjem oblika. Svaka vrednost tipa SlovoIliBroj može biti ili oblika Slovo x ili oblika Broj x, te podudaramo takve oblike: 

daLiJeSlovo :: SlovoIliBroj -> Bool
daLiJeSlovo (Slovo x) = True
daLiJeSlovo (Broj x) = False

Moguće je "sabrati" više tipova istovremeno, odnosno navesti više od dva konstruktora.

Primer 4.

Sledeći tip označava dužinu u različitim mernim jednicama 

data Dužina = Metar Float | Milja Float | SvetlosnaSekunda Float
                deriving (Show)

Za tip Dužina možemo da definišemo ovakvu funkciju konverzije: 

uMetre :: Dužina -> Dužina
uMetre (Milja x) = Metar (1609.344 * x)
uMetre (SvetlosnaSekunda x) = Metar (299792458 * x)
uMetre x = x

Tip Dužina 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 dobila primenom konstruktora na 1 :: Int

Napomenimo da poredak konstruktora u sumi nije od značaja. Tako na primer, definicija data SlovoIliBroj = Slovo Char | Broj Int definiše isti3 tip kao i definicija data SlovoIliBroj = Broj Int | Slovo Char. Za razliku od toga, u proizvodima poredak tipova je bitan. Tako na primer, definicija data SlovoIBroj = SIB Int Char je sasvim različita od definicije4 data SlovoIBroj = SIB Char Int

Suma jediničnih tipova

Jedinični tipovi nisu mnogo korisni sami po sebi, ali su veoma korisni kada se koriste unutar sume. Na primer, sada lako (i logično) možemo da predstavimo tipove sa konačno mnogo članova (takozvane enumeracije): 

data Pol = Muško | Žensko

data ZnakKarte = Herc | Karo | Tref | Pik

data Boje = Crna | Bela | Crvena | Plava | Zelena | Žuta

Do sada smo se sureli sa više tipova koji su suma jediničnih tipova (a da to nismo ni znali):

  1. Logički tip Bool je definisan kao suma jediničnih tipova True i False.
  2. Tip Ordering je definisan kao suma jediničnih tipova LT, EQ i GT. Podsećamo da se vrednosti ovog tipa koriste kao rezultati poređenja.
Zadatak 2. Kreirati alegbarski tip Ruka, koji može predstavljati papir, kamen ili makaze. Kreirati funkciju uporedi :: Ruka -> Ruka -> Ordering koja određuje poredak među različitim rukama.
data Ruka = Papir | Kamen | Makaze

uporedi :: Ruka -> Ruka -> Ordering
uporedi Kamen  Kamen  = EQ
uporedi Papir  Papir  = EQ
uporedi Makaze Makaze = EQ
uporedi Makaze Papir  = GT
uporedi Kamen  Makaze = GT
uporedi Papir  Kamen  = GT
uporedi _      _      = LT
Zadatak 3. Kreirati algebarski tip Dan čije vrednosti prezentuju dane u nedelji.
data Dan = Ponedeljak
    | Utorak
    | Sreda
    | Četvrtak
    | Petak
    | Subota
    | Nedelja
Radi preglednosti zgodno je definiciju prelomiti u više linija. Pri prelomu, nije neohodno da svaki konstruktor bude u posebnoj liniji niti je neophodno da uspravne crte budu jedna ispod druge. Neophodno je samo da da definicija nije podeljena na više delova sa praznim linijama.

Možda-tip

Sada ćemo kreirati tip MoždaBroj kojim možemo da predstavimo ili jedan Float broj ili izostanak bili kakve smislene vrednosti5. Ovaj tip ćemo konstrusati kao sumu tipa Float i jediničnog tipa Ništa: 

data MoždaBroj = SamoBroj Float | Ništa

Tip MoždaBroj 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 MoždaBroj tip za prezentovnje očitavanja senzora. Vrednost poput SamoBroj 2 označava da je temperatura zaista 2°C, dok vrednost Ništa označava da do očitavanja nije došlo.

Sa MoždaBroj vrednostima nije lako raditi kao sa Float vrednostima, ali nije ni preteško napisati funkcije koje su nam potrebne: 

apsolutnaRazlika :: MoždaBroj -> MoždaBroj -> MoždaBroj
apsolutnaRazlika (SamoBroj x) (SamoBroj y) = SamoBroj $ abs $ x - y
apsolutnaRazlika _ _ = Ništa
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 :: MoždaBroj -> MoždaBroj -> MoždaBroj
podeli (SamoBroj x) (SamoBroj y) = 
    if y == 0
        then Ništa
        else SamoBroj $ x / y
podeli _ _ = Ništa
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 MoždaBroj možemo konstruisati6 tip MoždaNiska: 

data MoždaNiska = SamoNiska String | Ništa

Konstrukcija tipa je MozdaNiska je u potpunosti analogna konstrukciji tipa MoždaBroj. Jasno je da je ovakva konstrukcija korisna za bilo koji tip, stoga možemo definisati naredni apstraktni tip 

data Možda t = Samo t | Ništa

Upravo ovako je definisan apstraktni tip Maybe koji je dostupan u Prelude-u: 

data Maybe t = Just t | Nothing

Od sada, svaki tip oblika Maybe a nazivaćemo možda-tip.

Zadatak 4. Koje vrednosti sadrži tip Maybe Bool?

Just True, Just False i Nothing.

Zadatak 5. Koje vrednosti sadrži tip Maybe (Maybe Bool)?

Just (Just True), Just (Just False), Just (Just Nothing) i Nothing

Totalne funkcije sa možda tipovima

Možda-tipovi se često koriste da bi se parcijalnim funkcijama pridružile odgovarajuće totalne funkcije. Ideja je da se za one vrednosti domena za koje je funkcija nedefinisana, prosto vrati Nothing vrednost.

Primer 6.

Funkcija head :: [a] -> a koja vraća glavu niza nije totalna: pozivanje head [] dovodi do izuzetka, jer prazan niz nema glavu. Zbog toga, u jednom od standardnih modula, definisana je funkcija maybeHead: 

maybeHead :: [a] -> Maybe a
maybeHead []  = Nothing
maybeHead x:_ = Just x

Dakle, ako niz nije prazan maybeHead će vratiti glavu niza upakovanu u Just. Ako je niz prazan, maybeHead će vratiti Nothing.

Zadatak 6. Definisati totalne varijante funkcija tail, init, last koristeći možda tipove.

Zapisi

Koliko god proizvod tipova delovao korisno, u nekim situacijama pristupanje elementima proizvoda može dovesti do glomaznog i nečitljivog koda.

Primer 7.

Na svakoj elektronskoj ličnoj karti su sačuvane i sledeće niske: ime, prezime, mesto stanovanja, adresa stanovanja, kao i broj koji predstavlja godinu rođenja. Ako formiramo novi tip koji će u sebi sadržati navedene informacije, dolazimo do glomazne definicije: 

data Osoba = MkOsoba String String String String Int
Primetimo da iz ove definicije ne znamo koja koordinata predstavlja koju informaciju. Jednino znamo da koordinata tipa Int predstavlja godinu rođenja. Ovu dvosmislenost možemo rešiti pisanjem komentara pored definicije

Možemo se odlučiti da prva niska predstavlja ime, druga prezime, treća mesto a četvrta adresu. Tada funkcije za rad sa tipom Osoba deluju poput sledećih: 

punoIme :: Osoba -> String
punoIme (MkOsoba ime prezime _ _ _)
    = ime ++ " " ++ prezime

punaAdresa :: Osoba -> String
punaAdresa (MkOsoba _ _ mesto adresa _)
    = adresa ++ ", " ++ ime

punoletna :: Int -> Osoba -> MyBool
punoletna trenutnaGodina (MkOsoba _ _ _ _ godinaRođenja)
    = trenutnaGodina - godinaRođenja >= 18

Osim što dekonstrukcije podatka daju dugačak kod, programer je u obavezi da pamti šta svaka od koordinata u proizvodu predstavlja. Takođe, veliki problem se javlja kada se definicija tipa promeni nakon što su funkcije napisane. Tada je potrebno izmeniti svako podudaranje oblika u kodu, što može biti zahtevan posao.

Da bi se sprečili problemi opisani u primeru, i olakšao programerima posao, Haskel dozvoljava nešto drugačiju definiciju proizvoda koju nazivamo zapis7. U definiciji zapisa svakoj od koordinata se dodeljuje ime - labela, koje se može kasnije iskoristiti za pristupanje toj koordinati. Niz imena koordinata se navodi u vitičastim zagradama.

Nastavljajući priču iz prošlog primera, možemo definisati tip Osoba kao zapis: 

data Osoba = MkOsoba {
    ime :: String,
    prezime :: String,
    godinaRođenja :: Int,
    mestoStanovaja :: String,
    adresaStanovanja :: String,
}

Vrednosti tipa Osoba je i dalje moguće konstruisati navođenjem vrednosti nakon konstruktora, ali je moguće i iskorititi sintaksu za zapise: 

osoba1 = MkOsoba "Petar" "Petrović" 2000 "Beograd" "Njegoševa"

osoba2 = MkOsoba {
    ime = "Jovana",
    prezime = "Jovanović",
    godinaRođenja = 1990,
    mestoStanovaja = "Novi Sad",
    adresaStanovanja = "Zmaj Jovina",
}
Korišćenjem sintakse za zapise, programer nije u obavezi da ispoštuje redosled koordinata, ali mora navesti vrednosti za svaku koordinatu.

Definisanjem tipa Osoba sintaksom za zapise, zapravo je kreirano šest funkcija ime :: Osoba -> String, prezime :: Osoba -> String, godinaRođenja :: Osoba -> Int, mestoStanovaja :: Osoba -> String, adresaStanovanja :: Osoba -> String. Ove funkcije se nazivaju projekcije, i vraćaju vraćaju odgovarajuće koordinate: 

ghci> :t ime
ime :: Osoba -> String
ghci> ime osoba1
"Petar"
ghci> ime osoba2
"Jovana"

Prema tome, labele zapisa se koriste poput getera u objektno orijentisanim jezicima8. Što se tiče promene vrednosti koordinate (odnosno setera), to se može izvrštiti navođenjem labele sa novom vrednošću koordinate: 

ghci> ime osoba1
"Petar"
ghci> osoba3 = osoba1{ime = "Miloš"}
ghci> ime osoba3
"Miloš"
Vrednosti kordinata vrednosti osoba3 su iste kao odgovarajuće vrednosti koordinata osoba2, osim vrednosti labela koja je "Miloš".

Pri poklapanju šablona, moguće je "uhvatiti" samo labele koje su potrebne. Tako bi se funkcije od malopre mogla ovako napisati: 

punoIme :: Osoba -> String
punoIme (MkOsoba {ime = ime, prezime = prezime})
    = ime ++ " " ++ prezime

punaAdresa :: Osoba -> String
punaAdresa (MkOsoba {mestoStanovaja = mesto, adresaStanovanja = adresa})
    = mesto ++ ", " ++ adresa

punoletna :: Int -> Osoba -> MyBool
punoletna trenutnaGodina (MkOsoba {godinaRođenja = godinaRođenja})
    = trenutnaGodina - godinaRođenja >= 18

Zadaci

Zadatak 7. 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 8. 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 Račun koji sadži vrednost tipa Int (broj računa) i vrednost tipa Banka (predstavlja banku u kojoj je otvoren račun). Tip Račun 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 Račun 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 promenaNaRačunu:: Račun -> 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 9. Kreirati tip Tačka 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 površina :: 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 10. Kreirati tip KompleksanBroj. Implemenitari funkcije koje sabiraju, oduzimaju, množe i dele kompleksne brojeve.

Zadatak 11. Kreirati tip Matrica koji predstavlja matricu dimenzija \(3\times 3\). 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.