Operatori

Iako možda nismo ni svesni, funkcije koristimo još od najranijih dana matematičkog obrazovanja. Operacije sabiranja, oduzimanja, množenja i deljenja su zapravo funkcije od dve promenljive. Tako na primer, operacija sabiranja koju označavamo simbolom $+$ je funkcija koja svakom paru brojeva pridružuje njihov zbir. Za razliku od većine ostalih funkcija od dve promenljive, primena funkcije $+$ na vrednosti $x$ i $y$, ne označava se sa $+(x, y)$, već sa $x+y$. Glavni razlog je naravno istorijski: simbol $+$ je ušao u upotrebnu pre nego što se pojam funkcije pojavio. Ali postoji i praktičan razlog: zapis $x+y$ je jednostavniji (pa samim tim i čitljiviji) od zapisa $+(x, y)$. Slično važi i za simbole $-$, $\times$, $\colon$ koji takođe predstavljaju funkcije dve promenljive.

Notaciju pri kojoj ime funkcije navodimo između argumenata funkcije, nazivamo infiksna notacija. Za razliku od toga, notaciju u kojoj se ime funkcije navodi pre argumenta, naziva se prefiksna notacija¹. Do sada, sve funkcije koje smo definisali u Haskelu smo koristili isključivo u prefiksnoj notaciji (npr. f x y).

Pojam funkcije je fundamentalan u Haskel jeziku. Zbog toga je Haskel jezik dizajniran tako da omogući programerima da sami definišu funkcije koje će moći da se koriste u infiksnoj notaciji. Ovakve funkcije nazivamo operatori.

Osnovni operatori

Do sada smo već imali prilike da koristimo neke operatore. To su bili

Aritmetički operatori +, -, *, /, ^
Logički operatori &&, ||
Operatori poređenja ==, /=, <, <=, >, >=
Nizovni operatori :, ++, !!

Koristeći :type naredbu u GHCi okruženju, možemo se uveriti da su i navedeni operatori funkcije. Na primer, tip operatora && nam govori da se radi o binarnoj funkciji

ghci> :type (&&)
(&&) :: Bool -> Bool -> Bool

Da bi smo iskoristili naredbu :type sa operatorom (kao u gornjem primeru), neophodno je da ime tog operatora postavimo u zagrade.

Zapravo, postavljanjem imena proizvoljnog operatora u zagrade dobijamo prefiksnu funkciju:

ghci> (&&) True False
False
ghci> (+) 4 3
7
ghic> (-) 5 2
3

Iz poslednjeg primera vidimo da je "prvi" argument operatora u prefiksnoj notaciji zapravo levi argument, a "drugi" argument pri prefiksnoj notaciji je desni argument u infiksnoj notaciji.

Zadatak 1. Bez korišćenja type naredbe, odrediti tipove operatora nadovezivanja i spajanja lista : i ++.

Operator ++ poseduje tip [a] -> [a] -> [a] jer ovaj operator spaja dve liste istog tipa. Operator : poseduje tip a -> [a] -> a jer ovaj operator dodaje element (levi argument) na početak liste (desni argument).

Zadatak 2. Kog je tipa operator ==?

Operator poređenja poredi dve vrednosti istog tipa i vraća logičku vrednost kao rezultat tog poređenja. Da bi se dve vrednosti nekog tipa mogle porediti, neophodno je da taj tip pripada klasi Eq. Prema tome, operator == ima tip Eq a => a -> a -> Bool.

Prioritet i asocijativnost

Korišćenjem operatora dobijamo nove vrednosti na koje ponovo možemo delovati s operatorima. Na primer, rezultat zbira $1+2$ možemo pomnožiti sa $5$, a izraz koji odgovara ovom postupku je $(1 + 2) \cdot 5$. U datom izrazu, kao i uvek, zagrade označavaju podizraz kog je potrebno prvog izračunati.

