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. Definicija tipa T sada će počinjati sa data T = …, a umesto jednog konstruktora od sada ćemo potencijalno 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 novog tipa, a 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 definisati kao proizvod tipova Float i Float na sledeći način:

data Vektor = Vektor Float Float deriving (Show)

Vrednosti se konstruiš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 proizvod 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)¹. Svaku vrednost tipa Osoba možemo konvertovati u vrednost tipa ([Char], Int, Bool) i obrnuto².

Sličnost nije slučajna, jer 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 (,)
(,) :: * -> * -> *

Zadatak 2. Koristeći proizvod tipova (bez korišćenja uređenih parova), definisati tip kompleksnih brojeva Kompleksan oslanjajući se na Double vrednosti. Instancirati Num Kompleksan i Fractional Kompleksan.

Jedinični tip

Konstrukcija proizvoda tipova ima oblik K T₁ T₂ … Tₙ, gde su T₁, ... Tₙ 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, odnosno 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 shvati 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 različ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 jedinicama

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 različite vrednosti, iako se svaka od ovih vrednosti dobila primenom konstruktora na 1 :: Float

Napomenimo da poredak konstruktora u sumi nije od značaja. Tako na primer, definicija data SlovoIliBroj = Slovo Char | Broj Int definiše isti³ 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 definicije⁴ 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 susreli sa više tipova koji su suma jediničnih tipova (a da to nismo ni znali):

Logički tip Bool je definisan kao suma jediničnih tipova True i False.
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 3. Kreirati algebarski 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 4. 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 neophodno 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.

Zadatak 5. U lekciji o rekurziji pokazan je zadatak sa Hanojskim kulama. U tom zadatku, iskoristili smo tip Char da bismo predstavili različite štapove (\(A\), \(B\) ili \(C\)). Definisati tip Štap koji sadrži tri vrednosti, i prepraviti rešenje pomenutog zadataka tako da se umesto tipa Char koristi novi tip.

Možda-tip

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

5. Nešto poput vrednosti null ili undefined u nekim jezicima

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čitavamo 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 temperaturu (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 prezentovanje rezultata 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

Funkcija ć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 funkcije 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 prethodnoj funkciji, ako je jedan od argumenata Nista, vrednost Nista i vraćamo.

Slično tipu MoždaBroj možemo konstruisati⁶ tip MoždaNiska:

6. Obratite pažnju da u istom modulu nije moguće definisati tip MoždaBroj i MoždaNiska jer imaju istoimeni konstruktor Ništa. Naravno, rešenje je da promenim ime konstruktora u npr NištaNiska ili BezNiske. U nastavku ćemo radi jednostavnosti zadržati naziv Ništa.

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 Prelidu:

data Maybe t = Just t | Nothing

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

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

Just True, Just False i Nothing.

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

Just (Just True), Just (Just False), 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 8. 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 zapis⁷. 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,
    mestoStanovanja :: 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,
    mestoStanovanja = "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, mestoStanovanja :: 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 jezicima⁸. Što se tiče promene vrednosti koordinate (odnosno setera), to se može izvršiti navođenjem labele sa novom vrednošću koordinate:

8. Na primer, kôd ime osoba2 odgovara nečemu što bi se Javi/C++-u napisalo kao osoba2.ime.

ghci> ime osoba1
"Petar"
ghci> osoba3 = osoba1{ime = "Miloš"}
ghci> ime osoba3
"Miloš"

Vrednosti koordinata vrednosti osoba3 su iste kao odgovarajuće vrednosti koordinata osoba2, osim vrednosti labela koja je "Miloš".

Pri podudaranju oblika, moguće je "uhvatiti" samo labele koje su nam 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 {mestoStanovanja = mesto, adresaStanovanja = adresa})
    = mesto ++ ", " ++ adresa

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

Zadaci

Zadatak 9. 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 10. Kreirati algebarski tip Valuta koji može da predstavi neke valute (npr, RSD, EUR, USD) i funkcije koje vrše konverziju između ovih valuta. Kreirati algebarski tip Svota koji sadrži jednu vrednost tipa Float i vrednost tipa Valuta. Kreirati algebarski tip Banka koji predstavlja nekoliko domaćih banaka. Kreirati tip Račun koji sadrž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 proizvoljnu 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 11. Kreirati tip Tačka koji predstavlja tačku u dvodimenzionalnoj ravni. Kreirati tip Figura koji može da predstavi pravougaonik, 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 12. Kreirati tip KompleksanBroj. Implementirati funkcije koje sabiraju, oduzimaju, množe i dele kompleksne brojeve.

Zadatak 13. Kreirati tip Matrica koji predstavlja matricu dimenzija \(3\times 3\). Kreirati funkcije koje sabiraju matrice, skaliraju matricu, i računaju determinantu matrice. Kreirati tip Vektor koji predstavlja vektor trodimenzionalno prostora. Kreirati funkciju koja množi matricu i vektor.