Функције вишег реда¶

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

Функције које се прослеђују функционалима су често веома једноставне и пожељно је имати могућност њиховог једноставног дефинисања унутар самог позива функционала. За то се могу користити анонимне функције, тј. ламбда изрази. На пример, израз \x -> x + 1 представља анонимну функцију која свој аргумент увећава за 1, док израз \x y -> x + y `mod` 2 == 0 означава функцију која проверава да ли је збир њена два аргумента паран. Анонимне функције се могу добити и парцијалном применом. Наиме, све функције су Каријеве па се често задавањем једног аргумента добијају нове функције. На пример, max 0 је анонимна функција која прима број и враћа га ако је позитиван, а враћа 0 ако није. И инфиксни оператори могу бити парцијално примењени. Тако, на пример, (> 0) означава функцију која прима број и испитује да ли је позитиван. Исто важи и за израз (0 <). Инфиксни оператори се могу проследити функционалима тако што се наведу у заградама. На пример, (+) означава функцију сабирања.

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

• any pred list – функција any прихвата предикат pred (функцију која враћа тип bool, тј. проверава да ли дати елемент има неко својство) и листу list. Враћа True ако постоји бар један елемент у листи за који предикат pred враћа True, иначе враћа False.

  Prelude> any (> 3) [1, 2, 3, 4, 5]
  True
  

• all pred list – функција all прихвата предикат pred и листу list. Враћа True ако сви елементи у листи задовољавају предикат pred, иначе враћа False.

  Prelude> all (> 3) [1, 2, 3, 4, 5]
  False
  

• zipWith f list1 list2 – функција zipWith прихвата функцију f и две листе list1 и list2. Она примењује функцију f на парове елемената из list1 и list2 и враћа нову листу резултата.

  Prelude> zipWith (+) [1, 2, 3] [4, 5, 6]
  [5, 7, 9]
  

• takeWhile pred list – функција takeWhile прихвата предикат pred и листу list и издваја елементе са почетка листе све док задовољавају предикат pred.

  Prelude> takeWhile (>0) [1, 2, -3, -4, 5, 6]
  [1, 2]
  

• dropWhile pred list – функција dropWhile прихвата предикат pred и листу list и уклања елементе са почетка листе све док задовољавају предикат pred.

  Prelude> dropWhile (>0) [1, 2, -3, -4, 5, 6]
  [-3, -4, 5, 6]
  

Помоћу ових функција можемо имплементирати још неке алгоритме.

Дефинисати функцију која проверава да ли је листа сортирана.

Провера да ли је листа сортирана се своди на проверу да ли су сви узастопни парови елемената такви да је први елемент мањи од или једнак другом.

pairs :: [a] -> [(a, a)]
pairs xs = zip xs (tail xs)

sorted :: Ord a => [a] -> Bool
sorted xs = all (\(x, y). x <= y) (pairs xs)

Prelude> sorted [1, 2, 3, 4]
True
Prelude> sorted [1, 2, 2, 3, 3, 4]
True
Prelude> sorted [1, 2, 4, 3, 5]
False

Тип a елемената листе мора бити такав да елементи могу да се пореде по величини, што је наглашено условом Ord a (тип a мора припадати класи типова Ord). Приметимо да је анонимна функција \(x, y) -> x <= y, која пореди узастопне елементе, дефинисана тако да има један аргумент који је уређени пар бројева. Заиста, листа pairs xs садржи уређене парове, а предикат је потребно задовољити на сваком уређеном пару. Погрешно би било користити само кратку нотацију all (<=) (pairs xs), јер је функција (<=) Каријева (њен тип је Ord a => a -> a -> a, а не Ord a => (a, a) -> a). Ово се, као што смо видели, лако решава коришћењем ламбда–израза. Међутим, пошто је овај сценарио чест, на располагању нам је и функција uncurry која од Каријеве функције прави функцију која ради над уређеним паровима. Уз њено коришћење провера сортираности би могла бити дефинисана на следећи начин:

