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