Основни појмови језика Haskell¶

Изрази¶

Језик Haskell је чист функционални језик и као такав он не подржава наредбе. Основни концепт чине изрази. Изрази се граде од променљивих и константи применом разних операција и функција. Кренимо од аритметичких (бројевних) израза. Подржане су целобројне константе (при чему се могу користити произвољно велики бројеви) и реалне константе (које се подразумевано записују као бројеви у покретном зарезу). Основни нумерички типови које ћемо ми разматрати су:

• Int – „машински“ цели бројеви (записани са најмање 30 битова, најчешће са 32 или 64);

• Integer – неограничени цели бројеви;

• Float – бројеви у покретном зарезу једноструке тачности;

• Double – бројеви у покретном зарезу двоструке тачности.

Типови се групишу у такозване класе типова (енг. type classes) – њих не треба схватати као класе у објектно-оријентисаном програмирању. Сви наведени нумерички типови припадају класи Num. Сви ови бројеви су и реални бројеви па припадају класи Real. Целобројни типови Int и Integer припадају и класи Integral, док типови Float и Double припадају и класи Fractional. Постоје и друге класе типова, које ћемо увести касније, када се за њима јави потреба. Класе типова омогућавају да се неке функције дефинишу полиморфно, тако да оперишу над подацима било ког типа унутар неке класе. Ми нећемо често користити ову могућност, али ће неколико таквих примера бити приказано када се за тим природно јави потреба.

Подржане су и све основне аритметичке операције. На пример,

Prelude> 123456789 * 987654321
121932631112635269

Prelude> 5 / 2
2.5

Prelude> 0.2 * 3
0.6000000000000001

Операција којом се израчунава целобројни количник представљена је функцијом div, а остатак при дељењу функцијом mod. Функције се пишу префиксно, али је функције два аргумента могуће писати и инфиксно, тако што се запишу у оквиру обратних апострофа (на пример, mod 12 5 је исто што и 12 `mod` 5).

Prelude> div 13 5
2

Prelude> 13 `div` 5
2

Prelude> 13 `mod` 5
3

Применом релацијских оператора ==, /=, <, >, <= и >= на аритметичке изразе добијају се логичке вредности.

Prelude> 2 == 2
True

Prelude> 2 /= 2
False

Prelude> 5 <= 2
False

Логичке вредности се могу комбиновати применом логичких оператора not, && и ||.

Сложени изрази се могу учинити читљивијим употребом оператора let-in. На пример, наредни израз израчунава износ који ће добити запослени који је радио 4 дана за дневни бруто хонорар од 3700 динара, ако се приликом исплате на бруто износ наплаћује порез од 20%.

Prelude> let broj_dana = 4
             dnevni_honorar = 3700
             bruto = broj_dana * dnevni_honorar
             porez = 20 / 100
          in bruto * (1 - porez)
11840.0

Нагласимо да променљиве које су уведене у let-in изразу нису класичне променљиве на какве смо навикли у императивном програмирању и не може им се мењати вредност. Можемо их схватити само као имена за неке вредности.

Подржани су и условни изрази if-then, који одговарају тернарном оператору ?: у језику C# (а не наредби if).

Prelude> if 3 > 7 then 0 else 1
1

Ниске су представљене типом String (који је заправо само синоним за листу карактера). Константне ниске се записују између двоструких наводника. Ниске се могу надовезати оператором ++.

Prelude> "Zdravo" ++ " " ++ "svima" ++ "!"
"Zdravo svima!"

О нискама ће бити више речи у поглављу о листама.

Дефинисање функција¶

Кренимо од једноставне функције којом се израчунава обим квадрата чија је дужина странице \(a\). Обим се израчунава на основу формуле \(O = 4\cdot a\). Претпоставимо за почетак да је дужина квадрата увек цео број.

obim_kvadrata :: Int -> Int
obim_kvadrata a = 4 * a

Прва линија представља декларацију функције (каже се и потпис типа функције, енг. type signature или опис типа или спецификација типа). Њом се описује да се функција зове obim_kvadrata, да прима један аргумент типа Int и да враћа резултат типа Int (тип Int -> Int је тип функције која има један целобројни аргумент и израчунава целобројни резултат). Друга линија је једнакост која представља дефиницију функције.

Када је ова функција дефинисана, можемо је позвати. На пример,

Prelude> obim_kvadrata 5
20

Пошто језик Haskell има механизам закључивања типова, прва линија је опциона. Додуше, Haskell би закључио мало општији тип, јер оператор * може да се примени и на друге бројевне типове (на пример, на реалне бројеве тј. тип Float и Double). Ако бисмо сами написали најопштији могући тип, функција би изгледала овако:

obim_kvadrata :: Num a => a -> a
obim_kvadrata a = 4 * a