sorted :: Ord a => [a] -> Bool
sorted = all (uncurry (<=)) . pairs

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

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

Заиста, ако је дата Каријева функција f типа a -> b -> c и уређени пар (x, y) типа ((a, b)), резултат типа c се добија тако што се функција f прво примени на x, па се тако добијена функција примени на y. Парцијална апликација my_uncurry f, дакле враћа функцију која очекује уређен пар, распакује његове елементе и затим примењује Каријеву функцију f редом на њих.

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

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

Слично бисмо могли дефинисати и функцију my_curry, која одговара библиотечкој функцији curry и која функцију која функционише над уређеним паровима претвара у Каријеву функцију.

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

Проверу сортираности можемо имплементирати и на друге начине. У наредној имплементацији се коришћењем функције zipWith прави листа вредности типа Bool, а затим се помоћу функције and врши њена конјункција.

sorted :: Ord a => [a] -> Bool
sorted xs = and (zipWith (<=) xs (tail xs))

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

Наредни функционали map, filter и fold се по свом значају и својој општости обично истичу (већина функционала се може дефинисати коришћењем ова три основна).

• Функција filter служи да из листе издвоји све оне елементе који задовољавају дато својство. Она прихвата предикат pred и листу list и враћа нову листу која садржи све оне елементе листе list за које предикат pred враћа True. Дакле, функција filter има следећи тип:

  filter :: (a -> Bool) -> [a] -> [a]
  

  Наредним позивима се издвајају сви позитивни, а затим и сви парни елементи листе.

  Prelude> filter (>0) [1, -2, 4, 0, -5, 8, 2]
  [1, 4, 8, 2]
  Prelude> filter (\x -> mod x 2 == 0) [1, 2, 4, 5, 6]
  [2, 4, 6]
  

  

  Функционал filter користимо када желимо да филтрирамо серију елемената, тј. да издвојимо све оне елементе који задовољавају неко својство.

• Функција map прихвата функцију f и листу list и гради нову листу тако што на сваки елемент листе list примени функцију f.

  Дакле, функција map има следећи тип:

  map :: (a -> b) -> [a] -> [b]
  

  Наредним позивом се квадрирају сви елементи листе, а затим се израчунавају степени двојке:

  Prelude> map (^2) [1, 3, 2, 4]
  [1, 9, 4, 16]
  Prelude> map (2^) [1, 3, 2, 4]
  [2, 8, 4, 16]
  

  

  Функционал map користимо када желимо да исто израчунавање применимо на сваки елемент неке серије елемената.

• Функционал fold (у варијантама foldl и foldr) служи да извршимо агрегацију неке серије елемената, узастопном применом неке операције, кренувши од неког почетног елемента (обично неутралног елемента за ту операцију).

  Размотримо, на пример, сабирање серије елемената. Збир елемената \([x_0, x_1, x_2]\) се може добити као \(((0 + x_0) + x_1) + x_2\) или као \(x_0 + (x_1 + (x_2 + 0))\). Први израз представља основу итеративног алгоритма за израчунавање збира.

  int zbir = 0;
  foreach (int x in xs)
     zbir = zbir + x;
  

  Веома слично, производ тих елемената добијамо изразима \(((1 \cdot x_0) \cdot x_1) \cdot x_2\) или као \(x_0 \cdot (x_1 \cdot (x_2 \cdot 1))\). Итеративни алгоритам се онда програмира на следећи начин.

  int proizvod = 0;
  foreach (int x in xs)
     proizvod = proizvod * x;
  

  Слично можемо дефинисати и функцију која одређује максимум серије природних бројева. \(max(max(max(0, x_0), x_1), x_2)\) или \(max(x_0, max(x_1, max(x_2, 0)))\).

  int maks = 0;
  foreach (int x in xs)
     maks = Math.Max(maks, x);
  

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

  foldl :: (b -> a -> b) -> b -> [a] -> b
  foldr :: (a -> b -> b) -> b -> [a] -> b
  

  Ове функције су примењиве и на друге колекције, не само на листе, па им је тип мало општији од наведеног, али ћемо их ми примењивати само на листе.

  Тип b означава тип резултата, а тип a означава тип елемената серије. Функција foldl прво добија функцију која на основу текућег резултата и текућег елемента серије израчунава нову вредност резултата, затим почетну вредност резултата и затим листу која садржи елементе који се редом обрађују. Функција foldr прима исте аргументе, осим што функција прима текући елемент серије и текући резултат у обратном редоследу. Ефекат ових функција се може описати на следећи начин.

  foldl f i [x0, x1, x2]
  f (f (f i x0) x1) x2     тј.   ((i `f` x0) `f` x1) `f` x2
  
  foldr f i [x0, x1, x2]
  f x0 (f x1 (f x2 i))     тј.   x0 `f` (x1 `f` (x2 `f` i))
  

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

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

  Prelude> foldl (+) 0 [1, 2, 3, 4]
  10
  
  Prelude> foldr (+) 0 [1, 2, 3, 4]
  10
  

  У оба случаја се креће од резултата 0 и у сваком кораку се резултат увећава за текући елемент листе.