Zagrade su neophodne da bi se tačno preneo smisao izraza. Ako bismo iz prethodnog primera obrisali zagrade, dobili bismo izraz $1 + 2 \cdot 5$. U zavisnosti od toga kojim redom vršimo računske operacije, od ovog izraza možemo da dobijemo vrednost $11$ ili $15$. Naravno ovde grešku nećemo napraviti jer znamo za konvenciju o prioritetu računskih operacija koja govori da je množenje potrebno izvršiti pre sabiranja kada zagradama drugačije nije naznačeno. Pomenutom konvencijom je ustanovljen prioritet operatora. Za operator $\cdot$ kažemo da ima veći (ili viši) prioritet od operatora $+$, odnosno za $+$ kažemo da ima manji (ili niži) prioritet od operatora $\cdot$.

Dakle, uspostavljenjem prioriteta operatora, možemo se osloboditi nekih parova zagrada bez brige da ćemo izgubiti namereno značenje izraza. Na primer, iz izraza $1 + (2 \cdot 5)$ možemo obrisati zagrade, ali ne i iz izraza $(1 + 2) \cdot 5$ jer bismo time dobili sasvim drugi izraz.

Šta se dešava kada koristimo operatore istog prioriteta? Štaviše, šta se dešava kada koristimo samo jedan operator? Da li možemo iz izraza $(2 + 4) + 6$ obrisati zagrade? U navedenom primeru možemo, jer izrazi $(2 + 4) + 6$ i $2 + (4 + 6)$ daju potpuno isti rezultat.

Za neki operator $\star$ kažemo da je asocijativan ako važi \[(a \star b)\star c = a \star (b\star c)\] za sve vrednosti $a,b,c$ na koje operator može da deluje.

Primer 1.

Operator sabiranja $+$ je asocijativan operator, a takav je i operator množenja $\cdot$.

Primer 2.

Nije svaki operator asocijativan. Operator deljenja $/$ nije, jer izraz $1 / (2 / 3)$ ima drugačiju vrednost od izraza $(1 / 2) / 3$. Prema tome, izraz $1 / 2 / 3$ je potrebno pažljivo interpretirati².

Korišćenjem osobine asocijativnosti i konvencije o prioritetu možemo se osloboditi zagrada u izrazima. Zbog toga su autori Haskel jezika omogućili izražavanje ove dve osobine u jeziku.

U Haskelu, svaki operator ima prioritet koji je označen sa jednim prirodnim brojem. Operatori sa najnižim prioritetom imaju prioritet $0$, a oni sa najvišim imaju prioritet $9$. Prioritet $10$ je rezervisan za aplikaciju funkcija na vrednost.

Primer 3.

Operator ++ koji nadovezuje liste je asocijativan operator jer očigledno važi xs ++ (ys ++ zs) = xs ++ (ys ++ zs) za sve liste xs, ys, zs. Prema tome, uvek kada nadovezujemo više lista, možemo pisati izraz poput xs ++ ys ++ zs jer je sve jedno kako se taj izraz interpretira.

Primer 4.

Operator : koji nadovezuje element na početak liste nije asocijativan. Zaista iz izraza (x:xs):ys možemo zaključiti da ako je x :: T tada mora biti xs :: [T] a samim tim i ys :: [[T]] (jer xs :: [T] nadovezujemo na početak ys). Sa druge strane, ako u izrazu x:(xs:ys) važi x :: T, tada mora biti (xs:ys) :: [T], a samim tim i xs :: T i ys :: [T].

Dakle, (x:xs):ys i x:(xs:ys) predstavljaju potpuno različite izraze (štaviše ako je jedan dobro tipiziran, tada onaj drugi nije).

Definisanje operatora

Operatori se definišu slično ostalim funkcijama. Pri biranju imena operatora, potrebno ispoštovati tri pravila:

Ime operatora mora se sastojati samo od znakova !#$%&*+./<=>?@\^|-~:
Ime operatora ne sme biti: .., :, ::, =, \, |, <-, ->, @, ~, =>.
Ime operatora ne sme počinjati sa :.

Operatori se mogu definisati na više načina, kako i pokazuje naredni primer.

Primer 5.

