Tipske klase

Tipska klasa predstavlja kolekciju tipova koji imaju neke zajedničke osobine. Te zajedničke osobine izražavaju se kroz funkcije koje je moguće pozivati nad svim tipovima te klase. Svaki tip koji pripada nekoj klasi naziva se instanca te klase.

Klasa se definiše dekleracijom klase nakon koje sledi niz dekleracija tipova nekih funkcija koje instanaca mora da implementira:

class C a where
  f1 :: T1
  f2 :: T2 
  ....
Ovde a je tipska promenljiva koja predstavlja instancu klase C. Tipovi T1, T2,... mogu (i ne moraju) da sadrže tipsku pormenljivu a.

Da bi neki tip T pridružili klasi tipova C, koristimo narednu konstrukciju nakon koje slede definicije funkcija koje propisuje klasa:

instance K T where
  f1 = ...
  f2 = ... 
  ...

Jedan primer

Gotovo da nema uvodne knjige o programiranju u nekom jeziku koja ne sadrži primer sa geometrisjkim figurama poput pravougaonika, trougla i kruga. Implementirati strukture koje predstavljaju figure i funkcije koje računaju obim i površinu figura je jednostavno u svakom popularnom jeziku, ali može da pozluži za odličnu ilustraciju mnogobrojnih pojedinosti nekog programskog jezika. Nama će poslužiti da ilustrujemo zašto su klase tipova korisne.

Prvo ćemo definisati tri tipa podatka koji predstavljaju figure u Dekartovoj ravni:

  1. Svaki pravougaonik se može odrediti sa jednim temenom, širinom i visinom (jednostavnosti radi, pretpostavljamo da su stranice pravougaonika paralelne sa koordinatnim osama). Kako teme možemo predstaviti sa dve koordinate, ceo kvadrat možemo predstaviti sa četiri Double vrednosti.
  2. Trougao je u potpunosti određen sa tri temena. Prema tome, za predstavljanje trougla nam je potrebna struktura podataka koja sadrži šest Double vrednosti.
  3. Krug je određen centrom i poluprečnikom. Stoga struktura koja predstavlja krug sadrži tri Double vrednosti.

Kada znamo šta strukture sadrže, lako ih je implementirati kao uređene \(n\)-torke:

newtype Pravougaonik = Pravougaonik (Double, Double, Double, Double)
  deriving Show

newtype Trougao = Trougao (Double, Double, Double, Double, Double, Double)
  deriving Show

newtype Krug = Krug (Double, Double, Double)
  deriving Show
Za sada možda nije jasno šta navedene koordinate predstavljaju, ali ćemo kroz naredni kod ustanoviti na šta se koordinate odnose.

Implementacija funkcija koje računaju obim navedenih figura je takođe jednostavna:

obimPravougaonika :: Pravougaonik -> Double
obimPravougaonika (Pravougaonik (x, y, a, b)) = 2 * (a + b)

obimTrougla :: Trougao -> Double
obimTrougla (Trougao (x1, y1, x2, y2, x3, y3)) = a + b + c
  where
    a = sqrt $ (x1 - x2)^2 + (y1 - y2)^2
    b = sqrt $ (x2 - x3)^2 + (y2 - y3)^2 
    c = sqrt $ (x3 - x1)^2 + (y3 - y1)^2 

obimKruga :: Krug -> Double
obimKruga (Krug (x, y, r)) = 2 * pi * r 
Za računanje obima trougla, prvo smo izračunali dužinu stranica korišćenjem Pitagorine teoreme.

Navedeni kod je u potpunosti tačan. Ali u ovakvom pristupu se krije mali problem: pisanjem koda za rad sa figurama zahteva od nas da koristimo tri različite funkcije (obimPravougaonika, obimTrougla, obimKruga). Bilo bi jednostavnije kada bismo mogli primeniti jedinstvenu funkciju obim na svaku figuru1.

