Polimorfnost

Svaki programski jezik je osmišljen sa ciljem da olakša proces programiranja računara, koliko god ovoj iskaz delovao očigledno. Zaista, iako se svaki program može napisati u mašinskom jeziku, programeri biraju programske jezike zbog osobina tih jezika koje omogućuju efikasnije programiranje. Osobine koje olakšavaju programiranja su zapravo apstrakcije kojima se nebitne pojedinosti skrivaju i samim tim obezbeđuje lakše izražavanje suštinski ideja o programu¹.

Jednoj vrsti apstrakcija posvetićemo ovu lekciju, a na samom početku ćemo pokušati da motivišemo razloge za uvođenje takvih apstrakcija.

U prethodnim lekcijama naučili smo kako da definišemo funkcije, i upoznali smo se sa pojmom tipa funkcije. Programi koje smo pisali su bili mali i sačinjeni samo do nekoliko definicija funkcija. Ako bismo radili na velikim programima (kao što su web serveri, desktop aplikacije, itd...) uvideli bismo jedan jednostavan ali naporan problem. Naime, često bismo pisali gotovo iste funkcije koje imaju malo različite tipove.

f :: Int -> Int
f x = x*x + x

f :: Float -> Float
f x = x*x + x

Prethodni primer je trivijalan, ali demonstrira probleme koji se sreću na iole većim projektima bez obzira na programski jezik. Srećom, mnogi jezici su našli rešenja za navedene probleme, pa tako i Haskel. U Haskelu, moguće je definisati vrednosti (posebno, funkcije) za koje deluje da ne pripadaju jednom određenom tipu, već čitavoj kolekciji tipova. Ovakvi tipovi se nazivaju polimorfni tipovi².

Polimorfnost se u Haskelu obezbeđuje na dva načina: kroz parametarski polimorfizam i kroz ad-hoc polimorfizam.

Parametarski polimorfizam

Tipska promenljiva (ili još tipski parametar), je ime koje predstavlja proizvoljan tip (eventualno iz neke kolekcije tipova). Za razliku od tipova, tipske promenljive zapisuju se sa početnim malim slovom, a najčešće se ime tipske promenljive sastoji samo od jednog slova. Ako tipska promenljiva predstavlja svaki mogući tip (a ne neku specifičnu kolekciju tipova), tada za tu tipsku promenljivu kažemo da je slobodna. Kasnije ćemo objasniti promenljive koje nisu slobodne.

Parametarski polimorfni tipovi su oni tipovi koji sadrže slobodne tipske promenljive.

Najjednostavniji primer vrednosti koja poseduje parametarski polimorfan tip, je konstantna funkcija poput naredne:

konstantnoTačno :: a -> Bool
konstantnoTačno = \x -> True

Navedenom definicijom, kao³ da je definisano beskonačno mnogo funkcija sa različitim domenima: za svaki tip T po jedna funkcija tipa T -> Bool. Sve te funkcije nazivamo istim imenom konstantnoTačno. Kada u Haskel programu primenimo funkciju konstantnoTačno na neku određenu vrednost, tada tipska promenljiva a u tipu funkcije preuzima tip vrednosti na koju primenjujemo funkciju. Na primer, ako napisemo konstantnoTačno 'a' tada možemo smatrati da ime konstantnoTačno u navedenom izrazu predstavlja funkciju tipa Char -> Bool (jer je samo funkciju tog tipa moguće primeniti na vrednost tipa Char).

Nesto složeniji primer funkcije sa polimorfnim tipom je identička funkcija, definisana u Prelidu kao id:

id :: a -> a
id = \x -> x

Tip identičke funkcije sadrži tipsku promenljivu i u domenu i u kodomenu. Kad god se u tipu na više mesta mesta pojavljuje promenljiva sa istim imenom, tada sva pojavljivanja te promenljive određuju isti tip. Stoga, funkcija id predstavlja funkciju tipa Int -> Int ili funkciju tipa [Char] -> [Char] i tako dalje, ali ne može predstavljati funkciju tipa Bool -> Float. Sam tip a -> a ukazuje na to da domen i kodomen funkcije moraju biti isti tipovi, prema tome id True ili id False mogu predstavljati samo vrednosti tipa Bool.