Definišimo operator isključujuće disjunkcije, odnosno operator tipa Bool -> Bool -> Bool koji vraća True samo ako argumenti imaju različitu logičku vrednost. Za ime ovog operatora možemo uzeti na primer |-|.

Ako definišemo operator dodelom lambda izraza, možemo prosto pisati:

(|-|) :: Bool -> Bool -> Bool
(|-|) = \x y -> x /= y

Zagrade () nisu deo imena operatora, već služe za predstavljanje operatora u prefiksnom obliku.

Moguće je takođe i iskoristiti podudaranje oblika:

(|-|) :: Bool -> Bool -> Bool
(|-|) x y = x /= y

Prvo argument x predstavlja levi argument, a drugi argument y predstavlja desni argument.

Podudaranje oblika dozvoljava i narednu definiciju:

(|-|) :: Bool -> Bool -> Bool
x |-| y = x /= y

Sve tri navedene definicije su u potpunosti iste. Poslednji oblik definicije je najprirodniji pa se i najčešće koristi.

Učitavanjem bilo koje od definicija u GHCi možemo koristiti novi logički operator:

ghci> True |-| False
True
ghci> True |-| True
False

Zadatak 3. Definisati operator logičke implikacije (==>) :: Bool -> Bool -> Bool. Implikacija $p\Rightarrow q$ je netačna ako i samo ako je p tačno a q netačno.

Moguće je deklarisati prioritet i asocijativnost operatora takozvanom infix dekleracijom. Ova dekleracija se sastoji od jedne od ključnih reči infixl, infixr ili infix, i prirodnog broja manjeg od 9 koji označava prioritet operatora. Reč infixl označava da se radi o levoasocijativnom operatoru, infixr označava da se radi o desnoasocijativnom operatoru, dok infix označava da operator nije ni jedno ni drugo.

Ako prioritet i asocijativnost operatora nisu deklarisani, tada će se podrazumevati vrednost infixl 9.

Primer 6.

Operator nadovezivanja elementa na kraj niza možemo definisati sa

(@:) :: a -> [a] -> [a]
x @: xs = xs ++ [x]

Obratite pažnju da je operator definisan tako da levi argument nadovezuje na kraj desnog argumenta! Operator je ovako definisan radi primera.

ghci> '!' @: "Hello"
"Hello!"

Za gore definisan operator @: se podrazumeva da je levoasocijativan sa prioritetom 9. Zbog leve asocijativnosti, izraz x @: y @: z se tumači kao (x @: y) @: z što nam ne odgovara:

ghci> '?' @: '!' @: "Hello"

<interactive>:2:12: error:
    • Couldn't match expected type ‘[String]’ with actual type ‘Char’
    • In the second argument of ‘(@:)’, namely ‘'!'’
      In the first argument of ‘(@:)’, namely ‘"Hello" @: '!'’
      In the expression: "Hello" @: '!' @: '!'

<interactive>:2:19: error:
    • Couldn't match expected type ‘[[String]]’ with actual type ‘Char’
    • In the second argument of ‘(@:)’, namely ‘'!'’
      In the expression: "Hello" @: '!' @: '!'
      In an equation for ‘it’: it = "Hello" @: '!' @: '!'

Izraz x @: y @: z, tj (x @: y) @: z, zahteva da x bude tipa T, y tipa [T] a z tipa [[T]]. Zbog toga, @: nije pogodan za nadovezivanje više elemenata na kraj liste³ jer moramo pisati zagrade kad povezujemo više elemenata na kraj liste:

ghci> '?' @: ('!' @: "Hello")
"Hello!?"

Ipak, možemo deklarisati @: kao desnoasocijativan operator navođenjem linije:

infixr 9 @:

Ovu dekleraciju je moguće postaviti bilo gde u kodu.

Ako ponovo učitamo kod u GHCi-u, prethodni primer će bez problema funkcionisati:

ghci> '?' @: '!' @: "Hello"
"Hello!?"

Sada se izraz interpretira kao '?' @: ('!' @: "Hello"), što smo i zeleli.

Nijedna dekleracija asocijativnosti i prioriteta nije pogrešna. Ipak, pažljivom upotrebom infix dekleracija možemo se osloboditi mnogih zagrada u kodu.