Прикажимо сада како се ове функције могу користити за дефинисање разних других функција.

Дефинисати функцију која одређује све делиоце броја. Није потребно водити рачуна о ефикасности.

Ако не водимо рачуна о ефикасности, сви делиоци броја се могу лако одредити коришћењем филтрирања, директно на основу дефиниције.

divisors :: Integer -> [Integer]
divisors n = filter (\d -> n `mod` d == 0) [1..n]

Написати програм који одређује првих 15 Армстронгових бројева. Армстронгови бројеви су они k–тоцифрени бројеви чији је збир k–тих степена цифара једнак самом броју. Није потребно водити рачуна о ефикасности.

Употребићемо раније дефинисану функцију digits за одређивање цифара броја.

digits :: Integer -> [Integer]
digits 0 = []
digits n = (n `mod` 10) : digits (n `div` 10)

Дефинисаћемо сада функцију која проверава да ли је дати број Армстронгов. Након одређивања низа цифара cs и његове дужине k, сваку цифру дижемо на k-ти степен коришћењем функционала map и затим сабирамо добијене степене функцијом sum.

isArmstrongNumber :: Integer -> Bool
isArmstrongNumber n = let cs = digits n;
                           k = length cs
                      in sum (map (^k) cs) == n

Захваљујући лењости можемо дефинисати (бесконачну) листу Армстронгових бројева тако што ћемо из низа свих природних бројева издвојити оне који су Армстронгови. Након тога жељених првих 15 Армстронгових бројева добијамо узимањем првих 15 елемената те бесконачне листе (коришћењем функције take).

armstrongNumbers :: [Integer]
armstrongNumbers = filter isArmstrongNumber [1..]

armstrongNumbers15 :: [Integer]
armstrongNumbers15 = take 15 armstrongNumbers

Коришћењем функција and, or и map дефинисати функцију која проверава да ли сви елементи листе задовољавају дато својство (што ради функција all), да ли неки елемент листе задовољава дато својство (што ради функција any) и да ли листа садржи дати елемент (што ради функција elem).

my_all :: (a -> Bool) -> [a] -> Bool
my_all p xs = and (map p xs)

Још елегантније решење добијамо ако употребимо композицију.

my_all :: (a -> Bool) -> [a] -> Bool
my_all p = and . map p

На сличан начин можемо добити и функцију која проверава да ли дата листа садржи дати елемент (што ради функција elem).

my_elem :: Eq a => a -> [a] -> Bool
my_elem x = or . map (== x)

Наравно, препознајете вероватно да се овде заправо крије any, који је имплементиран композицијом or и map.

Применом функција foldl или foldr дефинисати функције за израчунавање производа листе, минумума и обртање листе.

Дефинисање производа је веома једноставно (крећемо од резултата 1 и у сваком кораку множимо текући елемент и текући резултат).

my_prod :: Num a => [a] -> a
my_prod = foldr (*) 1