Prethodno navedene funkcije su bile trivijalne. Ipak, polimorfne funkcije su izuzetno korisne, i mi smo ih zapravo već koristili.

Funkciju head (koja vraća prvi element prosleđene liste), ima smisla primenjivati na liste tipa [Int], [Char], [Bool] itd... Prema tome, umesto da se za svaki tip liste definise posebna funkcija, definisana je jedinstvena funkcija head sa polimorfnim tipom [a] -> a:

head :: [a] -> a
head (x:_) = x

U ovoj funkciji, vidimo da se tipska promenljiva pojavljuje unutar zagrada []. Prema tome [a] ne predstavlja svaki tip, vec predstavlja svaki tip lista. Npr. tip Int nije oblika [a], i stoga head 3 nije dobro tipiziran izraz. Sa druge strane, ako head primenimo na [True, True, False] tada Haskel "poklapa" domen [a] sa tipom [Bool], odakle sledi da a mora biti Bool. Prema tome, head [True, True, False] je vrednost tipa Bool.

I ostale funkcije koje smo do sada koristili za rad sa listama (poput tail, init, last, null) imaju polimorfne tipove. Samim tim te funkcije se mogu koristiti za listom bilo kog tipa.

Nije nužno da vrednost polimorfnog tipa bude funkcija.

Iz prethodnih redova vidimo da polimorfne vrednosti poprimaju različiti tip u zavisnosti od izraza u kojima se nalaze (otuda i naziv poli-morfne).

Ponekad nije dovoljno da tip poseduje samo jednu promenljivu. Ako se u tipu nalaze dve ili vise razlicitih promenljiva, tada su te promenljive nezavisne.

fst3 :: (a, b, c) -> a
fst3 (x, _, _) = x

Zadatak 4. Implementirati funkciju zameni :: (a, b) -> (b, a) koja menja mesta koordinatama uređenog para.

Zadatak 5. Implementirati funkciju razmeni :: (a, b) -> (c, d) -> ((a, d), (c, b)) koja razmenjuje koordinate dva uređena para.

Iz prethodnih primera , vidimo da su tipovi sa slobodnim tipskim promenljivama izuzetno korisni. Mnoge funkcije iz prelida koje smo već koristili su parametarski polimorfne. Ipak, tehnika parametarskog polimorfizma i dalje ne rešava konkretan problem koji smo opisali na početku lekcije. Tada smo hteli da implementiramo funkciju koja bi prihvatala razne numeričke tipove. Tu funkciju ne možemo definisati sa sledećim kodom, koliko god to bilo privlačno:

f :: a -> a
f x = 253 * x + 17

Prethodna definicija nije dobra, iz prostog razloga zato što tipska promenljiva a može predstaviti svaki tip. Za tipove poput Char ili Bool, navedena definicija nema smisla jer se vrednosti tog tipa ne mogu sabirati niti množiti brojevima. Stoga bi bilo korisno kada bismo ograničili tipsku promenljivu a samo na one tipove koji dozvoljavaju sabiranje i množenje. Upravo ćemo to prikazati u nastavku.

Ad-hoc polimorfizam

Slobodne tipske promenljive mogu predstavljati bilo koji tip. Ponekad je poželjno ograničiti tipsku promenljivu na neku specifičnu kolekciju tipova. Upravo takva ograničenja se izražavaju kroz klase tipova.

Tipska klasa (ili skraćeno klasa⁶) je kolekcija tipova koji dozvoljavaju pozivanje određenih funkcija nad tipovima te klase. Često te funkcije nazivamo metode klase. Ime konkretne klase uvek počinje velikim slovom. Za svaki tip koji pripada nekoj klasi kažemo da je instanca te klase.

ghci> show True
"True"  
ghci> show 2
"2"

Za razliku od vrednosti koja pripada samo jednom tipu, tipovi se mogu istovremeno nalaziti u više⁷ klasa (ili nijednoj). Činjenicu da neki tip T pripada klasi C, označavamo sa C T.

