U L i k o o L matemaatika-informaatikateaduskond

[2], jaotis 8.4.4).

23

---

5

T¨

u¨

ubitaseme programmeerimine

5.1

T¨

u¨

ubitaseme funktsioonid Fumontrixis

5.1.1

T¨

u¨

ubitaseme funktsioonid

Vaatleme n¨u¨ud, millised on t¨u¨ubitaseme funktsioonide kasutamise v˜oimalu-

sed Fumontrixis. Erinevalt Haskellist, kus keerulisemaid t¨u¨ubitaseme funkt-

sioone tuleb defineerida t¨u¨ubiklasside kaudu loogilise programmeerimise stii-

lis implikatsioonidena ([2], jaotis 8.6.3, k¨aesolevas t¨o¨os vaatleme neid l¨ahe-

malt jaotises 5.3), on Fumontrixis t¨u¨ubitaseme funktsioonide defineerimiseks

eraldi konstruktsioonid ja neid saab defineerida funktsionaalse programmee-

rimise stiilis λ-abstraktsioonina nagu andmetaseme funktsioonegi.

Defineerime n¨aiteks t¨u¨ubitaseme funktsiooni, mis seab t˜oev¨a¨artust¨u¨ubile

vastavusse t¨aisarvut¨u¨ubi, t¨aisarvut¨u¨ubile t˜oev¨a¨artust¨u¨ubi ning k˜oigile teiste-

le t¨u¨upidele ¨uhikt¨u¨ubi:

type tf11 = \ a .

case a of

Bool -> Int;

Int -> Bool;

_

-> Unit;

end;

N¨aeme, et t¨u¨ubitaseme funktsioone defineeritakse λ-abstraktsiooniga na-

gu andmetaseme funktsioonegi ning t¨u¨ubitasemel saab t¨u¨upide sisse vaada-

ta case-konstruktsiooniga sarnaselt andmetasemega. case-konstruktsioon ei

pea katma k˜oiki v˜oimalusi — kui eelmisest definitsioonist viimane valikual-

ternatiiv ¨ara j¨atta, siis tuleks funktsiooni tf11 rakendamisel mingile muule

t¨u¨ubile kui Bool v˜oi Int t¨u¨ubiviga, nagu andmetasemel tuleb analoogilisel

juhul ⊥.

Samuti n¨aeme, et t¨u¨ubitaseme funktsioonile nime andmiseks saab kasu-

tada type-deklaratsiooni. Seda saab kasutada ka muude t¨u¨ubitaseme objek-

tide (t¨u¨upide, v¨a¨artuste jne), mitte ainult funktsioonide jaoks. Antud juhul

oli tegemist k˜oige lihtsama t¨u¨ubitaseme funktsiooniga (liiki * -> *), mis tei-

sendab tavalise t¨u¨ubi (liiki *) tavaliseks t¨u¨ubiks.

Fumontrixis saab defineerida ka keerulisemaid t¨u¨ubitaseme funktsioone,

n¨aiteks liiki * -> * -> *, (* -> *) -> * v˜oi ((* -> *) -> *) -> * -> *.

Erinevalt Haskelli t¨u¨ubiklassidega defineeritud t¨u¨ubitaseme funktsiooni-

dest saab Fumontrixi t¨u¨ubitaseme funktsioone kasutada ka t¨u¨ubiannotatsioo-

nides. N¨aiteks:

f13 = \ x : tf11 Bool . x + 3;

24

---

Siin on annotatsioonis kasutatud Int asemel tf11 Bool.

5.1.2

V¨

a¨

artustega arvutamine t¨

u¨

ubitasemel

T¨u¨ubitasemel saab arvutada lisaks t¨u¨upidele ka v¨a¨artustega, t¨u¨ubitaseme

v¨a¨artuse liik on @. Seega on kasutatavad ka t¨u¨ubitaseme funktsioonid liiki

@ -> @ (sarnaneb andmetaseme funktsioonidega), * -> @ jne.

Defineerime n¨aiteks t¨aisarvu ruudu arvutamise funktsiooni:

type tf12 = \ a : @ .

value (type a) * (type a);

Siin tuleb m¨a¨arata argumendi a liik @, kuna vaikimisi on liigiks *. Argumendi

t¨u¨upi ei ole t¨u¨ubitaseme funktsiooni korral vaja m¨a¨arata, see funktsioon on

kasutatav k˜oikide t¨u¨upide v¨a¨artuste jaoks, mille korral ei tule funktsiooni