Ako je fiksnost operatora deklarisana sa infix, tada je uvek neophodno koristiti zagrade kada se izraz sastoji od više primena operatora.

Primer 7.

Da smo fiksnost operatora iz prethodnog primera definisali sa npr. infix 8 tada bismo dobili narednu grešku u GHCi-u:

ghci> '?' @: '!' @: "Hello"
<interactive>:1:1: error:
    Precedence parsing error
        cannot mix ‘@:’ [infix 8] and ‘@:’ [infix 8] in the same infix expression

Ova greška nam sugeriše da je neophodno da postavimo zagrade na odgovarajuće mesto. Primetimo da je u ovom slučaju samo jedan poredak zagrada validan (iz razloga koji su opisani ranije).

Operator poređenja vrednosti == je primer infix operatora. Primetimo da izraz⁴ True == False == True izgleda kao validan, ali će zapravo dovesti do greške.

4. Ili bilo koji drugi izraz sačinjen od logičkih vrednosti i operatora ==.

Zadatak 4. Definisati operator !+ :: (Float, Float) -> (Float, Float) -> (Float, Float) koji sabira vektore (odnosno sabira odgovarajuće koordinate uređenog para).

Funkcije kao operatori

U Haskelu je moguće ad-hoc napraviti operator od funkcije. Potrebno je samo postaviti ime te funkcije između kosih navodnika ``. Navedeno ime se tada može koristiti kao operator, pri čemu se prvi argument postavlja sa leve strane, a drugi argument sa desne strane.

Primer 8.

Funkcija elem :: Eq a => a -> [a] -> Bool proverava da li se vrednost nalazi u listi. Ova funkcija se često koristi u infiksnom obliku, pa se umesto elem x xs piše x `elem` xs:

ghci> 2 `elem` [1,2,3]
True
ghci> 'm' `elem` "Beograd"
False

Primetimo da izraz x `elem` xs podseća na matematičku notaciju $x \in XS$.

Podsetimo se da smo gore opisali da je moguće uraditi i obrnuto, od operatora dobiti prefiksnu funkciju, postavljanjem imena tog operatora u zagrade.

Sekcije

I operatore kao i 'obične funkcije', možemo parcijalno aplicirati na vrednosti. Ovakve parcijalne aplikacije nazivamo sekcije. Sekcija se zapisuje navođenjem operatora unutar zagrada zajedno sa još jednim od argumenata, i predstavlja prefiksnu funkciju.

Primer 9.

Sa sekcijama možemo da apliciramo jedan operand, levi ili desni, na operator /:

Sekcija (/ 2) predstavlja funkciju \x -> x / 2.
Sekcija (2 /) predstavlja funkciju \x -> 2 / x.

Kao što smo naveli, sekcije su prefiksne funkcije. Tako da nedostajući argument navodimo nakon sekcije, bez obzira da li je to levi ili desni operand:

ghci> (/ 2) 10
5.0
ghci> (2 /) 10
0.2

Primer 10.

Sekcije su posebno zgodne pri radu sa funkcijama višeg reda. Ako želimo da svaki element liste xs dupliramo, možemo da napišemo map (* 2) xs umesto dosadašnjeg map (\x -> x * 2) xs.

Neki važni operatori

Osim aritmetičkih, logičkih i operatora nad listama, Haskel programi sadrže obilje drugih operatora (od kojih mnogi nisu ni prisutni u drugim jezicima). Haskel programeri vole da koriste razne operatore jer time skraćuju programe. Neke od tih operatora ćemo predstaviti u nastavku ove glave, dok ćemo ostale obraditi u narednim lekcijama.

Operator kompozicije

Kompozicija funkcija f :: a -> b i g :: b -> c jeste funkcija h :: a -> c za koju važi (g (f x)) = h x za svako x :: a. Drugim rečima, kompozicija funkcija f i g je funkcija čija vrednost za argument x se dobija primenom funkcije g na vrednost f x.

