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
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.
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.
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 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 () = ()
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.
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
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.
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):
- Logički tip
Bool
je definisan kao suma jediničnih tipovaTrue
iFalse
. - Tip
Ordering
je definisan kao suma jediničnih tipovaLT
,EQ
iGT
. 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
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.
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
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
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.
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.
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
Int
predstavlja godinu rođenja. Ovu dvosmislenost možemo rešiti pisanjem komentara pored definicijeMož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", }
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š"
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.