U L i k o o L matemaatika-informaatikateaduskond

Samuti v˜oime keerulisema argumendi t¨u¨ubi jaoks tulemuse v¨a¨artuse defi-

neerimisel kasutada rekursiivselt lihtsama argumendi t¨u¨ubi jaoks tulemuse

arvutamist. N¨aiteks v˜oime eelnevale lisada

instance C2 a => C2 [a] where

f2 xs = map f2 xs

Siin defineerime funktsiooni listide jaoks, kasutades rekursiivselt selle listi

elementide jaoks defineeritud funktsiooni.

5.3.2

Ad-hoc-pol¨

umorfism tulemuse t¨

u¨

ubi jaoks

Kui me tahame, et ka funktsiooni tulemuse t¨u¨up s˜oltuks argumendi t¨u¨ubist

ad-hoc-pol¨umorfselt, siis Haskell 98-st ei piisa. Sellisel juhul on v˜oimalik ka-

sutada GHC-d, kus on olemas mitme parameetriga t¨u¨ubiklassid ja funktsio-

naalsed s˜oltuvused (selleks tuleb GHC-s sisse l¨ulitada v˜oti -fglasgow-exts).

Sellisel juhul saame kirjutada n¨aiteks funktsiooni, mis t˜oev¨a¨artustele seab

vastavusse t¨aisarvu ja t¨aisarvudele t˜oev¨a¨artuse:

class C3 a b | a -> b where

f3 :: a -> b

instance C3 Bool Integer where

f3 b = bool2int b

instance C3 Integer Bool where

f3 x = int2bool x

5.3.3

Rekursioon tulemuse t¨

u¨

ubi leidmiseks

Proovime n¨u¨ud sarnaselt eespool olnud n¨aitele laiendada selle funktsiooni ka

listide jaoks:

instance C3 a b => C3 [a] [b] where

f3 xs = map f3 xs

Seda GHC vaikimisi ei aktsepteeri, kuna nn Coverage Condition (vt [2], jao-

tis 8.6.3.1) ei kehti. See n˜ouab, et esindajadeklaratsiooni peas (antud juhul

C3 [a] [b]) funktsionaalse s˜oltuvuse tulemust¨u¨up (antud juhul [b]) ei si-

saldaks selliseid t¨u¨ubimuutujaid, mis ei esine selle funktsionaalse s˜oltuvuse

argumentt¨u¨upides (antud juhul [a]). Kuna tulemuses esineb muutuja b, mi-

da argumendis ei esine (seal on ainus muutuja a), siis tingimus ei kehti. See

tingimus t¨ahendab, et ei ole v˜oimalik tulemust¨u¨ubi leidmisel kasutada rekur-

siivselt leitud t¨u¨upi (antud juhul b, mis on C3 poolt rekursiivselt t¨u¨ubile a

vastavusse seatud t¨u¨up), kuna see t¨u¨up on vaja t¨ahistada uue muutujaga,

mida argumentt¨u¨upides ei esine.

33

---

Et sellest tingimusest vabaneda, on GHC-s v˜oimalik sisse l¨ulitada v˜o-

ti -fallow-undecidable-instances. Sellisel juhul GHC aktsepteerib selle

viimati toodud deklaratsiooni. See v˜oti aga muudab v˜oimalikuks ka mitteter-

mineeruvate t¨u¨ubifunktsioonide kirjutamise. N¨aiteks aktsepteerib GHC siis

j¨argmised deklaratsioonid:

class C5 a where

f5 :: a -> Integer

instance C5 [a] => C5 a where

f5 = const 3

Kui n¨u¨ud ¨uritada f5 kasutada, siis l¨aheb t¨u¨ubikontroll l˜opmatusse rekursioo-

ni (reaalselt katkestatakse see teatud s¨ugavusele j˜oudmisel ¨ara).

Eelnevas C3 n¨aites oli tegelikult ainult lihtrekursiooni vaja, mitte ¨uldist

rekursiooni, kuid GHC seda ei v˜oimalda. Fumontrixis kasutatakse t¨u¨ubitase-