Налажење минимума има смисла само за непразне листе. Уместо да размишљамо која би вредност била неутрална за операцију минимума (а то је \(+\infty\)), можемо кренути од почетног елемента листе, а затим обрадити реп листе (на текући резултат и текући елемент листе у сваком кораку примењујемо функцију max којом се израчунава максимум два дата броја.

my_maximum :: Ord a => [a] -> a
my_maximum xs = foldl max (head xs) (tail xs)

Обртање листе можемо остварити тако што елементе обрађујемо један по један с лева надесно (користимо foldl) и у сваком кораку текући елемент додајемо на почетак тренутног резултата.

my_reverse :: [a] -> [a]
my_reverse = foldl (\xs x -> x:xs)  []

С обзиром на то да први аргумент функције foldl мора прво да прими текући резултат, а затим елемент који се дописује, морали смо употребити ламбда–израз, тј. није било могуће написати само foldl (:) []. Ипак, постоји уграђена функција flip која прима Каријеву функцију и обрће јој редослед прва два аргумента.

my_reverse :: [a] -> [a]
my_reverse = foldl (flip (:))  []

Чак и да функција flip није дефинисана, она би се лако могла дефинисати.

my_flip :: (a -> b -> c) -> (b -> a -> c)
my_flip f b a = f a b

Коришћењем неких од функционала map, filter, fold дефинисати функцију која уклања све дупликате из листе, задржавајући редослед елемената (задржати само прво појављивање сваког елемента).

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

remdups :: Eq a => [a] -> [a]
remdups = foldr (\ x a -> x : filter (/= x) a) []

Рекурзивне функције са листама¶

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

Чињеница да је листа или празна или је облика glava : rep користи се за дефинисање рекурзивних функција које обрађују листе. Обично се први елемент, тј. глава, обележава са x, а реп листе са xs. Прикажимо неколико примера.

Дефинисати рекурзивну функцију која одређује дужину дате листе.

my_length :: [a] -> Int
my_length [] = 0
my_length (x:xs) = my_length xs + 1

Дужина празне листе је 0, а непразне је за 1 већа од дужине њеног репа. Ако се глава не користи, обичај је да се обележи доњом цртом.

my_length :: [a] -> Int
my_length [] = 0
my_length (_:xs) = my_length xs + 1

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

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

Дефинисати функцију која одређује последњи елемент дате листе.

my_last :: [a] -> a
my_last [x] = x
my_last (_:xs) = my_last xs

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

Дефинисати функцију која испитује да ли дати елемент припада датој листи (аналогно библиотечкој функцији elem).

Ниједан елемент не припада празној листи, а непразној листи припада ако и само ако је или једнак њеној глави или припада њеном репу.

my_elem :: Eq a => a -> [a] -> Bool
my_elem _ [] = False
my_elem y (x:xs) = y == x || my_elem y xs

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

Дефинисати функцију која одређује елемент листе на позицији n (она одговара оператору индексног приступа !!).

Подсетимо се, овим оператором се може прочитати елемент листе са дате позиције (позиције се броје од нуле).

Prelude> [5, 4, 1, 3, 2] !! 2
1

Празна листа нема елемената, нулти елемент непразне листе је њена глава, а n–ти елемент непразне листе је n минус први елемент њеног репа. Дакле, рекурзивна имплементација може бити оваква:

nth_element :: [a] -> Int -> a
nth_element (x:xs) 0 = x
nth_element (_:xs) n = nth_element xs (n-1)

Нагласимо да је сложеност приступа елементу листе увек линеарна (и у нашој имплементацији, али и када се користи оператор !!).

Дефинисати функцију која надовезује две листе (она одговара оператору ++ којим се надовезују две листе).

Prelude> [1, 2, 3] ++ [4, 5]
[1,2,3,4,5]

Наредни код говори више од речи (рекурзија се врши по првој листи):

my_append :: [a] -> [a] -> [a]
my_append [] ys = ys
my_append (x:xs) ys = x : my_append xs ys

Дефинисати функцију која додаје дати елемент на крај дате листе.

У језику Haskell не постоји оператор додавања елемента на крај листе. То није случајно, јер та операција мора бити сложености \(O(n)\). Синтаксички је овај ефекат могуће постићи помоћу оператора надовезивања две листе, али ово не би требало користити, због очигледне неефикасности.

Prelude> [1, 2, 3] ++ [4]
[1,2,3,4]

Ручна имплементација додвања на крај се може урадити на слдећи начин.

my_append :: [a] -> a -> [a]
my_append [] y = [y]
my_append (x:xs) y = x : my_append xs y

Без коришћења уграђених функција имплементирати функцију која обрће листу (чији је ефекат исти као ефекат библиотечке функције reverse).

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

my_reverse :: [a] -> [a]
my_reverse [] = []
my_reverse (x:xs) = my_append (my_reverse xs) x
   where
     my_append :: [a] -> a -> [a]
     my_append [] y = [y]
     my_append (x:xs) y = x : my_append xs y

Ова имплементација обртања је лоша. Наиме, сложеност функције my_append је \(O(n)\), па је сложеност функције my_reverse \(O(n^2)\).

Наредна имплементација обртања је мање јасна од претходне, али је доста боља (њена сложеност је \(O(n)\)).

my_reverse :: [a] -> [a]
my_reverse xs = my_reverse' xs []
   where my_reverse' [] acc = acc
         my_reverse' (x:xs) acc = my_reverse' xs (x:acc)

Основна идеја алгоритма је да се узима један по један елемент са почетка листе и да се додаје на почетак нове, резултујуће листе (коју називамо акумулатор). Улога главне функције my_reverse је само да убаци у игру ту нову листу и да цео посао пребацивања елемената пребаци помоћној функцији my_reverse'. Она ради на следећи начин. Ако је полазна листа празна, тада је коначан резултат оно што се нагомилало у акумулатору. Ако је полазна листа непразна, онда њену главу додајемо на почетак акумултатора и рекурзивно настављамо пребацивање репа на овако проширени акумулатор. За разлику од почетне, ова варијанта је репно рекурзивна, па не постоји опасност од прекорачења стека приликом извршавања ове функције за дугачке листе.

Функција је репно-рекурзивна и лако је приказати њен рад:

my_reverse [1, 2, 3, 4] =
my_reverse' [1, 2, 3, 4] [] =
my_reverse' [2, 3, 4] [1] =
my_reverse' [3, 4] [2, 1] =
my_reverse' [4] [3, 2, 1] =
my_reverse' [] [4, 3, 2, 1] =
[4, 3, 2, 1]

Дефинисати функцију која проверава да ли су две листе једнаке (њен ефекат треба да буде исти као ефекат оператора ==).

Једнакост две листе може да се провери оператором == (наравно, у сложености \(O(n)\)). Вежбе ради, дефинишимо рекурзивну функцију која ово ради. Ако су обе листе празне, оне су једнаке. Ако су обе непразне, једнаке су ако и само ако су им главе и репови једнаки (једнакост репова можемо испитати рекурзивно). У свим другим случајевима листе су различите.

equal :: Eq a => [a] -> [a] -> Bool
equal [] [] = True
equal (x:xs) (y:ys) = x == y && equal xs ys
equal _ _ = False

Приметимо и како смо последњим шаблоном покрили оба случаја када је једна листа празна, а друга непразна.

Прикажимо и како би могли да се имплементирају неки класични алгоритми сортирања листе.

Имплементирати алгоритам сортирања уметањем (енгл. insertion sort).

Дефинисаћемо прво рекурзивну функцију insert која умеће елемент на његово место у сортираној листи, а затим ћемо имплементирати и функцију insertion_sort која сортира листу коришћењем функције insert. Уметањем елемента у празну листу добија се једночлана листа која садржи тај елемент. Уметање у непразну листу зависи од тога да ли је елемент који се умеће мањи од главе листе или није. Ако јесте, нови елемент се поставља на почетак те листе, а ако није, глава се задржава, а нови елемент се рекурзивно умеће у реп листе. Сортирањем празне листе добија се празна листа. Сортирање непразне листе врши се тако што се сортира реп, а затим се глава уметне на своје место у сортираном репу.

insert :: Ord a => a -> [a] -> [a]
insert a [] = [a]
insert a (x:xs)
    | a <= x     = a : x : xs
    | otherwise  = x : insert a xs

insertion_sort :: Ord a => [a] -> [a]
insertion_sort [] = []
insertion_sort (x:xs) = insert x (insertion_sort xs)

Приметимо да смо у описима типова морали да нагласимо да тип елемената листе мора припадати класи типова Ord a, што значи да се елементи типа a могу поредити (операторима <, <=, > и >=).

Сложеност функције insert је линеарна, па је укупна сложеност, очекивано, квадратна.

Наравно, insertion_sort очигледно акумулира резултат додајући један по један елемент функцијом insert па је сасвим природно да она буде имплементирана помоћу fold (а не рекурзивно).

insertion_sort :: Ord a => [a] -> [a]
insertion_sort = foldl insert []

Имплементирати алгоритам сортирања обједињавањем (енгл. merge sort).

Дефинисаћемо три функције. Прва од њих, функција merge обједињава две сортиране листе у трећу, такође сортирану.

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

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
  | x < y      = x : merge xs (y:ys)
  | otherwise  = y : merge (x:xs) ys

Потребна нам је и функција која дели листу на две подлисте једнаке дужине (једна од њих може, евентуално, садржати један елемент више него друга). Ова функција треба да врати две листе. Најједноставније је да то буде у облику уређеног пара. Тип уређеног пара означавамо тако што тип сваког елемента наведемо у загради. На пример, (Int, Int) је уређени пар који чине два податка типа Int. Дефинисаћемо функцију split, која прима листу елемената типа a и враћа уређени пар таквих листа. Имплементираћемо је тако што ће елементе из полазне листе наизменично распоређивати у те две резултујуће листе. Дакле, ако делимо празну листу, резултат ће бити две празне листе. Ако делимо листу која има бар два елемента, рекурзивно ћемо поделити реп листе добијен избацивањем та два елемента, а онда ћемо та два елемента распоредити сваки у по једну од листи добијених из рекурзивног позива. Не смемо још заборавити случај једночлане листе, пошто он није покривен са последња два случаја. У том случају ћемо вратити пар у коме једна листа садржи тај једини елемент, а друга је празна (у зависности да ли тај елемент распоредимо лево или десно, приликом поделе листе са непарним бројем елемената лева или десна листа ће имати један елемент више).

split :: [a] -> ([a], [a])
split [] = ([], [])
split [x] = ([x], [])
split (x1:x2:xs) =
   let (ys, zs) = split xs
    in (x1:ys, x2:zs)

Нагласимо да смо резултат рекурзивног позива прихватили и елементе уређеног пара именовали коришћењем израза let-in.

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

merge_sort :: Ord a => [a] -> [a]
merge_sort [] = []
merge_sort [x] = [x]
merge_sort xs =
   let (ys, zs) = split xs
    in merge (merge_sort ys) (merge_sort zs)

Приметимо да је једини механизам чистог функционалног програмирања редукција израза на основу датих једнакости. Већ смо показали како се на тај начин израчунавају вредности факторијела и НЗД. Ни ова, компликованија имплементација се не разликује.

merge_sort [3, 8, 1, 4, 6, 5, 2, 7] =
let (ys, zs) = split [3, 8, 1, 4, 6, 5, 2, 7]
 in merge (merge_sort ys) (merge_sort zs) =
...
merge (merge_sort [3, 1, 6, 2]) (merge_sort [8, 4, 5, 7]) =
merge (let (ys, zs) = split [3, 1, 6, 2]
        in merge (merge_sort ys) (merge_sort zs))
      (let (ys, zs) = split [8, 4, 5, 7]
        in merge (merge_sort ys) (merge_sort zs)) =
...
merge (merge (merge_sort [3, 6]) (merge_sort [1, 2]))
      (merge (merge_sort [8, 5]) (merge_sort [4, 7])) =
...
merge (merge (merge [3] [6]) (merge [1] [2]))
      (merge (merge [8] [5]) (merge [4] [7])) =
...
merge (merge [3, 6] [1, 2]) (merge [5, 8] [4, 7]) =
...
merge [1, 2, 3, 6] [4, 5, 7, 8] =
...
[1, 2, 3, 4, 5, 6, 7, 8]

При том, није приказано како се корак–по–корак извршавају функције split и merge (то вам остављамо за вежбу).

Сложеност ове функције је \(O(n \log{n})\). Ипак, важна разлика у односу на императивно сортирање низова је то што се у функционалном програмирању листе не могу мењати и уместо измене оригиналне гради се увек нова листа (што може узроковати одређену неефикасност). Додуше, алгоритам сортирања обједињавањем и у императивној имплементацији захтева коришћење помоћног низа.

Имплементирати алгоритам брзог сортирања (енгл. quick sort).

Основна идеја брзог сортирања је да се један елемент листе изабере за тзв. пивотирајући елемент, да се остали елементи листе раздвоје на оне који су мањи од пивота и оне који то нису, да се сваки од та два дела листе рекурзивно сортира и да се резултат добије тако што се пивот уметне између ова два сортирана дела. Та идеја се може веома једноставно изразити у програмском језику Haskell (издвајање делова листе који су мањи од пивота и који нису мањи од пивота се лако може изразити помоћу компрехенсије или филтрирања).

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++
               [x] ++
               qsort [y | y <- xs, y >= x]

Сложеност ове функције је иста као и у императивној имплементацији, међутим, ова имплементација није „у месту“, тј. сортирање се не врши само разменама елемената низа, тако да је ова функционална имплементација мало неефикаснија, али је неупоредиво једноставнија и разумљивија.

Ово је добар тренутак да застанемо и да упоредимо ове имплементације са класичним, императивним. Размотримо прво сортирање уметањем.

static void InsertionSort(int[] a)
{
    for (int i = 1; i < a.Length; i++) {
        int j, tmp = a[i];
        for (j = i; j > 0 && a[j-1] > tmp; j--)
            a[j] = a[j-1];
        a[j] = tmp;
    }
}

Ако упоредимо ово са решењем у језику Haskell, видимо да је приступ потпуно другачији. У решењу у језику Haskell, подсетимо се, оригинална листа се не мења, већ се сортирање врши тако што се гради нова листа.

insertion_sort = foldl insert []
  where
    insert a [] = [a]
    insert a (x:xs)
        | a <= x     = a : x : xs
        | otherwise  = x : insert a xs

Ово можда није подједнако ефикасно као императивно, али је свакако много јасније и разумљивије. Рекурзивна дефиниција функције уметања је веома јасна и заиста је лако имплементирати је. Нема потребе водити рачуна о дужини листе, нити алокацији и деалокацији меморије. Простор за грешку је много мањи него у императивној имплементацији. Захваљујући библиотечкој функцији fold, имплементација „спољне петље” је тривијална и код је јако кратак. Наравно, и у императивном језику је могуће направити имплементацију која би била мање ефикасна, али јаснија, али би свакако било тешко остварити овај ниво једноставности и јасноће имплементације.

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

void Swap(int[] a, int i, int j)
{
   int tmp = a[i];
   a[i] = a[j];
   a[j] = tmp;
}

void QuickSort(int[] a, int l, int d)
{
   if (l >= d)
      return;
   int p = l;
   for (int j = l+1; j <= d; j++)
       if (a[j] < a[l])
          Swap(a, ++p, j);
   Swap(a, l, p);
   QuickSort(a, l, p-1);
   QuickSort(a, p+1, d);
}

void QuickSort(int[] a)
{
    QuickSort(a, 0, a.Length - 1);
}