Korišćenjem klasa, moguće je ograničiti tipsku promenljivu na neku određenu klasu. Klasno ograničenje kojim se tipska promenljiva a ograničava na tipove klase C se zapisuje kao C a. Ovakva ograničenja se razdvajaju od samog tipa sa strelicom =>. U slučaju da postoji vise ograničenja, tada se ta ograničenja navode u obliku uređene \(n\)-torke.

Klase su korisne jer omogućavaju korišćenje funkcija sa istim imenom nad različitim tipovima što značajno pojednostavljuje programiranje.

U Haskel programima često se koriste naredne klase:

1. Klasa Show je klasa svih tipova čije vrednosti mogu da se reprezentuju kao niska. Nad vrednostima instance klase Show dozvoljeno je pozivati funkciju show koja vrednost pretvara u nisku.
2. Klasa Eq je klasa svih tipova čije vrednosti se mogu porediti sa operatorima == i /=.
3. Klasa Ord je klasa svih tipova čije vrednosti se mogu porediti pomoću operatora <, <=, > i >=.
4. Klasa Num je klasa svih tipova čije vrednosti se mogu sračunavati sa operatorima +, -, *.
5. Klasa Fractional je podklasa klase Num koja sadrži tipove nad kojima se može pozivati operacija /.

Tipovi poput Bool, Int, Integer, Float, Double, Char pripadaju klasama Eq, Ord i Show. To znači da vrednosti ovih tipova možemo da poredimo sa ==, /=, <, <=, >, >= kao i da pretvaramo u niske sa funkcijom show.

Tipovi Int, Integer, Float, Double svi pripadaju klasi Num. Vrednosti ovog tipa možemo da sabiramo, oduzimamo, i množimo sa operatorima +, -, *. Tipovi Float i Double pripadaju klasi Fractional⁸.

f :: Num a => a -> a
f x = x*x + x

x1 :: Int
x1 = 5

x2 :: Integer
x4 = 5

x3 :: Float
x3 = 5

x4 :: Double
x4 = 5

ghci> f x1
30
ghci> f x2
30
ghci> f x3
30
ghci> f x4
30

Iz primera vidimo da klase zaista omogućavaju polimorfizam: vrednost f kao da istovremeno poseduje različite tipove Int -> Int, Integer -> Integer, Float -> Float i Double -> Double.

Važno je imati na umu da metode neke određene klase su različite funkcije (što možda nije očigledno u prethodnom primeru). Na primer, operacija + u smislu tipa Int nije isto što i operacija + u smislu tipa Integer iako na prvi pogled ne deluje tako.

y1 :: Int
y1 = 12345678987654321

y2 :: Integer
y4 = 12345678987654321

y3 :: Float
y3 = 12345678987654321

y4 :: Double
y4 = 12345678987654321

ghci> f y1
-1878358338631772398
ghci> f y2
152415789666209432556012777625362
ghci> f y3
1.5241581e32
ghci> f y4
1.5241578966620942e32

Ako smo u pretposlednjem primeru demonstrirali kako klase omogućuju polimorfizam, u poslednjem primeru smo uvideli zašto se taj polimorfizam naziva ad hoc: konkretna implementacija metoda razlikuje se od klase do klase!

Naravno, i dalje nismo razjasnili mnoge stvari oko klasa, kao na primer kako se klase definišu ili kako se tipovi uvode u klase. Više o tipskim klasama, njihovom definisanju i instanciranju, biće rečeno u lekciji Tipske klase. Za sada je bitno samo da razumemo tipske potpise koji sadrže klasna ograničenja.

Klase i složeni tipovi

Videli smo u lekciji o tipovima, da je od postojećih tipova moguće dobiti nove tipove lista i proizvode (npr. od Int dobijamo [Int]). Deluje prirodno da se neke osobine tipova prenose pri ovom procesu. Tačnije, ako tip T pripada nekoj klasi C, tada je nekad smisleno da i [T] ili (T,T) pripadaju istoj to klasi. Srećom, ovakva "nasleđivanja" su moguća i prisutna u Haskelu.