Da bismo koristili jedinstvenu funkciju obim sa sva tri tipa, definisaćemo klasu Figura. Pošto želimo da sa svakom instancom klase Figura koristimo funkciju obim u definiciji klase ćemo navesti samo jednu dekleraciju tipa.

class Figura a where
  obim :: a -> Double
Dekleracije koje klasa pruža moraju biti nazubljene za jedan nivo (barem jedan razmak), u odnosu na liniju class ....

Linijom class ... započinje se blok definicije klase. Sve linije (nakon prve) u ovom bloku moraju biti nazubljene u odnosu na prvu liniju2. Blok se prostire sve dok se ne stigne do linije koja nije nazubljena.

Tipska promenljiva a u liniji class Figura a where predstavlja instancu klase Figura. Ova promenljiva, kao i svaka druga, može biti proizvoljno imenovana. Svako pojavljivanje promenljive a unutar bloka odnosi se na isti tip.

Navedeni kôd već možemo učitati u GHCi. Korišćenjem komande :type možemo uvideti da je tip funkcije obim dat sa Figura a => a -> Double. Ovo nam govori da se funkcija obim može primeniti samo na neki vrednost tipa a, pri čemu taj tip a pripada klasi Figura. Za sada takvi tipovi ne postoje, potrebno je tipove Pravougaonik, Trougao i Krug učininiti instancama klase Figura.

Pošto klasa Figura pripisuje samo jednu funkciju (obim), instacinaranje podrazumeva implementaciju funkcije obim za svaki od navedenih tipova.

instance Figura Pravougaonik where
  obim (Pravougaonik (x, y, a, b)) = 2 * (a + b)

instance Figura Trougao where
  obim (Trougao (x1, y1, x2, y2, x3, y3)) = a + b + c
    where
      a = sqrt $ (x1 - x2)^2 + (y1 - y2)^2
      b = sqrt $ (x2 - x3)^2 + (y2 - y3)^2 
      c = sqrt $ (x3 - x1)^2 + (y3 - y1)^2 

instance Figura Krug where
  obim (Krug (x, y, r)) = 2 * pi * r
Definicije funkcija su u potpunosti iste kao definicije funkcija obimPravougaonika, obimTrougla, obimKruga.

Linijom instance ... započinje se blok definicija funkcija. Kao i kod definicije klase, sve u ovom bloku mora biti nazubljeno u odnosu na početak linije.

U bloku definicija, neophodno je definisati sve funkcije koje klasa deklariše3. U bloku definicija ne navode se dekleracije tipova!

Nakon učitavanja navedenih definicija u GHCi, možemo se uveriti da povrsina može da se primenjuje na razne tipove figura

ghci> trougao = Trougao (0, 0, 1, 0, 0, 1)
ghci> obim trougao
3.414213562373095
ghci> pravougaonik = Pravougaonik (0, 0, 2, 2)
obim pravougaonik
8.0
ghci> krug = Krug (0, 0, 10)
ghci> obim krug
62.83185307179586

Figure osim što imaju obim, imaju i površinu. Stoga ćemo u definiciju klase Figura dodati i dekleraciju funkcije povrsina koja nam daje površinu figure. Sada u svakoj instanci moramo implementirati i funkciju povrsina. Površinu Pravougaonika i kruga ćemo lako izračinati, a za površinu trougla ćemo iskoristiti Heronovu formulu. Kompletan kôd sada izgleda ovako:

class Figura a where
  obim :: a -> Double
  povrsina :: a -> Double


instance Figura Pravougaonik where
  obim (Pravougaonik (x, y, a, b)) = 2 * (a + b)

  povrsina (Pravougaonik (x, y, a, b)) = a * b


