U L i k o o L matemaatika-informaatikateaduskond

Keerulisemat liiki t¨u¨ubitaseme funktsioone ei saa GHC t¨u¨ubiklasside abil

¨uldse defineerida, kuna t¨u¨ubitaseme funktsioone ei saa t¨u¨ubiklasside argu-

mendina kasutada. Erinevalt Fumontrixist ei ole GHC t¨u¨ubitaseme funkt-

sioonid t¨u¨ubitasemel first-class. Seega ei saa defineerida selliseid kasulikke

operaatoreid nagu jaotises 5.1.2 defineeritud argtype ning erinevad funkt-

siooni rakendamise operaatorid nagu jaotises 6.4.2 defineeritav applyImpred

impredikatiivseks funktsiooni rakendamiseks.

Samuti ei ole GHC-s typeof-operaatorit ning t¨u¨ubiklasside abil definee-

ritud t¨u¨ubitaseme funktsioonidega arvutatud t¨u¨upe ei saa annotatsioonides

kasutada.

GHC-s on olemas ka t¨u¨ubis¨unon¨u¨umid, mis v˜oivad ka keerulisemat liiki ol-

la, kuid nende abil on v˜oimalik ainult oma argumendi suhtes parameetriliselt

pol¨umorfseid funktsioone kirjutada, argumendi struktuuri j¨argi hargnemist

kasutada ei saa.

Nii t¨u¨ubis¨unon¨u¨ume kui t¨u¨ubiklasse ja esindajaid saab GHC-s defineerida

ainult peataseme skoobis, mis suurendab koodi hakitust. Fumontrixis saab

t¨u¨ubitaseme funktsioone defineerida suvalises skoobis.

39

---

6

Pol¨

umorfism

6.1

¨

Uldiselt pol¨

umorfismist

Pol¨umorfism v˜oimaldab kasutada sama nime mitme sarnase t¨ahendusega

(kuid erinevat t¨u¨upi) v¨a¨artuse jaoks. See v¨ahendab programmeerija jaoks

nimede v¨aljam˜otlemise ja pikkade nimede kirjutamise vaeva ning muudab

koodi l¨uhemaks.

Pol¨umorfismi on mitut liiki. Funktsionaalsetes keeltes laialt levinud para-

meetriline pol¨umorfism v˜oimaldab kasutada sama koodi (funktsiooni definit-

siooni) erinevat t¨u¨upi argumentide jaoks. See v¨ahendab vajadust sama koodi

mitmesse kohta kopeerimiseks.

Ad-hoc-pol¨umorfism v˜oimaldab defineerida funktsioone, mis on kasuta-

tavad erinevat t¨u¨upi argumentide jaoks ning nende erinevate t¨u¨upide jaoks

rakendatakse erinevat koodi. Sisuliselt on tegemist mitme sama nimega funkt-

siooniga, millest translaator valib t¨u¨ubikontrolli k¨aigus argumendi t¨u¨ubi p˜oh-

jal ˜oige.

6.2

Pol¨

umorfism ja t¨

u¨

ubitaseme funktsioonid

Fumontrixis on pol¨umorfismi v˜oimalik realiseerida ka t¨u¨ubitaseme funktsioo-

nide abil. Liiki @ -> @ t¨u¨ubitaseme funktsiooni saab kasutada sarnaselt and-

metaseme funktsiooniga (kuigi s¨untaks on natuke kohmakam). T¨u¨ubitaseme

funktsiooni korral ei ole argumendi t¨u¨upi ilmutatult deklareeritud, see on

m¨a¨aratud ilmutamata kujul sellega, millistes kontekstides seda argumenti

funktsiooni kehas kasutatakse.

T¨u¨ubitaseme funktsiooni tulemuse t¨u¨up v˜oib s˜oltuda argumendi t¨u¨ubist

suvalise lihtrekursiivse funktsioonina kvantoriteta t¨u¨upidel (kuna kvantori-

tega t¨u¨upide sisse ei v˜oimalda Fumontrixi t¨u¨ubitaseme case-konstruktsioon

vaadata). Seega t¨u¨ubitaseme funktsioon v¨a¨artustel v˜oib olla suvaline osali-

selt rekursiivne funktsioon v¨a¨artustel (mille t¨u¨up ei sisalda kvantoreid), mis

sama t¨u¨upi v¨a¨artustele seab alati vastavusse sama t¨u¨upi tulemuse ning mille

