Tipske klase

Tipska klasa predstavlja kolekciju tipova koji imaju neke zajedničke osobine. Te zajedničke osobine izražavaju se kroz metode¹ koje "rade" sa svim tipovima te klase. Svaki tip koji pripada nekoj klasi naziva se instanca te klase.

U lekciji o polimorfizmu videli smo da nam tipske klase omogućuju da pišemo polimorfne funkcije koje koriste neke određene metode koje nisu dostupne svakom tipu². U ovoj lekciji ćemo prikazati kako i sami možemo definisati naše klase, i kroz primere predefinisanih klase videćemo razne tehnike koje je moguće koristiti pri radu sa klasama.

Klasa se definiše dekleracijom klase nakon koje sledi niz dekleracija tipova metoda koje instanca mora da implementira:

class C a where
  f1 :: T1
  f2 :: T2 
  ....

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

instance C T where
  f1 = ...
  f2 = ... 
  ...

Jedan primer

Gotovo da nema uvodne knjige o programiranju u nekom jeziku koja ne sadrži primer sa geometrijskim 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 posluž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

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 

Navedeni kôd 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 figuru³.

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

class Figura a where
  obim :: a -> Double

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

Slobodna tipska promenljiva a u liniji class Figura a where predstavlja proizvoljnu 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, te je potrebno tipove Pravougaonik, Trougao i Krug učiniti instancama klase Figura.

Pošto klasa Figura pripisuje samo jednu funkciju (obim), instanciranje 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

Linijom instance ... započinje se blok definicija metoda. 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 metode koje klasa deklariše⁵. U bloku definicija ne navode se dekleracije tipova!

Nakon učitavanja navedenih definicija u GHCi, možemo se uveriti da se obim može primeniti 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 površina koja nam daje površinu figure. Sada u svakoj instanci moramo implementirati i funkciju površina. Površinu Pravougaonika i kruga ćemo lako izračunati, a za površinu trougla ćemo iskoristiti Heronovu formulu. Kompletan kôd sada izgleda ovako:

class Figura a where
  obim :: a -> Double
  površina :: a -> Double


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

  površina (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
  
  površina (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
  
  površina (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.

newtype Racionalan = R (Int, Int)

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

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

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 instanci⁶.

Konkretno, puna definicija klase Eq je⁷:

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 definicijama⁸, svaka instanca Eq klase mora sadržati barem jednu od definicija funkcija == i /=.

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

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 >=⁹. Prema tome, klasa Ord je podklasa klase Eq.

Klasa Ord propisuje funkciju compare :: a -> a -> Ordering koja upoređuje dve vrednosti, uobičajene 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.

instance Ord Racionalan where
  compare (R (a, b)) (R (c, d)) = compare (a * d) (c * 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

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.

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

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

instance Show Racionalan where
  show (R (x, y)) = show x ++ "/" ++ show y

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.

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

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

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 Integer¹⁰ 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 transformiš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 broja¹¹. 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.

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)

instance Fractional Racionalan where
  recip (R (a, b)) = R (b, a)
  fromRational r = R (numerator r, denominator r) 

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 (Double, Double). 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. Instancirati 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 definisati 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.