Kompozicija funkcija je operacija koja se često koristi u matematici. U matematičkoj notaciji, kompozicija funkcija $f$ i $g$ se označava se $g\circ f$. Primetimo da se levo od operatora $\circ$ navodi funkcija koja se primenjuje druga.

Primer 11.

Neka su date funkcije $f(x)=2x$ i $g(x)=x^2$. Tada je funkcija $g\circ f$ data sa \[(g\circ f)(x) = g(f(x))=g(2x)=4x^2.\] Sa druge strane, funkcija $f\circ g$ je data sa \[(f\circ g)(x) = f(g(x)) = f(x^2)= 2x^2.\] Dakle vidimo da funkcije $g\circ f$ i $f\circ g$ ne moraju biti iste.

U Haskelu, operator kompozicije se označava sa ., i u potpunosti odgovara matematičkom operatoru kompozicije $\circ$. Tip operatora . je

(.) :: (b -> c) -> (a -> b) -> a -> c

Iz tipa vidimo da je prvi argument funkcija tipa b -> c pa zatim funkcija tipa a -> b. Primenom vrednosti ova dva tipa, ostaje nam tip a -> c koji predstavlja funkciju.

Primer 12.

Prethodni primer možemo prevesti u Haskel. Funkcije f i g i kompozicije se lako definišu:

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

g :: Int -> Int
g x = x ^ 2

h1 :: Int -> Int
h1 = g . f

h2 :: Int -> Int
h2 = f . g

Učitavanjem u GHCi, možemo proveriti kompozicije nad nekoliko vrednosti

ghci> h1 3
36
ghci> h2 3
18

Funkcije se ne mogu proizvoljno komponovati. Da bismo mogli funkciju g da primenimo na vrednost f x, neophodno je da domen funkcije g bude jednak kodomenu funkcije f. Zato su argumenti operatora . funkcije tipa b -> c i a -> b.

Primer 13.

Neka je dat kod

paran :: Int -> Bool
paran x = mod x 2 == 0

dužina :: [a] -> Int
dužina xs = length xs

Dve navedene funkcije možemo da komponujemo samo na jedan način. Pokušaj konstrukcije kompozicije dužina . paran dovešće do tipske greške.

ghci> k1 = paran . dužina
ghci> k2 = dužina . paran

<interactive>:7:15: error:
    • Couldn't match type ‘Bool’ with ‘t0 a0’
        Expected: a -> t0 a0
            Actual: a -> Bool
    • In the second argument of ‘(.)’, namely ‘paran’
      In the expression: dužina . paran
      In an equation for ‘k2’: k2 = dužina . paran

Zadatak 5. Neka je f :: A -> B i g :: B -> C -> D. Da li je g . f dobro tipiziran izraz? Ako jeste, koji je njegov tip?

Zadatak 6. Neka je f :: A -> B -> C i g :: C -> D. Da li je g . f dobro tipiziran izraz? Ako jeste, koji je njegov tip?

Zadatak 7. Neka je f :: (A -> B) -> C i g :: C -> D. Da li je g . f dobro tipiziran izraz? Ako jeste, koji je njegov tip?

Zadatak 8. Neka su p i q dve funkcije tipa a -> Bool. Zašto su filter p . filter q i filter (\x -> p x && q x) iste funkcije?

Kako je (filter p . filter q) xs = filter p (filter q xs) to se primenom funkcije filter p . filter q na listu xs odstranjuju svi elementi koji ne zadovoljavaju predikat q, a zatim se odstranjuju sve elementi koji ne zadovoljavaju predikat p. Prema tome, u listi (filter p . filter q) xs se nalaze svi elementi koji zadovoljavaju predikate p i q. A upravo se takva lista dobija i kao filter (\x -> p x && q x) xs.

Zadatak 9. Implementirati funkciju ks :: [a -> a] -> a -> a koja uzima listu funkcija i vraća njihovu kompoziciju. Tačnije, za funkciju ks mora važiti \[\mathrm{ks}\;[f_1, f_2, \dots, f_n] = f_1 \circ f_2 \circ \cdots \circ f_n\]