Ознака a означава било који тип (у питању је тзв. типска променљива), па тип a -> a означава функцију која прима аргумент типа a и враћа вредност типа a. Међутим, тип а не може бити било какав тип, већ мора бити бројевни тип да би подржао операцију множења. Зато је пре типа a -> a потребно навести додатни услов, а то је да тип a мора да припада тзв. класи типова Num, која означава бројевне типове. Дакле, опис типа Num a => a -> a читамо на следећи начин: функција прима аргумент неког типа a и враћа вредност истог типа a, при чему тип a мора припадати класи типова Num, тј. мора бити у питању неки бројевни тип.

Дефинишимо сада функцију која израчунава обим правоугаоника чије су дужине страница \(a\) и \(b\). Обим се сада израчунава формулом \(O = 2\cdot (a + b)\). Ова функција је слична претходној, једино што прима два аргумента. Ако претпоставимо да су они целобројни, долазимо до следеће дефиниције.

obim_pravougaonika :: Int -> Int -> Int
obim_pravougaonika a b = 2 * (a + b)

Размотримо мало детаљније опис типа Int -> Int -> Int. Иако се он може тумачити као да је у питању функција која прима два аргумента типа Int и враћа резултат типа Int, овај опис треба читати као Int -> (Int -> Int), тј. тумачити је као функцију која прима аргумент типа Int, а враћа функцију типа Int -> Int. Све функције су функције једне променљиве, а функције више променљивих се добијају техником Каријевања (енг. currying). Дакле важи:

• Вредност израза obim_pravougaonika 3 5 је целобројног типа Int и износи 16.

• Вредност израза obim_pravougaonika 3 је функција типа Int -> Int која прима један целобројни аргумент и враћа обим правоугаоника коме је једна страница 3, а друга задата тим аргументом.

• Вредност израза obim_pravougaonika је функција која прима један аргумент типа Int и враћа функцију која прима Int и враћа Int.

Наравно, уместо типа Int функција се може уопштити на произвољни нумерички тип.

obim_pravougaonika :: Num a => a -> a -> a
obim_pravougaonika a b = 2 * (a + b)

Са десне стране дефиниције функције налазе се произвољни изрази, па је могуће да буду и изрази који користе let-in.

На пример, дефинишимо функцију која израчунава обим ограде око фудбалског терена познате дужине и ширине, ако се зна да је ограда постављена на истом растојању од сваке стране терена.

obim_ograde :: Float -> Float -> Float -> Float
obim_ograde sirina duzina rastojanje =
    let sirina_ograde = sirina + 2*rastojanje
        duzina_ograde = duzina + 2*rastojanje
     in obim_pravougaonika sirina_ograde duzina_ograde

Приликом дефинисања функције постоји још један начин да се уведу помоћне променљиве.

obim_ograde :: Float -> Float -> Float -> Float
obim_ograde sirina duzina rastojanje =
    obim_pravougaonika sirina_ograde duzina_ograde
    where sirina_ograde = sirina + 2*rastojanje
          duzina_ograde = duzina + 2*rastojanje

У секцији where је могуће дефинисати и помоћне (локалне) функције. Претходни пример подразумева да је функција obim_pravougaonika већ дефинисана, а да није, она би могла да се дефинише у склопу дефиниције функције obim_ograde (наравно, тада не би могла да се користи у другим функцијама).

obim_ograde :: Real -> Real -> Real -> Real
obim_ograde sirina duzina rastojanje =
    obim_pravougaonika sirina_ograde duzina_ograde
    where sirina_ograde = sirina + 2*rastojanje
          duzina_ograde = duzina + 2*rastojanje
          obim_pravougaonika :: Num a => a -> a -> a
          obim_pravougaonika a b = 2 * (a + b)

Уместо једне једнакости, функције могу бити дефинисане и коришћењем већег броја једнакости. Тада се користи тзв. уклапање шаблона (енг. pattern matching). Приликом израчунавања вредности функције једнакости се проверавају редом и резултат се одређује коришћењем прве једнакости која се уклапа са задатом вредношћу аргумента. На пример, наредна функција одређује назив на основу редног броја дана. Доња црта у последњој једнакости се поклапа са било којим аргументом, тако да ће се у случају било које вредности која није између 1 и 7 добити грешка.

naziv_dana :: Int -> String
naziv_dana 1 = "Ponedeljak"
naziv_dana 2 = "Utorak"
naziv_dana 3 = "Sreda"
naziv_dana 4 = "Cetvrtak"
naziv_dana 5 = "Petak"
naziv_dana 6 = "Subota"
naziv_dana 7 = "Nedelja"
naziv_dana _ = "Greska"

Још једна интересантна синтаксичка конструкција која избегава коришћење if-then израза и чини код мало читљивијим су услови који се додају испред једнакости у дефиницијама (тзв. чувари, енг. guards). Наредна функција израчунава оцену на основу броја поена (претпоставља се да ће број поена бити између 0 и 100).

