U L i k o o L matemaatika-informaatikateaduskond



Yüklə 0,53 Mb.

səhifə8/23
tarix13.11.2017
ölçüsü0,53 Mb.
1   ...   4   5   6   7   8   9   10   11   ...   23

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



oningaid t¨



ubitaseme funktsioonide rakendusi

5.2.1





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





Dostları ilə paylaş:
1   ...   4   5   6   7   8   9   10   11   ...   23


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2019
rəhbərliyinə müraciət

    Ana səhifə