Zadatak možemo da rešimo rekurzivno. Funkcija ks primenjena na praznu listu treba da nam da identičku funkciju \x -> x koja je već definisana u Haskelu pod imenom id. Ako lista funkcija nije prazna, tada je možemo rastaviti na glavu i na rep, rekurzivno naći kompoziciju repa, a zatim komponovati glavu sa tom kompozicijom:

ks :: [a -> a] -> a -> a
ks [] = id
ks (f:fs) = f . ks fs

Navedeni rekurzivni šablon može se zameniti sa foldl funkcijom:

ks :: [a -> a] -> a -> a
ks fs = foldl (.) id fs

Zadatak 10. Dati primer tipa $X$ i funkcije $f \colon X \to X$ takve da važi \[f = f \circ f = f \circ f \circ f = \cdots\]

Zadatak 11. Dati primer tipa $X$ i funkcije $f \colon X \to X$ takve da važi \[f \ne f \circ f, \qquad f = f \circ f \circ f.\]

Zadatak 12. Kog je tipa izraz . (.)?

Zadatak 13. Kog je tipa izraz (.) (.)?

Operator aplikacije

Operator aplikacije je operator koji na prvi pogled ne radi ništa korisno. Definicija ovog operatora je

infixr 0
($) :: (a -> b) -> a -> b
f $ a = f a

Dakle, operator $ primenjuje (aplicira) funkciju na vrednost. Razlog zašto je $ koristan, je taj što je $ definisan sa najnižim prioritetom, dok aplikacija funkcije na vrednost (f x) ima najviši prioritet. Pošto $ ima najniži prioritet, često se može iskoristiti za uklanjanje zagrada iz izraza.

Primer 14.

Ako želimo funkciju f :: Int -> Int da primenimo na vrednost 32 * 81, tada je neispravno napisati f 32 * 81. Aplikacija ima veći prioritet od množenja pa se izraz f 32 * 81 tumači kao (f 32) * 81 što ne želimo. Ali ako iskoristimo operator aplikacije $, tada jednostavno možemo napisati f $ 32 * 81. Kako $ ima manji prioritet od *, navedeni izraz će se protumačiti kao f (32 * 81) što smo i želeli.

Naravno, ušteda od jednog karaktera koju smo ostvarili na prethodnom primeru nije vredna uvođenja posebnog operatora. Ali operator $ se može iskoristiti u mnogim drugim situacijama.

Primer 15.

Ako bismo želeli da niz funkcija f1, f2, f3, f4 primenimo jednu za drugom, prvi pokušaj bi verovatno bio

f4 (f3 (f2 (f1 x)))

Primetimo da ne možemo izostaviti zagrade iz navedenog izraza, jer je aplikacija levo asocijativna te se izraz f4 f3 f2 f1 x tumači kao (((f4 f3) f2) f1) x (što u ovom slučaju nema smisla).

I ovde ćemo iskoristiti $ da pojednostavimo zapis. Korišćenjem činjenice da je $ definisan kao desnoasocijativan operator, možemo pisati

f4 $ f3 $ f2 $ f1 x

Naravno, navedeni kod možemo napisati i korišćenjem kompozicije. Time dobijamo

(f4 . f3 . f2 . f1) x

Međutim, možemo da iskoristimo operator $ da bismo aplicirali kompoziciju na vrednost x. Kako $ ima manji prioritet od ., možemo pisati

f4 . f3 . f2 . f1 $ x

Osim što se često koristi da pojednostavi zapis, $ je koristan kad god je potrebno eksplicitno navesti primenu funkcije na argument. Na primer, ako su nam date liste [1, 2, 3] :: [Int] i [f, g, h] :: [Int -> Int], tada uparivanje funkcija sa brojevima možemo jednostavno napisati kao

zipWith ($) [f, g, h] [1, 2, 3]

Ovim se naravno dobija lista [f 1, g 2, h 3]

Slično, ako je data lista funkcija [f1, f2, f3] i jedna vrednost x, tada možemo iskoristiti parcijalnu aplikaciju i napisati map ($ x) [f1, f2, f3] da bi smo dobili listu [f1 x, f2 x, f3 x]⁵.