ocena :: Int -> Int
ocena poeni
  | poeni < 40    = 1
  | poeni < 55    = 2
  | poeni < 70    = 3
  | poeni < 85    = 4
  | otherwise     = 5

Услови се проверавају редом (као у конструкцији else if у императивним програмским језицима). Последњи услов је увек испуњен (подразумевајући да претходни нису) и одговара грани else.

Рекурзивне функције¶

Пошто је Haskell чист функционални језик, није могућа измена вредности променљивих и самим тим није могуће коришћење петљи. Уместо тога, контрола тока се може постићи коришћењем рекурзивних функција (функција које позивају саме себе). Видећемо касније да се контрола тока може остварити и на друге начине (пре свега коришћењем функција вишег реда), тако да директно коришћење рекурзије треба избегавати када год је то могуће (а није увек).

Дефинишимо рекурзивну функцију која израчунава факторијел.

faktorijel :: Integer -> Integer
faktorijel 0 = 0
faktorijel n = n * faktorijel (n - 1)

Ова дефиниција у потпуности одговара математичкој рекурзивној дефиницији факторијела:

Израчунавање оваквих функција своди се на низ једнакости. На пример,

faktorijel 5 =
5 * faktorijel 4 =
5 * (4 * faktorijel 3) =
5 * (4 * (3 * faktorijel 2)) =
5 * (4 * (3 * (2 * faktorijel 1))) =
5 * (4 * (3 * (2 * (1 * faktorijel 0)))) =
5 * (4 * (3 * (2 * (1 * 1)))) =
120

Приметимо да се у имплементацији користи уклапање шаблона. Наравно, гранање се може остварити и на друге начине. На пример, могуће је употребити израз if-then.

faktorijel :: Integer -> Integer
faktorijel n = if n == 0 then 1 else n * faktorijel (n - 1)

А могуће је употребити и чуваре:

faktorijel :: Integer -> Integer
faktorijel n
   | n == 0     = 1
   | otherwise  = n * faktorijel (n - 1)

Алтернатива би била да факторијел дефинишемо на следећи начин:

faktorijel :: Integer -> Integer
faktorijel n = product [1..n]

Ова дефиниција користи листе (њима ћемо се веома детаљно бавити ускоро) и каже да је факторијел броја n производ елемената листе која садржи бројеве од 1 до n (функција product рачуна производ). Можемо слободно да констатујемо да је ова дефиниција још декларативнија од оне засноване на рекурзији.

Веома слично можемо математичку дефиницију степеновања броја \(x\) на изложилац \(n\) који је природан број:

претворити у рекурзивну дефиницију у програмском језику Haskell:

stepen :: Num a => a -> Integer -> a
stepen x 0 = 1
stepen x n = x * stepen x (n - 1)

Приметимо да смо тип функције оставили отвореним (иста дефиниција важи за основу x произвољног нумеричког типа a).

Наравно, степеновање се може извршити и ефикасније, ако се примети да за парне вредности \(n\) важи \(x^{n} = (x^2)^\frac{n}{2}\).

stepen :: Num a => a -> Integer -> a
stepen x 0 = 1
stepen x n =
  | n `mod` 2 == 0   = stepen (x * x) (n `div` 2)
  | otherwise        = x * stepen x (n - 1)

Прикажимо израчунавање ове функције.

stepen 2 10 =
stepen 4 5 =
4 * stepen 4 4 =
4 * stepen 16 2 =
4 * stepen 256 1 =
4 * 256 =
1024

Још један пример једноставне рекурзивне функције може бити Еуклидов алгоритам за одређивање највећег заједничког делиоца два броја.

nzd :: Integer -> Integer -> Integer
nzd a 0 = 0
nzd a b = nzd b (a `mod` b)

Прикажимо израчунавање ове функције на једном примеру:

nzd 48 18 =
nzd 18 12 =
nzd 12 6 =
nzd 6 0 =
6

Репна рекурзија¶

Приметимо да се приликом израчунавања вредности факторијела све вредности првог чиноица морају сложити на стек и да се тек при изласку из рекурзије рачуна производ. У случају дубоке рекурзије овакво понашање може довести до прекорачења стека. За разлику од тога сваки наредни позив функције nzd само замени вредност њених аргумената и нема потребе памтити никакве податке на стеку. То је зато што је функција nzd репно-рекурзивна (енг. tail-recursive), што значи да се резултат функције добија рекурзивним позивом за промење аргументе, тј. да резултат рекурзивног позива не треба додатно обађивати да би се добио коначан резултат. За разлику од тога функција faktorijel није репно-рекурзивна, јер се резултат рекурзивног позива faktorijel (n - 1) додатно мора помножити са n. У оптимизованој верзији функције stepen један рекурзивни позив је репни, а други није. Репну рекурзију је пожељно користити када год је то могуће, да би се избегла могућност прекорачења стека (нарочито код функција код којих дубина рекурзије може бити велика, тј. линеарно зависи од вредности аргумената).

