Nii tfSum kui tfProd on rekursiivsed oma teise argumendi suhtes. Lihtrekur-
siivse t¨u¨ubitaseme funktsiooni defineerimiseks kasutatakse v˜otmes˜ona rec
λ-abstraktsiooni p¨aises. Sama v˜otmes˜ona kasutatakse ka rekursiivse funkt-
siooni kehas selle funktsiooni rekursiivselt arvutatud v¨a¨artuse kasutamiseks
(toodud n¨aites rec b’ leiab funktsiooni v¨a¨artuse argumendil b’).
Viimases n¨aites oli rekursiivse t¨u¨ubitaseme funktsiooni tagastusv¨a¨artus
liiki *. Kui tagastusv¨a¨artus on mingit teist liiki, siis tuleb see liik λ-abstrakt-
siooni p¨aises m¨arkida, et hiljem rekursiivselt arvutatud v¨a¨artuse kasutamisel
(rec-konstruktsiooniga) oleks selle liik teada (kuna Fumontrixis liigiinferentsi
ei toimu). N¨aiteks
type typeNatToValue = \ a rec @ .
case a of
Zero
-> value 0;
Succ b -> value 1 + (type rec b);
end;
See funktsioon teisendab t¨u¨ubitaseme t¨aisarvu andmetaseme t¨aisarvu kujule.
Kuna tulemus on liiki @, siis on see λ-abstraktsiooni p¨aises m¨argitud.
Vaatleme veel, kuidas kahekordset lihtrekursiooni kasutada. Defineerime
n¨aiteks t¨u¨ubitaseme funktsiooni, mis arvutab m-korda-n-elemendilise korru-
tustabeli elementide summa, simuleerides rekursioonidega ts¨ukleid ¨ule natu-
raalarvude:
type tfProdSum = \ m . \ n .
(\ a rec:outer * -> * . \ b rec .
case b of
Zero
->
case a of
Zero
->
Zero;
Succ a’ ->
rec:outer a’ n;
end;
Succ b’ ->
rec b’ ‘tfSum‘ (a ‘tfProd‘ b);
end
) m n;
Siin on v¨alise rekursiooni jaoks lisatud v˜otmes˜onale rec kooloniga identi-
fikaator outer. Seda kooloniga notatsiooni kasutatakse nii rekursiivse λ-
abstraktsiooni p¨aises kui selle rekursiooni poolt eelnevalt arvutatud v¨a¨artuste
27
kasutamisel. Sisemise rekursiooni jaoks ei ole vaja identifikaatorit kasutada,
kuna tavaline rec viitab k˜oige sisemisele ilma nimeta rekursioonile, mis on
antud skoobis k¨attesaadav. (Seega v˜oib ka sisemisele rekursioonile nime anda
ja v¨alimise nimeta j¨atta.)
Fumontrixis saab lihtrekursiooni kasutada ka ¨ule keerulisemat liiki t¨u¨upi-
de. Defineerime n¨aiteks unaarsed t¨u¨ubitaseme naturaalarvud, millel on lisaks
¨uks ¨uleliigne argument. Neid saab kasutada n¨aiteks ¨uhikuga suuruste jaoks.
See ¨uleliigne argument on siis suuruse v¨a¨artus ning unaarne t¨u¨ubitaseme na-
turaalarv v¨aljendab suuruse ¨uhikut: null — dimensioonita suurus, ¨uks —
meeter, kaks — ruutmeeter jne. Suuruse ¨uhik on siis t¨u¨ubitasemel staatiliselt
teada, erinevalt selle v¨a¨artusest, mis leitakse d¨unaamiliselt.
data FZero B = FZero B;
data FSucc (A : * -> *) B = FSucc B;
type tfFSum = \ a : * -> * . \ b : * -> * rec * -> * .
case b of
FZero
-> a;
FSucc b’ -> FSucc (rec b’);
end;
Siis saab kasutada n¨aiteks avaldist
FSucc 3 $: (tfFSum (FSucc FZero) (FSucc (FSucc (FSucc FZero)))),
mis defineerib viienda astme (siin on viis FSucc konstruktorit) ¨uhikuga suu-
ruse, mille v¨a¨artus on 3.
Fumontrixis funktsionaalset liiki t¨u¨ubin¨aidiste kasutamisel tuleb arvesta-
da, et siin ei kehti ekstensionaalsuse printsiip. Ekstensionaalsuse korral keh-
tiks samav¨a¨arsus λx.f x ≡ f, st funktsiooni semantika oleks m¨a¨aratud tema
v¨a¨artustega k˜oigil v˜oimalikel argumentidel. See muudab ebapraktiliseks (l˜op-
liku, kuid suure m¨a¨aramispiirkonna korral) v˜oi mittelahenduvaks (l˜opmatu
m¨a¨aramispiirkonna korral) funktsioonide v˜ordsuse kontrollimise. Seet˜ottu on
t¨u¨ubitasemel funktsionaalsete n¨aidiste kasutamiseks Fumontrixis t¨u¨ubitase-
mel ekstensionaalsusest loobutud. Seega funktsioonid FZero ja
\ x . FZero x on erinevad (kuigi ekstensionaalselt v˜ordsed) ning esimene
neist sobitub n¨aidisega FZero, kuid teine mitte. Fumontrixi andmetasemel
siiski ekstensionaalsus kehtib.
Ka GHC-s ei kehti t¨u¨ubitasemel ekstensionaalsus. Nimelt t¨u¨ubis¨unon¨u¨u-
me ei saa defineerida t¨u¨ubiklassi elementideks. N¨aiteks
class C (a :: * -> *)
28
type F = Either Int
type G a = Either Int a
--instance C G -- ei ole lubatud
instance C F
-- on lubatud
Siin t¨u¨ubifunktsioonid F ja G on ekstensionaalselt v˜ordsed, kuna F a ja G a
on iga a korral v˜ordsed (m˜olemad on Either Int a). Samas esindajadekla-
ratsioonis on F lubatud, aga G keelatud.
5.2
M˜
oningaid t¨
u¨
ubitaseme funktsioonide rakendusi
5.2.1
T¨
u¨
ubitaseme funktsioonid ja ad-hoc-pol¨
umorfism
¨
Uks t¨u¨ubitaseme funktsioonide rakendus on ad-hoc-pol¨umorfsete funktsioo-
nide realiseerimine. Ad-hoc-pol¨umorfset funktsiooni saab rakendada erinevat
t¨u¨upi argumentidele ja erinevate t¨u¨upide korral v˜oib funktsioon k¨aituda eri-
nevalt. Sellisel juhul v˜oib kirjutada t¨u¨ubitaseme funktsiooni, mis seab vaa-
deldava funktsiooni igale lubatud argumendi t¨u¨ubile vastavusse monomorfse
funktsiooni, mis ootab argumendiks seda t¨u¨upi v¨a¨artust. N¨aiteks Javas v˜oime
defineerida ad-hoc-pol¨umorfse funktsiooni f:
boolean f(int x) {
return x != 0;
}
int f(boolean x) {
return x ? 1 : 0;
}
Siis saame kasutada avaldisi nagu f(2) ja f(true). Siin on kummagi luba-
tud argumendit¨u¨ubi (int ja boolean) jaoks defineeritud eraldi monomorfne
funktsioon ning need definitsioonid kokku annavad ad-hoc-pol¨umorfse funkt-
siooni. Siin on iga argumendi t¨u¨ubi jaoks vaja anda eraldi definitsioon ja
koodi lugeja peab k˜oik skoobis olevad definitsioonid l¨abi vaatama, et kogu
pol¨umorfse funktsiooni definitsioon k¨atte saada.
Fumontrixis defineeritakse t¨u¨ubitaseme funktsioon ¨uhe definitsiooniga:
type f = \ x : @ .
case typeof type x of
Int ->
value (type x) != 0;
Bool ->
value if (type x) 1 0;
end;
29