5. Da ne znamo za $, verovatno bi smo sa map funkcijom iskoristili lambdu \f -> f x.

Operator podizanja

Za funkciju map se kaže da podiže funkcije tipa A -> B do funkcija tipa [A] -> [B]. Zaista, kada map apliciramo na f :: A -> B, dobijamo vrednost tipa [A] -> [B]. Zbog toga što se map izuzetno često koristi u kodu, ova funkcija poseduje i operatorski oblik <$>⁶. Sa leve strane operatora se navodi funkcija, a sa desne strane lista.

6. Zapravo <$> je funkcija fmap :: (a -> b) -> M a -> M b koja se može koristiti za podizanje u kontekstu mnogih struktura podataka (a ne samo lista). Funkcija map je samo specijalan slučaj funkcije fmap. Više o tome kasnije...

Primer 16.

Ako smo do sada koristili map, ne bi trebalo da imamo problema sa <$>.

ghci> (*2) <$> [1 .. 10]
[2,4,6,8,10,12,14,16,18,20]

Zadatak 14. Neka je f :: A -> B i g :: B -> C. Zašto su map g . map f i map (g . f) iste funkcije? Koji su odgovarajući izrazi sa <$> operatorom?

Funkcija map g . map f je kompozicija funkcija map f i map g. Funkcija map f transformiše neku listu [x1, x2 ... xN] u listu [f x1, f x2 ... f xN], a zatim funkcija map g transformiše tu listu u [g (f x1), g (f x2)... g(f xN)]. Sa druge strane, funkcija map (g . f) primenjuje kompoziciju g . f na svaki element liste, odnosno [x1, x2 ... xN] transformiše u [(g . f) x1, (g . f) x2 ... (g . f) xN]. Međutim, po definiciji kompozicije funkcije, jasno je da su liste [g (f x1), g (f x2)... g(f xN)] i [(g . f) x1, (g . f) x2 ... (g . f) xN] iste vrednosti.

Kako se map f može zapisati kao (f <$>), i analogno za g, to se jednakost map g . map f = map (g . f) može zapisati kao (g <$>) . (f <$>) = ((g . f) <$>). Ako obe strane ove jednakost apliciramo na vrednost xs, dobijamo ((g <$>) . (f <$>)) xs = (g . f) <$> xs. Raspisivanjem kompozicije sa leve stane, dobijamo g <$> (f <$> xs) = (g . f) <$> xs. Operator <$> je desnoasocijativan, pa se poslednja jednakost može zapisati kao g <$> f <$> xs = (g . f) <$> xs.

Primer: Određen integral

U nastavku je dat jedan primer koji nije neophodan za razumevanje ostatka knjige. Primer zahteva određena predznanja iz matematike.

Otkriće diferencijalnog i integralnog računa je jedno od najznačajnijih trenutaka u istoriji nauke. Navedeni matematički aparati su neophodni za formulaciju mnogih prirodnih fenomena: od kretanja elektrona do kretanja galaksija. Svakako, ova tematika je van opsega ove knjige, ali ovde možemo da prikažemo kako se elegantno može implementirati formula za aproksimaciju određenih integrala.

Određeni integral funkcije $f\colon \mathbb R \to \mathbb R$ na intervalu $[a,b]$, označava se sa \[\int\limits_a^b f(x)\,\mathrm dx\] i može se shvatiti kao površina između grafika funkcije $f$ i $x$ ose⁷. Integral, tj. površina, može se aproksimirati Rimanovom sumom, odnosno sumom površina malih pravougaonika koji aproksimiraju površinu ispod grafika.

Aproksimacija površine ispod grafika funkcije $f$ nizom pravougaonika. Iako nije neophodno da svi pravougaonici budu iste širine, mi ćemo algoritam implementirati tako da su svi iste širine, baš kao na ovoj ilustraciji.