poolt m¨a¨aratud funktsioon t¨u¨upidel on lihtrekursiivne.

Siin tuleb t¨u¨upide hulka lugeda ka nn ⊥-t¨u¨up ehk t¨u¨ubiviga. T¨u¨ubita-

seme funktsioonid on t¨u¨upide suhtes agara semantikaga, seega t¨u¨ubiviga ei

saa esineda t¨u¨ubikonstruktori argumendina ning andes t¨u¨ubivea argumendiks

t¨u¨ubitaseme funktsioonile, on tulemuseks ikka sama t¨u¨ubiviga.

T¨u¨ubitaseme funktsioonid liiki @ -> @ v˜otavad argumendiks ja annavad

tulemuseks andmetaseme v¨a¨artusi. Kui me soovime t¨u¨ubitaseme funktsiooni

argumendi v˜oi tulemusena kasutada teisi t¨u¨ubitaseme funktsioone, siis tuleb

kasutada k˜orgemat liiki (n¨aiteks (@ -> @ -> @) -> @ -> @) t¨u¨ubitaseme

40

---

funktsioone. Ka nendel on olemas ilmutamata t¨u¨up, mis s˜oltub sellest, mil-

listes kontekstides argumenti kasutatakse.

Kui t¨u¨ubitaseme funktsioonina saab defineerida praktiliselt k˜oiki pol¨u-

morfseid funktsioone, siis milleks on andmetaseme pol¨umorfseid funktsioone

vaja?

T¨u¨ubitaseme funktsioone ei saa hoida andmetaseme andmestruktuuride

sees, selleks tuleks kasutada t¨u¨ubitaseme andmestruktuure. Fumontrixis saab

algebraliste andmet¨u¨upide konstruktoritele argumendiks anda ainult t¨u¨upe

ja t¨u¨ubikonstruktoreid, mitte suvalisi t¨u¨ubitaseme funktsioone. See on vaja-

lik t¨u¨ubikontrolli lahenduvuse s¨ailitamiseks. Vastasel korral saaks kirjutada

n¨aiteks j¨argmised definitsioonid:

data Dt21 (A : * -> *);

type tf21 = \ pf .

case pf of

Dt21 tf21’ -> tf21’ pf;

end;

Siin defineerime uue t¨u¨ubikonstruktori, mis saades argumendi liiki * -> *,

konstrueerib uue t¨u¨ubi liiki *. Seej¨arel defineerime funktsiooni tf21, mis on

liiki * -> *. Konstruktori Dt21 abil saame selle funktsiooni pakkida tavali-

seks liiki * t¨u¨ubiks, mille saame anda argumendiks sellele samale funktsiooni-

le, mis pakib selle lahti, saades k¨atte iseenda koopia, mille kutsub rekursiiv-

selt v¨alja. Tekib l˜opmatu rekursioon. Kuna Fumontrixis oli eesm¨ark s¨ailitada

t¨u¨ubikontrolli lahenduvus, siis tuli vaadeldav kitsendus sisse viia.

¨

Uks olukord, kus veel andmetaseme pol¨umorfseid funktsioone vaja l¨aheb,

on siis, kui me soovime kirjutada pol¨umorfset funktsiooni, mis t¨o¨otaks ka

selliste t¨u¨upide korral, mida selle funktsiooni defineerimise hetkel veel ei ek-

sisteeri ning mille k¨aitumine nende t¨u¨upide jaoks ei ole samuti veel t¨apselt

teada. Jaotises 6.3 vaatleme, kuidas sellisel juhul pol¨umorfismi kasutada.

Samuti l¨aheb andmetaseme pol¨umorfseid funktsioone vaja juhul, kui me

soovime anda pol¨umorfset v¨a¨artust argumendiks (pol¨umorfsele v˜oi mono-

morfsele) funktsioonile, mis ootab monomorfset v¨a¨artust. Seda olukorda vaat-

leme jaotises 6.4.

6.3

Pol¨

umorfism ja d¨

unaamilise skoopimise elemendid

6.3.1

Veel ¨

uks pol¨

umorfismi liik

Nii parameetrilise kui ad-hoc-pol¨umorfismi korral on argumendiks sobivate

argumentide hulk funktsiooni definitsiooniga fikseeritud (parameetrilise po-

l¨umorfismi korral kuuluvad sinna ka need t¨u¨ubid, kus parameetriks on mingi

41

---