U L i k o o L matemaatika-informaatikateaduskond

M a -> M b

a

M b

f (return x)

M (M a -> b)

a

M b

f ‘ap‘ return (return x)

M (M a -> M b) a

M b

join (f ‘ap‘ return (return x))

M a -> b

M a

b

f x

M a -> M b

M a

M b

f x

M (M a -> b)

M a

M b

f ‘ap‘ return x

M (M a -> M b) M a

M b

join (f ‘ap‘ return x)

Selles tabelis on kirjas, kuidas nendel juhtudel GHC standardfunktsioonide

abil funktsiooni rakendada. Nende 16 juhu jaoks tuleb kokku kasutada 10

erinevat funktsiooni rakendamise operaatorit. Et nende kasutamine oleks v¨a-

hem kohmakas, v˜oime defineerida need 10 infiksoperaatorit (m˜oned on juba

standardfunktsioonidena olemas), n¨aiteks:

f

x

f x

infiksoperaator

-----------------------------------------------

a -> b

a

b

$

a -> M b

a

M b

$

M (a -> b)

a

M b

%=

M (a -> M b)

a

M b

=%<<=

a -> b

M a

M b

=%

a -> M b

M a

M b

=<<

M (a -> b)

M a

M b

%%

M (a -> M b)

M a

M b

=%<<

M a -> b

a

b

$=

M a -> M b

a

M b

$=

M (M a -> b)

a

M b

%==

M (M a -> M b) a

M b

=%<<==

M a -> b

M a

b

$

M a -> M b

M a

M b

$

M (M a -> b)

M a

M b

%=

M (M a -> M b) M a

M b

=%<<=

Lisaks tavalisele funktsiooni rakendamisele on vaja ka infiksoperaatoreid

kasutada. Neid v˜oib muidugi tavaliste funktsioonidena (prefikskujul) kasuta-

da, kuid see on ebamugav. Seega on vaja veel v¨ahemalt ¨uhte operaatorit (kui

infiksoperaatori t¨u¨up v˜oib ka monaadi sisaldada, siis on rohkem operaatoreid

vaja):

($%) :: forall a b (m :: * -> *).

(Monad m) => m a -> (a -> b) -> m b

($%) = flip liftM

51

---

Vaatleme n¨u¨ud j¨argmist imperatiivset algoritmi (j¨arjestamise kiirmeetod

ehk Quicksort):

void qs(int[] a, int l, int r) {

if r-l <= 1 then

return;

else {

void swap(int u, int v) {

int t = a[u];

a[u] = a[v];

a[v] = t;

}

int x = a[l];

int j = l+1;

int i = j;

while i < r {

if a[i] < x {

swap(i, j);

j = j+1;

}

i += 1;

}

swap(j-1, l);

qs(a, l, j-1);

qs(a, j, r);

}

}

Imperatiivne kiirmeetod sorteerib massiivi in-place, s.t kasutades ainult kons-

tantset hulka lisam¨alu lisaks sorteeritavale massiivile. See on vajalik n¨aiteks

sellisel juhul, kui sorteeritav massiiv asub v¨alisel andmekandjal (nt k˜ovakettal

v˜oi v˜orgus) ning on nii suur, et m¨allu ei mahu. Funktsionaalselt realiseeritud

kiirmeetodit ei saaks sellisel juhul kasutada, kuna seal on vaja pidevalt uusi

liste moodustada, mille maht rekursiooni ¨ulemisel tasemel on sorteeritava

massiiviga samas suurusj¨argus.

Haskellis v˜oib selle algoritmi eespool defineeritud infiksoperaatorite abil

kirjutada nii:

qs :: STArray s Int Int -> Int -> Int -> ST s ()

qs a l r =

if r-l <= 1 then

return ()

52

---

else do

let al = writeArray a

let ar = readArray a

let

swap u v = do

t <- ar u

al u =<< ar v

al v $ t

x <- ar l

(jl,jr) <- makeSTRef (l+1)

(il,ir) <- makeSTRef =<< jr

while (ir $% (<) %= r) $ do

when =% ((ar =<< ir) $% (<) %= x) =%<<= do

swap =% ir =%<< jr

jl =<< jr $% (+) %= 1

il =<< (+1) =% ir

swap =% (jr $% (-) %= 1) =%<<= l

qs a l =<< (jr $% (-) %= 1)

qs a =% jr =%<<= r

Siin makeSTRef tekitavad uue viida ning tagastab selle viida vasaku ja parema

semantika. Analoogiliselt saaks massiivi defineerimiseks kasutada funktsioo-

ni makeSTArray, mis tagastab selle massiivi vasaku ja parema semantika.

Siin on massiiv a juba eelnevalt konstrueeritud, funktsioonis defineeritakse

vaid selle vasak ja parem semantika (al ja ar). Funktsioon while on intui-

tiivse semantikaga. N¨aeme, et antud koodis on vaja funktsiooni rakendamise

jaoks kasutada 7 erinevat operaatorit ($% %= $ =% =%<< =<< =%<<=). See

on v¨aga ebamugav, programmeerija peab pidevalt m˜otlema, millist operaa-

torit kasutada, ning infiksoperaatorite prioriteedid l¨ahevad kaduma. Samuti

on kood halvasti loetav (kuigi seda annab parandada, kui lasta tekstiredak-

toril s¨untaks v¨arvida nii, et need operaatorid oleks raskesti n¨ahtavad, n¨aiteks

tumehall mustal taustal).

Fumontrixis on tavaline funktsiooni rakendamise operaator ($ v˜oi j¨ar-

jest kirjutamine) ¨ule laaditud ja kasutatav k˜oigil 16 juhul (eeldusel, et ST-

konstruktori monaadina k¨asitlemine on sisse l¨ulitatud). Seega viimase n¨aite

v˜oime kirjutada j¨argmiselt:

rec qs : forall S. stArray S Int -> Int -> Int -> ST S Unit =

forall S. \ a @ Pair al ar : stArray S Int .

\ l : Int . \ r : Int .

mif $: (ST S) (r-l <= 1)

Unit

53

---

do

. swap = \ u : Int . \ v : Int . do

. t <- ar u;

al u $ ar v;

al v $ t;

end;

. x <- ar l;

. Pair jl jr <- makeSTRef $: S (l+1);

. Pair il ir <- makeSTRef $: S jr;

while (ir < r) do

when (ar ir < x) do

swap ir jr;

jl $ jr+1;

end;

il $ (+1) ir;

end;

swap (jr-1) l;

qs a l (jr-1);

qs a jr r;

end;

Siin on funktsiooni rakendamise operaatori korral sisuliselt tegemist ad-hoc-

pol¨umorfismiga ja seda saaks ka t¨u¨ubitaseme funktsioonidega realiseerida,

kuid siis tuleks iga monaadikonstruktori jaoks operaatori k¨aitumine eraldi

defineerida, kuna Fumontrix ei toeta geneerilist programmeerimist.

6.5.2

do-notatsioon

Haskellis on imperatiivse programmeerimisstiili mugavamaks kasutamiseks

olemas do-notatsioon ([1], jaotis 3.14), mis on defineeritud monaadioperat-

sioonide >>= ja fail kaudu. Kuna Fumontrixis on funktsiooni rakendamise

operaator eelmises jaotises kirjeldatud viisil ¨ule laaditud, siis on v˜oimalik

do-avaldised defineerida funktsiooni rakendamise operaatori, mitte otse mo-

naadioperatsioonide kaudu.

Fumontrixis on do-avaldis defineeritud s¨untaktilise suhkruna j¨argmiselt:

54

---