kehas t¨u¨ubiviga, ehk antud juhul ainult t¨aisarvude jaoks, kuna korrutustehe

on defineeritud ainult t¨aisarvude jaoks (ujukomaarve Fumontrixis ei ole).

Siin kasutatakse ka v˜otmes˜onu type ja value, mis on vajalikud t¨u¨ubi-

taseme ja andmetaseme vahel liikumiseks. Need konstruktsioonid ulatuvad

s¨untaktiliselt nii kaugele paremale kui v˜oimalik (nagu let-konstruktsiooni

v˜otmes˜ona in j¨arel olev osa).

V˜otmes˜ona type muudab t¨u¨ubitaseme v¨a¨artuse (liiki @) andmetaseme

v¨a¨artuseks, mida saab n¨aiteks anda argumendiks andmetaseme funktsioonile

(kui see v¨a¨artus on ˜oiget t¨u¨upi). Viimases n¨aites * on andmetaseme funkt-

sioon, kuid a on t¨u¨ubitaseme v¨a¨artus, seega lihtsalt a * a ei saa kirjutada.

V˜otmes˜ona value muudab andmetaseme v¨a¨artuse t¨u¨ubitaseme v¨a¨artu-

seks (liiki @). Viimases n¨aites on see vajalik, kuna t¨u¨ubitaseme funktsioon

saab tagastada ainult t¨u¨ubitaseme v¨a¨artust (v˜oi muud t¨u¨ubitaseme objekti),

aga mitte andmetaseme v¨a¨artust.

Erinevalt Haskellist on Fumontrixis olemas ka v˜otmes˜ona typeof, mis

v˜oimaldab kasutada avaldise t¨u¨upi ja sellega arvutada ning n¨aiteks annotat-

sioonides kasutada. N¨aiteks

type argtype = \ a : @ .

case typeof type a of (arg -> res) -> arg end;

f14 = \ x : argtype (value (+)) . x + x;

Siin defineerime k˜oigepealt funktsiooni argtype, mis leiab monomorfse and-

metaseme funktsiooni argumendi t¨u¨ubi. Kasutades seda funktsiooni, saame

funktsiooni f14 argumendi t¨u¨ubi m¨a¨arata selles kasutatava funktsiooni (+)

argumendi t¨u¨ubi p˜ohjal nagu t¨u¨ubiinferentsi korral. Praegusel juhul on k¨ull

lihtsam argumendi t¨u¨up Int v¨alja kirjutada, aga keerulisema t¨u¨ubi korral

v˜oib argtype olla mugavam kasutada.

25

---

5.1.3

T¨

u¨

ubitaseme lihtrekursiivsed funktsioonid

Fumontrixis on v˜oimalik t¨u¨ubitasemel defineerida ka rekursiivseid funktsioo-

ne. Erinevalt GHC-st, kus vajaliku laienduse sissel¨ulitamisel on v˜oimalik kir-

jutada funktsioone, mis l¨ahevad l˜opmatusse rekursiooni (vt jaotist 5.3.3),

on Fumontrixis t¨u¨ubitasemel kasutatav ainult lihtrekursioon ¨ule t¨u¨upide (nii

lihtsate kui ka keerulisemat liiki t¨u¨upide). See garanteerib t¨u¨ubikontrolli ter-

mineeruvuse, samas lihtrekursioonist peaks piisama enamiku kasulike t¨u¨ubi-

taseme funktsioonide realiseerimiseks.

Lihtrekursioon t¨ahendab, et funktsiooni v¨a¨artuse arvutamiseks mingil ar-

gumendil v˜oib selle sama funktsiooni (rekursiivselt arvutatud) v¨a¨artusi kasu-

tada ainult selle argumendi komponentide (vahetute v˜oi mitte) jaoks. N¨aiteks

funktsiooni arvutamiseks argumendil

List (Tuple3 (Pair Int Bool) Unit Int)

v˜oib kasutada selle sama funktsiooni v¨a¨artusi argumentidel

Tuple3 (Pair Int Bool) Unit Int

Pair Int Bool

Unit

Int

Bool

Defineerime n¨aiteks t¨u¨ubitaseme unaarsed naturaalarvud ning liitmise ja

korrutamise nendel:

data Zero;

data Succ A;

type tfSum = \ a . \ b rec .

case b of

Zero

-> a;

Succ b’ -> Succ (rec b’);

end;

type tfProd = \ a . \ b rec .

case b of

Zero

-> Zero;

Succ b’ -> tfSum (rec b’) a;

end;

26

---