Ako neki tip A pripada klasi Eq, tada i tip [A] pripada klasi Eq. To praktično znači da ako se vrednosti nekog tipa mogu porediti sa operatorima == i /=, tada se i liste tog tipa mogu porediti sa istim operatorima. Poređenja lista se vrše član po član. Analogno važi i za klase Ord i Show: ako tip A pripada nekoj od ovih klasa, tada i [A] pripada istoj klasi. Prema tome, tipovi poput [Bool], [Int], [Char] ali i [[Bool]], [[[Int]]] itd... pripadaju klasama Eq, Ord i Show.

ghci> show [1,2,3]
"[1,2,3]"
ghci> show [[1,2],[3,4],[5,6]]
"[[1,2],[3,4],[5,6]]"

Za uređene \(n\)-torke važi sličan princip. Ako tipovi A, B, ... T pripadaju klasi Eq, tada i tip (A, B,..., T) pripada klasi Eq. Ovo takođe važi i za klase Ord i Show.

ghci> 8 == 2 * (3 + 1)
True
ghci> 'a' == 'b'
False

ghci> (2, 'a') == (3, 'b')
False
ghci> (2, 'a') == (2, 'a')
True

ghci> (2, 'a') < (3, 'b')
True
ghci> (100, 'W') < (100, 'A')
False

ghci> [(2,'a')] == [(3,'b'), (2,'a')]
False

max3 :: Ord a => a -> a -> a -> a
max3 x y z = max (max x y) z

Zaključivanje tipova

GHC kompajler (skoro) uvek može da zaključi tip izraza. Zbog toga često nije neophodno navoditi tipske dekleracije u izvornim datotekama.⁹

Zaključivanje tipova nam takođe omogućava da u GHCi okruženju proverimo tipove izraza. To možemo uraditi pomoću naredbe :type nakon koje navodimo izraz čiji tip nas interesuje:

ghci> :type [True, False]
[True, False] :: [Bool]
ghci> :type [True, False] !! 1
[True, False] !! 1 :: Bool
ghci> :type length [True, False]
length [True, False] :: Int
ghci> :type (True, 'a')
(Bool, Char) 

Zaključivanje tipova je složen proces, ali možemo demonstrirati osnove ovog procesa.

1. Pri zaključivanju tipa izraza [True, False], kompajler prvo uviđa da se radi o listi. Prema tome, prvo se zaključuje da je tip ovog izraza [a] za neki neodređeni tip a. Zatim, kompajler uvidom u prvi element ove liste zaključuje da je tip a baš Bool, pa je samim tim tip celog izraza [Bool]. Naravno pri ovom procesu se proverava da svi ostali elementi liste imaju isti tip.
2. Operacijom !! se pristupa \(n\)-tom elementu liste. Kako lista u izrazu [True, False] !! 1 ima tip [Bool] sledi da izraz [True, False] !! 1 ima tip Bool.
3. Izraz length [True, False] je nešto složeniji. Funkcija length poseduje polimorfan tip [a] -> Int. U ovom slučaju jasno je da će povratna vrednost funkcije imati tip Int. Ali svakako, pri proveri dobre tipiziranosti celog izraza kompajler prvo mora da utvrdi da argument poseduje tip koji se može poklopiti sa [a].

Rezultat :type naredbe će nas iznenaditi u slučaju numeričkih literala:

ghci> :type 2
2 :: Num a => a

Za izraz 2 GHCi nije mogao da zaključi konkretan tip. Literal 2 može predstavljati vrednost tipa različitih numeričkih tipova. Zbog toga GHCi zaključuje da je 2 nekog tipa a koji pripada klasi Num, sto se naravno označava sa Num a => a.

Ako potražimo tip izraza 3.14 uvidećemo da je u pitanju tip Frac a => a. Svakako izraz 3.14 predstavlja jedan racionalan broj, te ne može biti tipa Int ili Integer. Ali racionalan broj može biti predstavljen i kao Float i kao Double vrednost. Zbog toga ni ovde nemamo konkretan odgovor već klasno ograničenje.

Karijevanje