instance Figura Trougao where
  obim (Trougao (x1, y1, x2, y2, x3, y3)) = a + b + c
    where
      a = sqrt $ (x1 - x2)^2 + (y1 - y2)^2
      b = sqrt $ (x2 - x3)^2 + (y2 - y3)^2 
      c = sqrt $ (x3 - x1)^2 + (y3 - y1)^2
  
  povrsina (Trougao (x1, y1, x2, y2, x3, y3)) = sqrt . prod $ [s, s-a, s-b, s-c]
      where
        a = sqrt $ (x1 - x2)^2 + (y1 - y2)^2
        b = sqrt $ (x2 - x3)^2 + (y2 - y3)^2
        c = sqrt $ (x3 - x1)^2 + (y3 - y1)^2
        s = (a + b + c) / 2


instance Figura Krug where
  obim (Krug (x, y, r)) = 2 * pi * r
  
  povrsina (Krug (x, y, r)) = pi * r^2

Više o klasama tipova naučićemo na primerima poznatih klasa koje su već definisane u Haskelu.

Equality

U klasi Eq nalaze se svi tipovi čije vrednosti je moguće porediti pomoću funkcija == i /=. Definicija klase Eq je sasvim jednostavna:

class Eq a where
  (==) :: a -> a -> Bool
  (/=) :: a -> a -> Bool

Klasa Eq deklariše dva operatora koje vraćaju logičke vrednosti. Ta dva operatora služe za poređenje vrednosti tipa a.

Primer 1.

Definišimo tip koji predstavlja racionalan broj. Kako je svaki racionalan broj oblika \(a/b\) za neka sva cela broja \(a\) i \(b\ne 0\), to tip Racionalan možemo definisati kao uređen par celih brojeva:

newtype Racionalan = R (Int, Int)

Pokušaj korišćenja vrednosti tipa Racionalan sa operatorima klase Eq dovešće do greške, jer tip Racionalan nije intanca ove klase:

ghci> a = R (1, 2)
ghci> b = R (5, 10) 
ghci> a == b 

<interactive>:1:3: error:
    • No instance for (Eq Racionalan) arising from a use of ‘==’
    • In the expression: a == b
      In an equation for ‘it’: it = a == b

Da bismo mogli da poredimo vrednosti tipa Racionalan, instaniraćemo Eq Racionalan:

instance Eq Racionalan where
    (Racionalan (a, b)) == (Racionalan (c, d)) = a * d == c * b
    (Racionalan (a, b)) /= (Racionalan (c, d)) = a * d /= c * b

Ponovnim učitavanjem koda u GHCi, dobijamo mogućnost poređenja vrednosti tipa Racionalan:

ghci> a = R (1, 2)
ghci> b = R (5, 10) 
ghci> a == b 
True
ghci> a /= b
False 

Primetimo da deluje nepotrebno definisati obe funkcije == i /=. Zaista, ako bi smo poznavali jednu od ove dve funkcije, bilo bi prirodno da izvedemo onu drugu kao njenu negaciju (ako su dve vrednosti jednake onda nisu različite, i obrnuto). Haskel jezik nam omogućuje i to. Osim što u klasi možemo deklarisati tipove funkcija, možemo definisati i neke od tih funkcija preko ostalih a zatim navesti minimalni skup funkcija koje moraju biti definisane u instanci4.

Konkretno, puna definicija klase Eq je5:

class Eq a where
  (==), (/=)           :: a -> a -> Bool
  
  x /= y               = not (x == y)
  x == y               = not (x /= y)
  { -# MINIMAL (==) | (/=) #-}

Linija {-# MINIMAL (==) | (/=) #-}, koja samo podseća na komentar, naziva se pragma, i služi da kompajleru ukaže da je barem jednu od funkcija == i /= dovoljno i potrebno implementirati. Kroz naredne primere upoznaćemo se detaljnije sa sintaksom pragme MINIMAL.

Svaka od te dve funkcije se može izvesti preko one druge, i u samoj definiciji klase Eq su navedena ta izvođenja. Međutim, da se ne bismo vrteli u krug sa definicijama6, svaka instanca Eq klase mora sadržati barem jednu od definicija funkcija == i /=.

Primer 2.

Nastavak prethodnog primera. Za instacu Racionalan, dovoljno je napisati sledeće

instance Eq Racionalan where
    (Racionalan (a, b)) == (Racionalan (c, d)) = a * d == c * b
Umesto definicije za ==, mogli smo da napišemo i samo definiciju za /=.

Ordering

Klasu Ord čine svi tipovi koje je moguće porediti pomoću funkcija <, <=, > i >=. Definicija klase Ord je sledeća:

class (Eq a) => Ord a where
    compare              :: a -> a -> Ordering
    (<), (<=), (>), (>=) :: a -> a -> Bool
    max, min             :: a -> a -> a

    compare x y = if x == y then EQ
                  else if x <= y then LT
                  else GT

    x <= y = case compare x y of
      GT -> False;
      _ -> True

    x >= y = y <= x
    x > y = not (x <= y)
    x < y = not (y <= x)

    max x y = if x <= y then y else x
    min x y = if x <= y then x else y
    { -# MINIMAL compare | (<=) #-}

Ovde vidimo nešto drugačiju definiciju klase. Umesto sa class Ord a where definicija klase započinje sa class (Eq a) => Ord a where. Izraz (Eq a) => predstavlja klasno ograničenje. Kao i kod tipova vrednosti, klasnim ograničenjima ograničavamo skup tipova koji mogu biti postavljeni na mesto tipske promenljive a. U ovom slučaju, sa klasnim ograničenjem garantujemo da će neki tip pripadati nekoj drugoj klasi pre nego što ga pridružimo ovoj klasi.

U slučaju klase Ord, ima smisla zahtevati da tip već pripada klasi Eq jer pojam jednakosti vrednosti neophodan za razlikovanje funkcija > i >=7. Prema tome, klasa Ord je podklasa klase Eq.

Klasa Ord propisuje funkciju compare :: a -> a -> Ordering koja upoređuje dve vrednosti, uobičajne relacije (operatore koje vraćaju logičke vrednosti) za poređenje elementa kao i dve binarne funkcije min i max koje respektivno vraćaju manji odnosno veći od argumenata.

Tip Ordering je tip koji sadržati tri vrednosti LT, EQ, GT koje označavaju rezultat poređenja dve vrednosti. Vrednost compare a b je LT, EQ, GT ako je vrednost a strogo manja, jednaka, strogo veća od vrednosti b.

Definicije operatora <, >, >= koriste operator <= i prilično su jasne. Jasne su i definicije binarnih funkcija min i max koje takođe koriste operator <=. Operator <= je definisan preko funkcije compare. Funkcija compare preko funkcije <=. Kao i kod klase Eq, i ovde imamo slučaj beskonačne rekurzije kroz definicije. Stoga je potrebno, i dovoljno, u instanci definisati samo jednu od funkcija <= ili comapre.

I ovde imamo MINIMAL pragmu koja sugeriše kompajleru da je neophodno da instanca sadrži barem definiciju funkcije comapre ili <=. U instanci je moguće definisati i ostale funkcije (u tom slučaju te definicije instance će potisnuti definicije u definiciji klase), ali za tako nečim gotovo nikad nema potrebe.

Primer 3.

Načinimo tip Racionalan instancom Ord klase. Pošto smo već u prethodnim primerima implemetirali Eq Racionalan instancu, dovoljno je da implementiramo compare funkciju.

instance Ord Racionalan where
  compare (R (a, b)) (R (c, d)) = compare (a * d) (c * b)
U implementaciji smo iskoristili činjenicu da je odnos između brojeva \(a/b\) i \(c/d\) isti kao odnos između brojeva \(a\cdot d\) i \(c \cdot b\).

Show i Read

Klasu Show čine oni tipovi čije se vrednosti mogu prezentovati u vidu niske. Za nas je važno da definicija klase Show podrazumeva funkciju show:

class Show a where
  show :: a -> String
Ovde nismo naveli kompletnu definiciju klase, ali je dovoljno znati da minimalno instanciranje Show klase podrazumeva samo implementaciju funkcije show.

Klasa Show je neophodna za ispisivanje vrednosti u GHCi okruženju. Do sada smo koristili deriving (Show) konstrukciju koja je omogućavala da se tip automatski pridruži Show klasi tj . da se izvede instanca. Sada znamo kako možemo implementirati sopstvene instance.

Primer 4.

Ako želimo da izvedemo Show Racionalan, dovoljno je definiciju tipa promenimo u sledeću:

newtype Racionalan = R (Int, Int) deriving (Show)

Pri izvođenju, show funkcija će kreirati nisku koja liči veoma na sam kod s kojim je konstruisana vrednost.

ghci> a = R (2, 3)
ghci> show a
"R (2,3)"
ghci> a
R (2,3)
Kada u GHCi unesemo neki izraz, taj izraz će se evaluirati, i dobijena vrednost će se prikazati kao niska dobijena primenom show funkcije.

Za tip Racionalan je bolje implementirati posedbnu show funkciju, i ne koristiti izvođenje. U tom slučaju treba ukloniti deriving (Show), a dodati instancu Show Racionalan:

instance Show Racionalan where
  show (R (x, y)) = show x ++ "/" ++ show y
Primetimo da u definiciji koristimo takođe show funkciju, ali primenjenu na celobrojne vrednosti. Možemo da kažemo da show sa leve i desne strane znaka =, ne predstavljaju iste funkcije.

Prikazivanje vrednosti je sada smislenije:

ghci> a = R (2, 3)
ghci> show a
"2/3"
ghci> a
2/3

Klasa Read je suprotnost klasi Show. Instance klase Read su tipovi čije se vrednosti mogu "pročitati" iz niske. Kako je "čitanje" vrednosti iz niske značajno složenije nego zapisivanje u nisku i definicija klase Read je složenija. Stoga ovde nećemo navoditi definiciju klase.

Zgodno je ipak znati za funkciju read :: Read a => a -> String koja se može koristiti sa instancama klase Read.

Primer 5.

Ugrađeni tipovi poput numeričkih su instance klase Read. Stoga, sa read funkcijom možemo pročitati vrednost iz niske.

ghci> read "233"
*** Exception: Prelude.read: no parse

Razlog zašto smo dobili izuzetak je taj zato što interpreter ne kakva vrednost je zapisana u nici. Tip funkcije read je Read a => String -> a. Vidimo da je kodomen parametrizovan, što znači da tip izraza read "233" a priori može da bude bilo koji tip klase Read. Stoga je potrebno deklarisati tip izraza read "233":

ghci> read "233" :: Int
233
ghci> read "233" :: Float
233.0
ghci> read "-233" :: Double
-233

Mnogi drugi tipovi su takođe instance klase Read:

ghci> read "True" :: Bool
True
ghci> read "[1,2,3,4]" :: [Int]
[1,2,3,4]
ghci> read "(42,'a')" :: (Int, Char)
(42,'a')

Number i Fractional

Klasu Num čine svi tipovi koji predstavljaju nekakav skup brojeva (celih, racionalnih, realnih, kompleksnih...). Definicija klase Num je:

class Num a where
  (+) :: a -> a -> a
  (-) :: a -> a -> a
  (*) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a 

Ova klasa propisuje tri operatora +, - i * za koje je jasno šta predstavljaju. Funkcija negate negira vrednost (daje inverz u odnosu na sabiranje). Funkcija abs daje apsolutnu vrednost, dok signum daje znak. Funkcija fromInteger prevodi vrednost tipa Integer8 u vrednost instance.

Klasa Fractional je podklasa klase Num koja dozvoljava i deljenje vrednosti:

class Num a => Fractional a where
  (/) :: a -> a -> a
  recip :: a -> a
  fromRational :: Rational -> a
  { -# MINIMAL fromRational, (recip | (/)) #-}

Funkcija fromRational transormiše vrednost tipa Rational u vrednost instance. Do sada tip Rational nismo spominjali, ali u pitanju je tip koji se koristi za prezentovanje racionalnih brojeva u proizvoljnoj tačnosti.

Funkcija recip daje recipročnu vrednost broja9. Dovoljno je implementirati samo jednu od funkcija (/) i recip, jer su one u definiciji klase definisane jedna preko druge:

recip x = 1 / x
x / y   = x * recip y

Definicije klasa Num i Fractional približno odgovaraju definicijama prstena i polja.

Primer 6.

Uvedimo tip Racionalan u navedene klase. Imajući na umu zakone poput \[\frac{a}{b} \pm \frac{c}{d} = \frac{ad\pm cb}{cd} \qquad \frac{a}{b} \cdot \frac{c}{d} = \frac{ab}{cd} \qquad \left\lvert\frac{a}{b}\right\rvert=\frac{\lvert a\rvert}{\lvert b\rvert}\] kodiranje je veoma jednostavno:

instance Num Racionalan where
  (R (a, b)) + (R (c, d)) = R (a*d + c*b, c*d)
  (R (a, b)) - (R (c, d)) = R (a*d - c*b, c*d)
  (R (a, b)) * (R (c, d)) = R (a*d + c*b, c*d)
  negate (R (a, b)) = R (negate a, b)
  abs (R (a, b)) = R (abs a, abs b)
  signum (R (a, b)) = signum a * signum B
  fromInteger n = R (fromIntegral a, fromIntegral b)

instanciranje Fractional Racionalan je još jednostavnije, jer je dovoljno implementirati samo dve funkcije

instance Fractional Racionalan where
  recip (R (a, b)) = R (b, a)
  fromRational r = R (numerator r, denominator r) 
Funkcije numerator i denominator su funkcije kojima se može pristupiti brojiocu i imeniocu vrednosti tipa Rational.

Jasno je da tipovi poput Int, Integer, Float, Double i Rational pripadaju klasi Num. Od navedenih tipova, samo prva dva ne pripadaju klasi Fractional. Iako deluje da su samo ovakvi tipovi instance ovih klasa, Num i Fractional mogu sadržati još mnoge zanimljive primere što pokazuju naredni zadaci.

Zadatak 1. Definisati tip kompleksnih brojeva sa newtype Kompleksan = K (Int, Int). Instancirati Num Kompleksan i Fractional Kompleksan. Apsolutnu vrednost implementirati kao normu kompleksnog broja, a znak kompleksnog broja implementirati tako da važi abs z * signum z = z.

U narednim zadacima, funkcije abs i signum implementirati proizvoljno.

Zadatak 2. Definisati tip Z4 koji predstavlja skup ostataka pri deljenju sa \(4\) tj \[\mathbb Z_4 = \{0, 1, 2, 3\}.\] Ovaj tip definisati kao newtype Z4 = Z4 Int. Instacirati Num Z4 pri čemu voditi računa da se sve operacije vrše po modulu \(4.\) Na primer \(3 + 2 =_4 1\) i \(2 \cdot 2 =_4 0\).

Zadatak 3. Analogno prethodnom zadatku kreirati tip Z5 koji prezentuje \[\mathbb Z_5 = \{0, 1, 2, 3, 4\},\] i instancirati Num Z5. Kreirati (sa ili bez računara) tablicu množenja za u skupu \(\mathbb Z_5\) (naravno, u odnosu na množenje modulo \(5\)). Utvrditi da je množenje u \(\mathbb Z_5\) regularno tj. da je proizvod dva nenula elementa uvek različit od nule (iz prethodnog primera vidimo da to ne važi za \(\mathbb Z_4\)). Koristeći ovu činjenicu, definisati recipročnu vrednost svakog elementa iz \(\mathbb Z_5\) i instancirati Fractional Z5

Zadatak 4. Definisati tip za predstavljanje polinoma sa celobrojnim koeficijentima kao newtype Polinom = Polinom [Int]. Uvesti ovaj tip u klase Eq, Show i Num.