mel lihtrekursiooni, mis garanteerib t¨u¨ubikontrolli termineeruvuse. L¨ahemalt

vaatlesime seda jaotises 5.1.3.

5.3.4

Hargnemine t¨

u¨

ubi struktuuri j¨

argi

Vaatleme n¨u¨ud, kuidas kasutada hargnemist t¨u¨ubi struktuuri j¨argi, nn t¨u¨u-

bitaseme case-konstruktsiooni ekvivalenti. Haskellis (GHC-s) tuleb selleks

kirjutada eraldi esindajadeklaratsioon iga argumentt¨u¨ubi variandi jaoks (eel-

nevas C3 n¨aites Bool, Integer, [a]). See on kohmakas ja ebamugav, kuna

klassi nimi tuleb korduvalt v¨alja kirjutada. Fumontrixis on selle asemel ole-

mas t¨u¨ubitaseme case-konstruktsioon (vt jaotist 5.1.1).

Oletame n¨u¨ud, et me soovime kasutada hargnemist mitte argumentt¨u¨ubi,

vaid rekursiivselt arvutatud t¨u¨ubi struktuuri j¨argi. Proovime n¨aiteks kirju-

tada

class C4 a b | a -> b where

f4 :: a -> b

instance C4 Integer Bool where

f4 x = True

instance C4 a Integer => C4 [a] Bool where

f4 x = int2bool (f4 (head x))

instance C4 a Bool => C4 [a] Integer where

f4 x = bool2int (f4 (head x))

Siin me soovime, et kui t¨u¨upi a v¨a¨artusele seatakse vastavusse t¨aisarv, siis

t¨u¨upi [a] v¨a¨artusele seataks vastavusse t˜oev¨a¨artus ning vastupidi, kui re-

kursiivselt arvutati v¨alja t˜oev¨a¨artus, siis tulemuseks oleks t¨aisarv. Seda aga

34

---

GHC ei aktsepteeri, kuna C4 [a] jaoks on mitu deklaratsiooni ning GHC

seda ei luba, isegi kui kontekstid on mittel˜oikuvad, nagu on praegusel juhul.

Selle asemel tuleb hargnemise jaoks defineerida eraldi t¨u¨ubiklass:

class C4a a b | a -> b where

f4a :: a -> b

instance C4a Bool Integer where

f4a b = bool2int b

instance C4a Integer Bool where

f4a x = int2bool x

Siis saab C4 defineerida j¨argmiselt:

class C4 a b | a -> b where

f4 :: a -> b

instance C4 Integer Bool where

f4 x = True

instance (C4 a b, C4a b c) => C4 [a] c where

f4 x = f4a (f4 (head x))

N¨aeme, et GHC-s on t¨u¨ubitaseme funktsioonid ¨uhetasemelised, iga alam-

ploki jaoks tuleb defineerida eraldi t¨u¨ubitaseme funktsioon ning need funkt-

sioonid peavad k˜oik olema peataseme skoobis. See on kohmakas ja muudab

koodi v¨aga hakituks, samuti peab programmeerija k˜oigile neile funktsioo-

nidele nimed v¨alja m˜otlema ja meelde j¨atma. Fumontrixis on t¨u¨ubitaseme

funktsioone v˜oimalik defineerida suvalises alamskoobis, ¨uksteise sees saab

kasutada kui tahes palju t¨u¨ubitaseme case-konstruktsioone ja rekursiivseid

v¨aljakutseid ning samuti saab kasutada anon¨u¨umseid t¨u¨ubitaseme funktsioo-

ne (ka rekursiivseid), et programmeerija ei peaks igale funktsioonile nime

v¨alja m˜otlema.

Fumontrixis saab selle C4 n¨aite kirjutada j¨argmiselt:

type tf4 = \ v : @ .

value

(type

(\ t rec @ .

case t of

Int

->

value const True $: t;

List a ->

case typeof type rec a of

(_ -> Bool) ->

value const 3 $: t;

35

---