И факторијел је могуће дефинисати репно-рекурзивно.

faktorijel :: Integer -> Integer
faktorijel n = faktorijel' n 1
   where faktorijel' :: Integer -> Integer -> Integer
         faktorijel' 0 acc = acc
         faktorijel' n acc = faktorijel' (n-1) (n * acc)

Размотримо извршавање ове функције:

faktorijel 5 =
faktorijel' 5 1 =
faktorijel' 4 5 =
faktorijel' 3 20 =
faktorijel' 2 60 =
faktorijel' 1 120 =
faktorijel' 0 120 =
120

Функција faktorijel посао препушта функцији faktorijel', уводећи нову променљиву у којој ће се акумулирати резултат (такве променљиве ћемо називати акумулатор, енг. accumulator). Приметимо да ова имплементација сасвим одговара следећој императивној имплементацији:

int faktorijel(int n) {
    int acc = 1;
    while (n > 0) {
       acc = acc * n;
       n = n - 1;
    }
    return acc;
}

Све је ово лепо у теорији, али у пракси постоји проблем, због лењог израчунавања које је уграђено у језик Haskell. Наиме, вредност првог аргумента се увек експлицитно израчунава, јер је потребно да се она зна да би се знало да ли се примењује прво или друго правило. Међутим, вредност другог аргумента није потребна до самог краја израчунавања, тако да се то израчунавање одлаже до самог краја.

faktorijel 5 =
faktorijel' 5 1 =
faktorijel' 4 (5*1) =
faktorijel' 3 4*(5*1) =
faktorijel' 2 3*(4*(5*1)) =
faktorijel' 1 2*(3*(4*(5*1))) =
faktorijel' 0 1*(2*(3*(4*(5*1)))) =
120

Да би се спречила изградња овог великог израза, потребно је некако натерати Haskell да други аргумент израчуна чим може, а не лењо, тек када затреба. Да би се аргумент функције f израчунао пре позива функције f можемо употребити оператор $! (тзв. оператор стриктне примене функције). Измена у коду је мала, али доноси жељену оптимизацију. Функција faktorijel' (n-1) (подсетите се Каријевања) се примењује на аргумент n*acc, чије се израчунавање захтева пре позива функције.

faktorijel' :: Integer -> Integer -> Integer
   faktorijel' 0 acc = acc
   faktorijel' n acc = faktorijel' (n-1) $! (n * acc)

Репну рекурзију је по правилу боље користити него рекурзију која није репна, јер функционални програмски језици (али не само они) ту рекурзију уклањају и мењају је итерацијом (као што смо описали, не креирају се нови стек оквири, већ се у меморији рачунара мењају вредности променљивих, што одговара итеративном начину израчунавања).

Размотримо још један пример ове технике. Фибоначијев низ се дефинише помоћу следеће рекурзивне дефиниције:

\[\begin{split}\begin{eqnarray*} F_0 &=& 0\\ F_1 &=& 1\\ F_n &=& F_{n-1} + F_{n-2}, \quad n \geq 2 \end{eqnarray*}\end{split}\]

Ова дефиниција се може директно превести у Haskell.

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Међутим, овде долази до понављања рекурзивних позива (један те исти рекурзивни позив се извршава више пута), што узрокује експонецијалну сложеност и веома неефикасно рачунање. Проблем није у програмском језику, већ у лоше имплементираном алгоритму.

Итеративно решење се може добити применом репне рекурзије, тј. програмирања са акумулатором. Функцији се прослеђују два члана Фибоначијевог низа (назовимо их p као претходни и t као текући) и редни број n елемента који желимо да израчунамо. Ако је n једнако нула враћамо претходни елемент, ако је једнако један враћамо текући, а у супротном, у рекурзивном позиву рачунамо нова два елемента низа: текући постаје претходни, а збир претходног и текућег даје нови текући елемент.

fib :: Integer -> Integer
fib n = fib' 0 1 n
  where
     fib' p t 0 = p
     fib' p t 1 = t
     fib' p t n = fib' t (p + t) (n - 1)

Прикажимо извршавање ове функције на једном примеру.

fib 6 =
fib' 0 1 6 =
fib' 1 1 5 =
fib' 1 2 4 =
fib' 2 3 3 =
fib' 3 5 2 =
fib' 5 8 1 =
8

За разлику од полазне, ова имплементација је веома ефикасна и суштински одговара наредној итеративној имплементацији.

static uint fib(uint n)
{
    uint p = 0, t = 1;
    if (n == 0) return p;
    while (n != 1) {
       uint tmp = p + t;
       p = t;
       t = tmp;
       n--;
    }
    return t;
}