Rimanova suma se može zapisati kao \[I = \sum\limits_{i=0}^{n} f\left(x_i\right) \left(x_{i+1} - x_i\right),\] gde je \[a = x_0 < x_1 < \cdots < x_{n} < x_{n+1} = b\] niz tačaka koje dele interval $[a,b]$. Navedene podeone tačke se mogu uzeti proizvoljno, ali što ih više ima to će kvadratići biti uži, a samim tim će aproksimacija površine biti tačnija.

Lako možemo implementirati funkciju int :: (Double -> Double) -> Double -> Double -> Double koja računa određen integral neke funkcije f :: Float -> Float. Prvi parametar funkcije int je funkcija f, drugi početak intervala a treći kraj intervala. Povratna vrednost je aproksimacija određenog integrala Rimanovom sumom.

Listu podeonih tačaka možemo formirati korišćenjem izlistavanja. Ako su a i b krajevi intervala, a d neki dovoljno mali broj, tada lista [a, a + d .. b] predstavlja podelu intervala $[a,b]$. Primenom funkcije f na svaki element date liste, dobijamo listu visina pravougaonika: map f [a, a + d .. b]. Množenjem svake od ovih visina sa širinom intervala, odnosno sa d, dobijamo listu površina pravougaonika: map (\h -> h * d) (map f [a, a + d .. b]). Na kraju, dovoljno je da površine saberemo: sum (map (\h -> h * d) (map f [a, a + d .. b])).

Kompletna implementacija funkcije int je

int :: (Double -> Double) -> Double -> Double -> Double
int f a b = sum povrsine
    where
        povrsine = map (\h -> h * d) (map f [a, a + d .. b])
        d = (b - a) / 200

U ovoj implementaciji uzeto je da je d jednak $200$-tom delu intervala $[a, b]$. Prime tome, lista podeonih tačaka će sadržati $200$ elemenata. Za veću preciznost, dovoljno je uvećati konstantu 200.

Primer 17.

U GHCi okruženju je dostupna funkcija sin kao i konstanta pi. Ako učitamo implementaciju funkcije int možemo da izračunamo integral sinusa na intervalu $[0,\pi]$:

ghci> int sin 0 pi
1.9999588764792144

Koristeći operatore i sekcije, prethodnu definiciju možemo elegantnije da napišemo. Umesto map funkcije možemo iskoristiti operator podizanja <$>. Umesto lambda izraza \h -> h * d, možemo koristiti sekciju (*d). A umesto sum (map g ys), možemo iskoristiti $ i osloboditi se zagrada: sum $ map g ys. Sve navedeno nas dovodi do naredne definicije:

int :: (Double -> Double) -> Double -> Double -> Double
int f a b = sum $ (* d) <$> (f <$> [a, a + d .. b])
    where d = (b - a) / 200

Zadatak 15. Koristeći činjenicu da je \[\sum\limits_{i=0}^{n} (f\left(x_i\right) \cdot d) = d \cdot \sum\limits_{i=0}^{n} f\left(x_i\right),\] dodatno pojednostaviti kôd funkcije int.

int :: (Double -> Double) -> Double -> Double -> Double
int f a b = d * (sum $ f <$> [a, a + d .. b])
    where d = (b - a) / 200

Zaključak

Kreiranje operatora je moćna tehnika koju malo programskih jezika poseduje. Korišćenje operatora kao svih ostalih funkcija, kao i ad hoc transformisanje operatora u prefiksne funkcije i obrnuto, su tehnike koje još manje jezika poseduje. Nesumnjivo je da navedene osobine dozvoljavaju Haskel programeru veliku ekspresivnost.

Ipak, potrebno je biti veoma pažljiv sa kreiranjem operatora. Uvođenjem novih operatora možemo značajno otežati razumevanje koda. Čak i sami sebi možemo otežati programiranje kada posle kratke pauze u radu na nekom projektu zaboravimo semantiku operatora koje smo ranije definisali.

Iako nećemo u narednim lekcijama često definisati operatore, upoznaćemo sa mnogim, za nas novim, operatorima već definisanim u Haskel jeziku. Kao što ćemo videti, takvi operatori će biti korisni u rešavanju mnogih problema.