U lekciji o funkcijama prikazana su dva načina definisanja funkcije sa više parametara. Prvi, i jednostavniji, način podrazumeva konstrukciju funkcije koja uzima uređen par, dok drugi način podrazumeva konstrukciju funkcije višeg reda. Prva tehnika daje funkciju tipa (A, B) -> C dok druga tehnika daje funkciju tipa A -> (B -> C).

Intuitivno je jasno da su ove dve tehnike podjednako dobre. Svaka funkcija koja se može definisati na jedan od pomenutih načina može se definisati i na drugi. Stvar je ukusa za koju tehniku ćemo se opredeliti¹⁰. Ono što je zanimljivo je da je Haskel toliko ekspresivan jezik da se lako može definisati funkcija višeg reda koja transformiše funkciju tipa (A, B) -> C u funkciju tipa A -> (B -> C) (gde su A, B i C neki tipovi). Ovakva transformacija se naziva karijevanje¹¹. Označimo funkciju koja vrši ovu transformaciju sa k.

Kog tipa je funkcija k? Funkcija k uzima funkciju tipa (A, B) -> C i vraća funkciju tipa A -> (B -> C). Stoga je tip ove funkcije ((A, B) -> C) -> (A -> (B -> C)).

Kada smo utvrdili tip, možemo da implementiramo k. Pretpostavimo da je f :: (A, B) -> C funkcija koju želimo da transformišemo. Pošto primena k f predstavlja vrednost tipa A -> (B -> C), podudaranjem oblika možemo definisati da k f predstavlja neki lambda izraz \x y -> .... U telu ovog lambda izraza mora se nalaziti rezultat primene f na uređen par (x, y). Prema tome, k možemo da definišemo sa narednim kodom

k :: ((A, B) -> C) -> (A -> (B -> C))
k f = \x y -> f (x, y)

U definiciji funkcije k nigde nismo koristili činjenicu da radimo sa vrednostima tipova A, B ili C, tj nismo iskoristili osobine ovih tipova. Prema tome, funkciju k možemo učiniti u potpunosti parametarski polimorfnom:

k :: ((a, b) -> c) -> (a -> (b -> c))
k f = \x y -> f (x, y)

Na sličan način možemo da definišemo i inverznu funkciju k' koja funkcije tipa a -> (b -> c) transformiše u funkcije tipa (a, b) -> c. Jasno, tip funkcije k' je (a -> (b -> c)) -> ((a, b) -> c). Ako je g funkcija tipa a -> (b -> c) tada je k' g funkcija koja uzima uređen par, te ćemo stoga takvu funkciju konstruisati sa lambda apstrakcijom \(x, y) -> .... U telu lambda funkcije je potrebno da se nađe vrednost (g x) y. Stoga, k' možemo da definišemo sa narednim kodom

k' :: (a -> (b -> c)) -> ((a, b) -> c)
k' g = \(x, y) -> g x y

Uverimo se da navedene funkcije zaista dobro rade. Uzmimo primer is lekcije o funkcijama:

ljubav :: (String, String) -> String
ljubav (x, y) = x ++ " voli " ++ y ++ "!"

ghci> ljubav' = k ljubav
ghci> ljubav' "Ana" "Milovana"
"Ana voli Milovana!" 

Sa druge strane, od ugrađene funkcije mod možemo dobiti našu verziju funkcije koja uzima jedan uređen par brojeva:

ghci> mod' = k' mod
ghci> mod' (7, 2)
1

Funkcije koje smo konstruisali u prethodnim redovima dostupne su pod imenima curry i uncury i poseduju sleće tipove

curry :: ((a, b) -> c) -> (a -> (b -> c))
uncurry :: (a -> b -> c) -> ((a, b) -> c)

Zadatak 8. Konstruisati funkciju curry3 koja uzima funkciju tipa (a, b, c) -> d i daje funkciju tipa a -> (b -> (c -> d)).

Zadatak 9. Konstruisati funkciju curry2x2 koja uzima funkciju tipa (a, b) -> (c, d) -> e i daje funkciju tipa a -> (b -> (c -> (d -> e))).

Zadatak 10. Kog tipa je izraz uncurry curry?