Oh-jel-moin-ti-kiel-ten eh-dot-to-mas-ti tärkeim-mät ra-ken-teet o-vat tois-to-ra-ken-teet. Ne sal-li-vat teh-dä oh-jel-mi-a, jot-ka käsit-te-le-vät suu-ren, mah-dol-li-ses-ti en-nal-ta määräämättömän määrän tie-to-a. Tois-to-ra-ken-tei-den käyt-töä kut-su-taan y-lei-ses-ti re-pe-ti-ti-ok-si. Re-pe-ti-ti-o ja-kau-tuu (jos-kaan ei tyh-jen-ty-västi) kah-teen päätyyp-piin: i-te-raa-ti-oon ja re-kur-si-oon.
I-te-raa-ti-o on y-lei-ses-ti käy-tössä ns. im-pe-ra-tii-vi-sis-sa oh-jel-moin-ti-kie-lis-sä, joi-ta o-vat kaik-ki y-lei-sim-mässä käy-tössä o-le-vat kie-let, ku-ten C, Ja-va, C++ ja skrip-ti-kie-let. I-te-raa-ti-os-sa tiet-ty-jä oh-jei-ta/toi-mi-a tois-te-taan, kun-nes jo-kin eh-to täyt-tyy. E-si-mer-kik-si tau-lu-kon si-sällön voi tu-los-taa käyt-tämällä in-dek-si-muut-tu-jaa, jo-ka o-soit-taa vuo-ro-tel-len ku-hun-kin tau-lu-kon jäse-neen ja jon-ka kas-va-es-sa tau-lu-kon koon y-li lo-pe-te-taan:
(de-fi-ne (disp-lay-vec-tor v)
(do ((in-dex 0 (+ in-dex 1)))
((>= in-dex (vec-tor-length v)))
(disp-lay (vec-tor-ref v in-dex))
(new-li-ne)))
Funk-ti-o-naa-li-sis-sa kie-lis-sä, joi-hin Lisp-per-heet kie-let jok-seen-kin kuu-lu-vat, käy-te-tään kui-ten-kin u-sein re-kur-si-o-ta. Re-kur-sii-vi-set al-go-rit-mit (= funk-ti-ot) o-vat e-ri-tyi-sen luon-nol-li-nen rat-kai-su re-kur-sii-vis-ten tie-to-ra-ken-tei-den käsit-te-lyyn. Funk-ti-on re-kur-sii-vi-suus tar-koit-taa, et-tä funk-ti-on x määrit-te-lys-sä käy-te-tään a-pu-na funk-ti-o-ta x it-se-ään. Tie-to-ra-ken-teen re-kur-sii-vi-suus taas tar-koit-taa, et-tä tie-to-ra-ken-ne voi si-sältää o-sa-naan sa-man-lai-si-a tie-to-ra-ken-tei-ta. Seu-raa-vas-sa py-rin an-ta-maan e-si-merk-ke-jä näis-tä.
Var-maan-kin yk-sin-ker-tai-sin e-si-merk-ki re-kur-sii-vi-ses-ta tie-to-ra-ken-tees-ta on Lisp-per-heen kiel-ten o-min tie-to-ra-ken-ne, lis-ta. Lis-ta on jo-ko tyh-jä, tai sit-ten se koos-tuu kah-des-ta a-si-as-ta, ni-mit-täin en-sim-mäi-ses-tä e-le-men-tis-tään ja toi-ses-ta lis-tas-ta, jos-sa o-vat lo-put e-le-men-tit. Kos-ka lis-tan määrit-te-lyyn kuu-luu tällä ta-voin, et-tä sii-hen si-sältyy toi-nen lis-ta, on lis-ta tie-to-ra-ken-tee-na re-kur-sii-vi-nen. Kos-ka lis-ta on re-kur-sii-vi-nen, myös sen läpi-käyn-ti on hel-poin-ta määrit-tää re-kur-sii-vi-sel-la al-go-rit-mil-la:
(de-fi-ne (disp-lay-list ls)
(cond ((null? ls) #f)
(el-se (disp-lay (car ls))
(new-li-ne)
(disp-lay-list (cdr ls)))))
(cond on y-leis-tet-ty if
: sii-nä voi ol-la mie-lin määrin eh-to-ja,
joi-ta tes-ta-taan en-sim-mäi-ses-tä vii-mei-seen, kun-nes jo-kin eh-to täyt-tyy, ja
eh-don täyt-ty-es-sä voi suo-rit-taa u-se-am-pi-a ko-men-to-ja. Tässä käy-te-tään
cond:a, kos-ka el-se-lau-sek-kees-sa on kol-me ko-men-to-a.)
Re-kur-sii-vi-nen määrit-te-ly seu-raa luon-nos-taan tie-to-ra-ken-teen
määrit-te-lys-tä. Tie-to-ra-ken-teen e-ri "muo-to-ja"[1] — joi-ta lis-tal-la
on kak-si: se on jo-ko tyh-jä tai sit-ten koos-tuu en-sim-mäi-ses-tä e-le-men-tis-tä
ja lo-puis-ta — vas-taa-vat eh-to-lau-sek-keen (e-sim. if tai cond) e-ri haa-rat.
Pe-rus-muo-to-ja
e-li nii-tä muo-to-ja, jot-ka ei-vät si-sällä re-kur-sii-vi-si-a
o-si-a — lis-to-jen ta-pauk-ses-sa tyh-ji-ä lis-to-ja — vas-taa jo-kin
yk-sin-ker-tai-nen o-pe-raa-ti-o, e-sim. yl-lä vain pa-lau-te-taan #f.
Yh-dis-tel-mämuo-to-ja
e-li muo-to-ja, jois-sa on re-kur-sii-vi-si-a o-si-a, vas-taa
jo-kin pro-ses-soin-ti, jon-ka o-sa-na käy-te-tään re-kur-sii-vis-ta kut-su-a
tie-to-ra-ken-teen re-kur-sii-vi-sen o-san käsit-te-le-mi-sek-si; e-sim. yl-lä
disp-lay-list tu-los-taa lis-tan en-sim-mäi-sen e-le-men-tin se-kä ri-vin-vaih-don
ja kut-suu it-se-ään re-kur-sii-vi-ses-ti lop-pu-lis-tan käsit-te-le-mi-sek-si.
[1] näi-tä kut-su-taan
a-si-an-har-ras-ta-jien kes-kuu-des-sa tie-to-muo-dos-ti-mik-si
Toi-nen tyy-pil-li-nen e-si-merk-ki re-kur-sii-vi-ses-ta tie-to-ra-ken-tees-ta on syn-tak-si-puu. Käy-tämme e-si-merk-ki-nä syn-tak-si-puu-ta, jol-la on kak-si muo-dos-tin-ta: jo-ko puus-sa on vain yk-si sa-na (pe-rus-muo-to) tai sit-ten se koos-tuu kah-des-ta puus-ta, jois-ta toi-nen toi-mii määree-nä toi-sel-le (yh-dis-tel-mämuo-to). Li-säksi jo-kai-ses-sa puun sol-mus-sa (= haa-rau-ma tai leh-ti) on ta-gi, jo-ka ker-too, on-ko ky-sei-nen sol-mu ver-bi-lau-se-ke, no-mi-ni-lau-se-ke, ad-ver-bi tms.
Yk-si-sa-nai-sen puun voi e-sit-tää lis-ta-na, jos-sa on en-sin ta-gi ja sit-ten
ky-sei-nen sa-na (merk-ki-jo-no-na), e-si-mer-kik-si (v juok-see
).
Yh-dis-tel-mäpuun voi e-sit-tää lis-ta-na, jos-sa on en-sin ta-gi, sit-ten määre-puu
ja vii-mei-se-nä pääpuu, e-si-mer-kik-si (vp (n poi-ka
) (v juok-see
)).
Määri-tämme myös ka-san a-pu-funk-ti-oi-ta näi-den pui-den käsit-te-le-mi-seen:
(Tässä käy-te-tään uut-ta tie-to-tyyp-pi-ä, sym-bo-li-a, ta-gi-na. Sym-bo-li-va-ki-on voi kir-joit-taa pa-ne-mal-la sym-bo-lin e-teen heit-to-mer-kin. Oi-ke-as-taan ai-no-a, mi-tä sym-bo-leil-la voi teh-dä, on ver-ra-ta nii-tä toi-siin-sa. Sik-si ne o-vat lois-ta-vi-a ta-ge-ja. Sym-bo-leil-le on myös taat-tu-a, et-tä eq? ja eqv? toi-mi-vat (toi-sin kuin merk-ki-jo-noil-le). Li-säksi yl-lä käy-te-tään ra-ken-net-ta let, jol-la voi määrit-tää väli-ai-kais-muut-tu-ji-a, se-kä funk-ti-o-ta (cadr s) = (car (cdr s)) ja funk-ti-o-ta (caddr s) = (car (cdr (cdr s))).)
(de-fi-ne (ma-ke-word tag word) (list tag word))
(de-fi-ne (ma-ke-noun word) (ma-ke-word 'n word))
(de-fi-ne (ma-ke-verb word) (ma-ke-word 'v word))
(de-fi-ne (ma-ke-ad-verb word) (ma-ke-word 'adv word))
(de-fi-ne (ma-ke-ad-jec-ti-ve word) (ma-ke-word 'adj word))
(de-fi-ne (ma-ke-phra-se tag mo-dif he-ad) (list tag mo-dif he-ad))
(de-fi-ne (ma-ke-noun-phra-se mo-dif he-ad) (ma-ke-phra-se 'np mo-dif he-ad))
(de-fi-ne (ma-ke-verb-phra-se mo-dif he-ad) (ma-ke-phra-se 'vp mo-dif he-ad))
(de-fi-ne (syn-tax-tag s) (car s))
(de-fi-ne (syn-tax-phra-se? s)
(let ((tag (syn-tax-tag s)))
(or (eqv? tag 'np) (eqv? tag 'vp))))
(de-fi-ne (syn-tax-word? s) (not (syn-tax-phra-se? s)))
(de-fi-ne (syn-tax-mo-dif s)
(if (syn-tax-phra-se? s) (cadr s) #f))
(de-fi-ne (syn-tax-he-ad s)
(if (syn-tax-phra-se? s) (caddr s) #f))
(de-fi-ne (syn-tax-word s)
(if (syn-tax-word? s) (cadr s) #f))
Kat-so-kaam-me nyt, mil-tä näyt-tää re-kur-sii-vi-nen funk-ti-o e-sim. syn-tak-si-puun subs-tan-tii-vien (noun) las-ke-mi-seen:
(de-fi-ne (syn-tax-count-nouns s)
(if (syn-tax-word? s)
(if (eqv? (syn-tax-tag s) 'n) 1 0)
(+ (syn-tax-count-nouns (syn-tax-mo-dif s))
(syn-tax-count-nouns (syn-tax-he-ad s)))))
Yl-lä jälleen re-kur-sii-vi-nen määrit-te-ly lähtee sii-tä, et-tä tes-ta-taan, on-ko ky-sees-sä pe-rus-ta-paus e-li on-ko syn-tak-si-puu yk-si-sa-nai-nen. Jos on, las-ke-taan sen subs-tan-tii-vit hy-vin yk-sin-ker-tai-sel-la o-pe-raa-ti-ol-la: jos sa-na o-li subs-tan-tii-vi ('n), sii-nä on yk-si subs-tan-tii-vi; jos sa-na o-li jo-kin muu, sii-nä on nol-la subs-tan-tii-vi-a. Yh-dis-tel-mäpuul-le taas las-ke-taan määre-puun ja pääpuun subs-tan-tii-vi-määrät yh-teen. Ai-ka help-po-a, ei-kö? Ko-keil-laan-pa jo-tain muu-ta. Mi-ten puus-ta sai-si ai-kai-sek-si merk-ki-jo-non, jos-sa o-vat kaik-ki puun sa-nat?
(de-fi-ne (syn-tax->string s)
(if (syn-tax-word? s)
(syn-tax-word s)
(string-ap-pend (syn-tax->string (syn-tax-mo-dif s)) " "
(syn-tax->string (syn-tax-he-ad s)))))
Ko-vas-ti sa-man-lai-sel-ta näyt-tää. Pe-rus-ta-pauk-ses-sa, yk-si-sa-nai-ses-sa puus-sa, vain nos-te-taan ky-sei-nen sa-na e-siin. Yh-dis-tel-mäta-pauk-ses-sa lii-te-tään yh-teen määre-puu-ta vas-taa-va merk-ki-jo-no, väli-lyönti, ja pääpuu-ta vas-taa-va merk-ki-jo-no.
Eh-kä o-li-si ai-ka teh-dä jo-tain vai-ke-am-paa. Mi-ten sai-sim-me ai-kaan funk-ti-on, jo-ka kor-vaa syn-tak-si-puus-ta ver-bin jol-lain toi-sel-la sa-nal-la? Kat-so-taan-pa.
(de-fi-ne (syn-tax-rep-la-ce-verb s new-verb)
(ca-se (syn-tax-tag s)
((n adj adv np) s)
((v) (ma-ke-verb new-verb))
((vp) (ma-ke-verb-phra-se
(syn-tax-mo-dif s)
(syn-tax-rep-la-ce-verb (syn-tax-he-ad s) new-verb)))))
(ca-se on myös tie-tyn-lai-nen eh-to-lau-se-ke. Se ver-taa en-sim-mäis-tä ar-gu-ment-ti-aan (yl-lä (syn-tax-tag s)) e-ri-lai-siin ar-voi-hin.)
Tällä ker-taa pe-rus-ta-pauk-si-a on kak-si. Subs-tan-tii-vit, ad-jek-tii-vit, ad-ver-bit ja no-mi-ni-lau-sek-keet ei-vät voi si-sältää ver-be-jä, jo-ten niil-le on tur-ha teh-dä mi-tään. Oh-jel-ma pa-laut-taa-kin syn-tak-si-puun sel-lai-se-naan tässä ta-pauk-ses-sa. Sen si-jaan ver-bi ni-me-no-maan pi-ti kor-va-ta toi-sel-la, ja sen tähden pa-lau-te-taan uu-si (yk-si-sa-nai-nen) puu, jos-sa on uu-si ver-bi. Re-kur-si-o-ta-paus syn-tyy vain ver-bi-lau-sek-kees-ta. Tällöin muo-dos-te-taan uu-si ver-bi-lau-se-ke, jos-sa määre on sa-ma kuin en-ti-ses-säkin mut-ta pääpuus-ta on ver-bi kor-vat-tu uu-del-la (re-kur-sii-vi-nen kut-su).
Tar-kas-tel-laan vie-lä yh-tä sa-man-lais-ta o-pe-raa-ti-o-ta, ni-mit-täin sa-nan x kor-vaa-mis-ta y:llä syn-tak-si-puus-ta. Se käy näin:
(de-fi-ne (syn-tax-rep-la-ce-words s old-word new-word)
(if (syn-tax-word? s)
(if (string=? (syn-tax-word s) old-word)
(ma-ke-word (syn-tax-tag s) new-word)
s)
(ma-ke-phra-se (syn-tax-tag s)
(syn-tax-rep-la-ce-words (syn-tax-mo-dif s) old-word new-word)
(syn-tax-rep-la-ce-words (syn-tax-he-ad s) old-word new-word))))
Tässäkin on kak-si pe-rus-ta-paus-ta: yk-si-sa-nai-nen puu jo-ko on tai ei o-le se sa-na, jon-ka ha-lu-am-me kor-va-ta. Jos se on, pa-lau-tam-me uu-den yk-si-sa-nai-sen puun (ta-gi tu-lee en-ti-sen pe-rus-teel-la). Jos ei, pa-lau-tam-me puun muu-tok-sit-ta. Re-kur-si-o-ta-pauk-ses-sa muo-dos-tam-me uu-den puun en-ti-sen ta-gis-ta se-kä en-ti-sen määre- ja pääpuis-ta si-ten, et-tä niis-tä on re-kur-sii-vi-ses-ti kor-vat-tu sa-nat toi-sil-la.
Re-kur-sii-vi-sis-sa määrit-te-lyis-sä on se (e-ri-no-mai-nen) puo-li, et-tä ne o-vat ns. app-li-ka-tii-vi-si-a o-pe-raa-ti-oi-ta e-li ne ei-vät muu-ta ar-gu-men-tik-si saa-mi-aan tie-to-ra-ken-tei-ta vaan pa-laut-ta-vat vain uu-si-a.[2]
[2] Tästä syys-tä on
tur-val-lis-ta käyt-tää yh-tä syn-tak-si-puu-ta u-se-an muun o-sa-na — on taat-tu-a,
et-tä ky-sei-nen puu py-syy ai-na si-sällöltään sa-ma-na.
Pa-lat-kaam-me vie-lä het-kek-si lis-toi-hin. Yl-lä muo-dos-tet-tiin syn-tak-si-puis-ta uu-si-a pui-ta si-ten, et-tä re-kur-sii-vis-ten puun-käsit-te-ly-kut-su-jen tu-lok-set koot-tiin uu-dek-si puuk-si ma-ke-verb-phra-se:lla ja ma-ke-phra-se:lla. Sa-ma on-nis-tuu tie-ten-kin lis-to-jen-kin suh-teen. Lis-to-ja koo-taan muo-dos-ti-mel-la cons. E-si-mer-kik-si, jos ha-lu-ai-sim-me ker-to-a kaik-ki lis-tan lu-vut kah-del-la, voi-sim-me kir-joit-taa tällai-sen määrit-te-lyn:
(de-fi-ne (list-doub-le ls)
(if (null? ls) '()
(cons (* 2 (car ls)) (list-doub-le (cdr ls)))))
Pe-rus-ta-paus on jälleen tyh-jä lis-ta. Tyh-jän lis-tan lu-vut ker-rot-tu-na kah-del-la on uu-si tyh-jä lis-ta; ei-tyh-jän lis-tan lu-vut ker-rot-tu-na kah-del-la on uu-si lis-ta, jos-sa on en-sin van-han lis-tan en-sim-mäi-nen lu-ku ker-rot-tu-na kah-del-la ja sit-ten lop-pu-lis-tan lu-vut ker-rot-tui-na kah-del-la (re-kur-sii-vi-nen kut-su). Tämä ru-tii-ni on sen ver-ran yk-sin-ker-tai-nen, et-tä voi-sim-me kat-so-a, kuin-ka se toi-mii. Al-la e-si-te-tään ri-vi ri-vil-tä, kuin-ka las-ken-ta e-te-nee.
(list-doub-le '(1 3 5)) -> (cons (* 2 1) (list-doub-le '(3 5))) -> (cons 2 (list-doub-le '(3 5))) -> (cons 2 (cons (* 2 3) (list-doub-le '(5)))) -> (cons 2 (cons 6 (list-doub-le '(5)))) -> (cons 2 (cons 6 (cons (* 2 5) (list-doub-le '())))) -> (cons 2 (cons 6 (cons 10 (list-doub-le '())))) -> (cons 2 (cons 6 (cons 10 '()))) -> (cons 2 (cons 6 '(10))) -> (cons 2 '(6 10)) -> '(2 6 10)
Lis-to-jen läpi-käy-mi-seen e-si-tel-lään tuon-nem-pa-na muu-ta-mi-a a-pu-kei-no-ja, jot-ka o-vat jos-kus (e-sim. tässä ta-pauk-ses-sa) näppärämpi-ä kuin re-kur-sii-vi-sen ru-tii-nin kir-joit-ta-mi-nen.
E-del-li-ses-sä pa-neu-dut-tiin en-si-si-jai-ses-ti ns. struk-tu-raa-li-seen re-kur-si-oon e-li tie-to-ra-ken-teen ra-ken-tee-seen pe-rus-tu-vaan re-kur-si-oon. Re-kur-si-o on kui-ten-kin e-rit-täin y-leis-päte-vä tek-niik-ka, jol-la pys-tyy hel-pos-ti ku-vaa-maan min-kä ta-han-sa i-te-ra-tii-vi-sen me-ne-tel-män. Re-kur-si-o-ta, jo-ka ei pe-rus-tu niin-kään tie-to-ra-ken-teen o-mi-nai-suuk-siin vaan jo-hon-kin so-pi-vas-ti va-lit-tui-hin lo-pe-tu-seh-toi-hin ja ar-gu-ment-tien vaih-dok-siin, sa-no-taan ge-ne-ra-tii-vi-sek-si. Ot-ta-kaam-me e-si-mer-kik-si a-lus-sa käsi-tel-ty tau-lu-kon (i-te-ra-tii-vi-nen) läpi-käyn-ti in-dek-si-muut-tu-jal-la. Jos ha-lu-am-me ol-la oi-kein pe-rus-teel-li-si-a, sen tois-toon pe-rus-tu-va ver-si-o näyt-tää tältä:
(de-fi-ne (disp-lay-vec-tor v)
(let ((in-dex 0))
(do () ((>= in-dex (vec-tor-length v)))
(disp-lay (vec-tor-ref v in-dex))
(new-li-ne)
(set! in-dex (+ in-dex 1)))))
Y-lei-nen tyy-li näis-sä tois-tois-sa on seu-raa-va: tois-te-taan, kun-nes tiet-ty eh-to täyt-tyy; jo-ka tois-tol-la teh-dään tiet-ty-jä a-si-oi-ta ja päi-vi-te-tään muu-ta-mi-a ti-la-muut-tu-ji-a, jot-ka ker-to-vat, mis-sä men-nään (ku-ten in-dex yl-lä); sit-ten tes-ta-taan eh-to-a taas. Jo-kai-sen tällai-sen tois-ton voi muut-taa re-kur-sii-vi-sek-si määrit-te-lyk-si hel-pos-ti ja suo-ra-vii-vai-ses-ti muut-ta-mal-la tois-to-ra-ken-teen funk-ti-ok-si, ti-la-muut-tu-jat funk-ti-on ar-gu-men-teik-si ja ti-la-muut-tu-jien päi-vit-tämi-sen uu-sien ar-gu-ment-ti-ar-vo-jen las-ke-mi-sek-si. E-si-mer-kik-si näin:
(de-fi-ne (disp-lay-vec-tor-from v in-dex)
(cond ((>= in-dex (vec-tor-length v)) #f)
(el-se (disp-lay (vec-tor-ref v in-dex))
(new-li-ne)
(disp-lay-vec-tor-from v (+ in-dex 1)))))
(de-fi-ne (disp-lay-vec-tor v)
(disp-lay-vec-tor-from v 0))
Toi-se-na e-si-merk-ki-nä voi-si toi-mi-a tau-lu-kon sum-ma. Tyy-pil-li-nen i-te-ra-tii-vi-nen rat-kai-su näyt-tää tältä:
(de-fi-ne (vec-tor-sum v)
(let ((in-dex 0) (sum 0))
(do () ((>= in-dex (vec-tor-length v)))
(set! sum (+ sum (vec-tor-ref v in-dex)))
(set! in-dex (+ in-dex 1)))
sum))
Re-kur-sii-vi-ses-sa rat-kai-sus-sa se-kä sum et-tä in-dex muut-tu-vat ar-gu-men-teik-si, kos-ka nii-den ar-vo-a päi-vi-te-tään jo-ka tois-tol-la:
(de-fi-ne (vec-tor-sum-hel-per v in-dex sum)
(cond ((>= in-dex (vec-tor-length v)) sum)
(el-se (vec-tor-sum-hel-per v (+ in-dex 1) (+ sum (vec-tor-ref v in-dex))))))
(de-fi-ne (vec-tor-sum v)
(vec-tor-sum-hel-per v 0 0))
Huo-maa, et-tä toi-sin kuin disp-lay-vec-tor, vec-tor-sum pa-laut-taa jo-tain: tau-lu-kon sum-man. I-te-ra-tii-vi-ses-sa ver-si-os-sa pa-lau-tet-ta-va ar-vo on funk-ti-on lo-pus-sa, kun do-sil-muk-ka on suo-ri-tet-tu lop-puun. Re-kur-sii-vi-ses-sa ver-si-os-sa se on pe-rus-ta-pauk-sen (in-dex suu-rem-pi kuin tau-lu-kon pi-tuus) ar-vo.
Tällai-sel-la tek-nii-kal-la voi hel-pos-ti määrit-tää myös lis-tan kääntävän funk-ti-on (siis en-sim-mäi-nen e-le-ment-ti vii-mei-sek-si ja päin vas-toin):
(de-fi-ne (list-re-ver-se-hel-per ls re-sult)
(cond ((null? ls) re-sult)
(el-se (list-re-ver-se-hel-per (cdr ls) (cons (car ls) re-sult)))))
(de-fi-ne (list-re-ver-se ls)
(list-re-ver-se-hel-per ls '()))
list-re-ver-se-hel-per liit-tää lis-tan ls e-le-ment-te-jä yk-si ker-ral-laan re-sult-lis-taan, kun-nes ei o-le e-nää mi-tään lii-tet-tävää. Tällöin re-sult pa-lau-te-taan lop-pu-tu-lok-se-na.
Jo-ki-ki-nen tässä jak-sos-sa e-si-merk-ki-nä ol-lut re-kur-sii-vi-nen määrit-te-ly
koos-tuu kah-des-ta funk-ti-os-ta: var-si-nai-sen re-kur-si-on te-ke-västä
a-pu-funk-ti-os-ta ja wrap-per
-funk-ti-os-ta, jo-ka an-taa var-si-nai-sen työn
te-ke-vän funk-ti-on ar-gu-men-teil-le oi-ke-at al-ku-ar-vot. Kos-ka tällai-nen
ra-ken-ne on e-rit-täin y-lei-nen, sche-mes-sä on tyy-li-käs ni-met-ty
let
-ra-ken-ne. Se sal-lii määrit-tää a-pu-funk-ti-on ja sa-mal-la määrit-tää
sen ar-gu-ment-tien al-ku-ar-vot. E-si-mer-kik-si yl-lä o-le-vat re-kur-sii-vi-set
määrit-te-lyt näyt-täi-si-vät sen a-vul-la seu-raa-vil-ta:
(de-fi-ne (disp-lay-vec-tor v)
(let loop ((in-dex 0))
(cond ((>= in-dex (vec-tor-length v)) #f)
(el-se (disp-lay (vec-tor-ref v in-dex))
(new-li-ne)
(loop (+ in-dex 1))))))
(de-fi-ne (vec-tor-sum v)
(let loop ((in-dex 0) (sum 0))
(if (>= in-dex (vec-tor-length v)) sum
(loop (+ in-dex 1) (+ sum (vec-tor-ref v in-dex))))))
(de-fi-ne (list-re-ver-se ls)
(let loop ((re-mai-ning ls) (re-sult '()))
(if (null? re-mai-ning) re-sult
(loop (cdr re-mai-ning) (cons (car re-mai-ning) re-sult)))))
Jo-kai-ses-sa yl-lä o-le-vis-ta e-si-mer-keis-tä a-pu-funk-ti-on ni-mi on loop, mut-ta se voi ol-la ai-van hy-vin jo-tain muu-ta-kin, mah-dol-li-ses-ti ku-vaa-vam-paa. Tällä ta-voin teh-dyt määri-tel-mät o-vat u-sein hy-vin y-ti-mek-käi-tä, jo-pa pe-lot-ta-van tii-vii-tä. Huo-lel-li-sel-la lu-ke-mi-sel-la ne kum-min-kin sel-vi-ävät.
Yh-te-nä e-si-merk-ki-nä ge-ne-ra-tii-vi-ses-ta re-kur-si-os-ta voi-si ot-taa funk-ti-on i-o-ta, jo-ka pa-laut-taa kaik-ki nu-me-rot nol-las-ta n:ään. Tässä yh-dis-tämme ni-me-tyn let:n käy-tön ja lis-to-jen ra-ken-ta-mi-sen re-kur-sii-vi-ses-ti. An-nan en-sin kah-ta funk-ti-o-ta käyt-tävän määri-tel-män, sit-ten vas-taa-van ni-met-ty-ä let:a käyt-tävän määri-tel-män:
(de-fi-ne (num-bers from to)
(if (>= from to) '()
(cons from (num-bers (+ from 1) to))))
(de-fi-ne (i-o-ta n)
(num-bers 0 n))
(de-fi-ne (i-o-ta n)
(let num-bers ((cur-rent 0))
(if (>= cur-rent n) '()
(cons cur-rent (num-bers (+ cur-rent 1))))))
Vie-lä yk-si e-si-merk-ki ge-ne-ra-tii-vi-ses-ta re-kur-si-os-ta voi-si ol-la puh-taas-ti
nu-mee-ri-set al-go-rit-mit. Näis-sä pe-rus-ta-paus on u-sein nol-la tai jo-kin muu
pe-rus-nu-me-ro
, joi-ta re-kur-sii-vi-set kut-sut lähes-ty-vät. E-si-mer-kis-tä
käy-köön Fi-bo-nac-cin sar-jan n. lu-ku. En-sin kah-den funk-ti-on
määri-tel-mä, sit-ten let-poh-jai-nen:
(de-fi-ne (fi-bo-nac-ci-hel-per n x1 x2)
(if (= n 0) x1
(fi-bo-nac-ci-hel-per (- n 1) (+ x1 x2) x1)))
(de-fi-ne (fi-bo-nac-ci n)
(fi-bo-nac-ci-hel-per n 1 0))
(de-fi-ne (fi-bo-nac-ci n)
(let loop ((i-te-ra-ti-ons n) (x1 1) (x2 0))
(if (= i-te-ra-ti-ons 0) x1
(loop (- i-te-ra-ti-ons 1) (+ x1 x2) x1))))
Tie-tyt ta-vat käsi-tel-lä tie-to-ra-ken-tei-ta o-vat y-lei-sem-pi-ä kuin toi-set. E-si-mer-kik-si lis-toil-le on e-rit-täin tyy-pil-lis-tä käy-dä se läpi, teh-dä jo-tain jo-kai-sel-le sen e-le-men-til-le, ja pa-laut-taa uu-si lis-ta näi-den o-pe-raa-ti-oi-den tu-lok-sis-ta. Al-ku-puo-lel-la käsit-te-le-mämme lu-ku-lis-tan e-le-ment-tien tup-laa-mi-nen on e-si-merk-ki tällai-ses-ta o-pe-raa-ti-os-ta.
Funk-ti-o-naa-li-sis-sa oh-jel-moin-ti-kie-lis-sä on mah-dol-lis-ta määri-tel-lä
funk-ti-oi-ta, jot-ka aut-ta-vat tällai-sis-sa y-lei-sis-sä tie-to-ra-ken-tei-den
käsit-te-ly-ta-vois-sa. Näi-tä kut-su-taan tut-ta-val-li-ses-ti
i-te-raat-to-reik-si,
ja pe-rin-tei-nen e-si-merk-ki niis-tä on map, jo-ka ni-me-no-maan käy lis-tan
läpi, te-kee jon-kin o-pe-raa-ti-on sen e-le-men-teil-le ja pa-laut-taa uu-den lis-tan
tu-lok-sis-ta. I-te-raat-to-rei-ta on hel-pom-pi ym-märtää käy-tännön e-si-merk-kien
kuin määrit-te-lyn kaut-ta. E-si-mer-kik-si lis-tan-tup-laus-funk-ti-on voi-si
määrit-tää näin:
(de-fi-ne (doub-le x) (* 2 x)) (de-fi-ne (list-doub-le ls) (map doub-le ls))
map ot-taa siis kak-si ar-gu-ment-ti-a: en-sin-näkin funk-ti-on, jo-ta so-vel-le-taan ku-hun-kin lis-tan e-le-ment-tiin vuo-rol-laan; toi-sek-seen lis-tan, jon-ka e-le-ment-tei-hin si-tä so-vel-le-taan. map pa-laut-taa lis-tan, jo-ka koos-tuu ar-gu-ment-ti-funk-ti-on pa-laut-ta-mis-ta ar-vois-ta.
O-te-taan toi-sek-si e-si-mer-kik-si hy-vin sa-man-lai-nen toi-men-pi-de: lis-tan jo-kai-sen lu-vun ko-rot-ta-mi-nen toi-seen po-tens-siin. An-nan en-sin re-kur-sii-vi-sen määri-tel-män ja sit-ten i-te-raat-to-ri-määri-tel-män:
(de-fi-ne (squ-a-re x) (* x x))
(de-fi-ne (list-squ-a-re ls)
(if (null? ls) '()
(cons (squ-a-re (car ls)) (list-squ-a-re (cdr ls)))))
(de-fi-ne (list-squ-a-re ls)
(map squ-a-re ls))
Jos taas an-nan map:lle funk-ti-on e-ven?, saan lis-tan sii-tä, mi-kä nu-me-ro o-li pa-ril-li-nen ja mi-kä ei:
(map e-ven? '(1 2 3 5 8)) => '(#f #t #f #f #t)
Toi-nen, vähän käy-tännönlähei-sem-pi e-si-merk-ki on merk-ki-jo-non muut-ta-mi-nen pie-nik-si kir-jai-mik-si. Sche-mes-sä on si-säänra-ken-net-tu funk-ti-o char-down-ca-se, jo-ka toi-mii vain mer-keil-le. Mut-ta jos merk-ki-jo-non muut-taa merk-kien lis-tak-si, voim-me käyt-tää map:a, ja tu-los-lis-tan voi muut-taa ta-kai-sin merk-ki-jo-nok-si:
(de-fi-ne (string-down-ca-se str) (list->string (map char-down-ca-se (string->list str)))) (string-down-ca-se "HeLL!o") => "hell!o"
Map-funk-ti-os-sa muu-ten ei o-le mi-tään maa-gis-ta. Sen pys-tyy hel-pos-ti määrit-te-le-mään it-se-kin. Tätä määri-tel-mää ei tar-vit-se ym-märtää, mut-ta sen huo-lel-li-nen poh-dis-ke-lu saat-taa nos-taa kor-ke-am-mal-le tie-toi-suu-den ta-sol-le (tai sit-ten ei):
(de-fi-ne (map o-pe-ra-ti-on ls)
(if (null? ls) '()
(cons (o-pe-ra-ti-on (car ls)) (map o-pe-ra-ti-on (cdr ls)))))
Toi-nen tyy-pil-li-nen i-te-raat-to-ri on fil-ter. Se ot-taa kak-si ar-gu-ment-ti-a: funk-ti-on, jo-ka pa-laut-taa to-tuu-sar-von, ja lis-tan. Se käy lis-tan läpi ja muo-dos-taa uu-den lis-tan, jos-sa o-vat al-ku-pe-räi-ses-tä lis-tas-ta vain ne e-le-men-tit, joil-le ar-gu-ment-ti-funk-ti-o pa-laut-taa to-den. E-si-mer-kik-si:
(fil-ter e-ven? '(1 2 3 5 8)) =>
'(2 8)
(fil-ter string? '(1 3 "foo" #\o "bar")) =>
'("foo" "bar")
Kai-kis-sa Sche-meis-sä ei o-le fil-ter-funk-ti-o-ta si-säänra-ken-net-tu-na. Se on to-ki help-po määri-tel-lä. Tämänkin määri-tel-män tui-jot-ta-mi-nen saat-taa nos-taa tie-toi-suu-den ta-so-a:
(de-fi-ne (fil-ter ta-ke? ls)
(if (null? ls) '()
(if (ta-ke? (car ls))
(cons (car ls) (fil-ter ta-ke? (cdr ls)))
(fil-ter ta-ke? (cdr ls)))))
Jos-kus on mah-dol-lis-ta määri-tel-lä jos-sain mie-les-sä al-le-go-ri-si-a i-te-raat-to-rei-ta muil-le-kin tie-to-ra-ken-teil-le kuin lis-toil-le. E-si-mer-kik-si syn-tak-si-puil-le voi-sim-me määrit-tää syn-tax-map-funk-ti-on, jo-ka ot-taa funk-ti-on ja syn-tak-si-puun ja pa-laut-taa uu-den syn-tak-si-puun, jos-sa jo-kai-nen sa-na on pro-ses-soi-tu ar-gu-ment-ti-funk-ti-on läpi. Tämän a-vul-la voi-sim-me teh-dä e-sim. sa-maa kuin syn-tax-rep-la-ce-words-funk-ti-ol-la:
(de-fi-ne (syn-tax-map op s)
(if (syn-tax-word? s)
(ma-ke-word (syn-tax-tag s) (op (syn-tax-word s)))
(ma-ke-phra-se (syn-tax-tag s)
(syn-tax-map op (syn-tax-mo-dif s))
(syn-tax-map op (syn-tax-he-ad s)))))
(de-fi-ne (rep-la-ce-foo-with-bar word)
(if (string=? word "foo") "bar" word))
(de-fi-ne (syn-tax-rep-la-ce-foo-with-bar s)
(syn-tax-map rep-la-ce-foo-with-bar s))
Voi-sim-me hel-pos-ti myös jat-kaa pie-nik-si kir-jai-mik-si muun-ta-mi-sen vim-maam-me:
(de-fi-ne (syn-tax-down-ca-se s) (syn-tax-map string-down-ca-se s))
Yl-lä list-doub-le- ja list-squ-a-re-e-si-mer-keis-sä määri-tim-me a-pu-funk-ti-ot doub-le ja squ-a-re, kos-ka i-te-raat-to-reil-le pi-tää an-taa funk-ti-o ar-gu-ment-ti-na. Sa-moin syn-tax-rep-la-ce-foo-with-bar käyt-tää (ty-pe-rää) a-pu-funk-ti-o-ta rep-la-ce-foo-with-bar. I-te-raat-to-rien kans-sa tu-lee u-sein tar-ve muo-dos-taa pie-ni-ä a-pu-funk-ti-oi-ta len-nos-sa. On-nek-si Sche-mes-sä on kei-no muo-dos-taa ni-met-tömi-ä funk-ti-oi-ta. lamb-da-o-pe-raa-ti-o (ni-mi on his-to-ri-al-li-nen jäänne) pa-laut-taa funk-ti-on, jo-ka ot-taa tie-tyt ar-gu-men-tit ja pa-laut-taa tie-tyn ar-von. E-si-mer-kik-si:
(de-fi-ne (list-doub-le ls)
(map (lamb-da (x) (* 2 x)) ls))
(de-fi-ne (list-squ-a-re ls)
(map (lamb-da (x) (* x x)) ls))
(de-fi-ne (syn-tax-rep-la-ce-words s old new)
(syn-tax-map
(lamb-da (word)
(if (string=? word old) new word))
s))
lamb-da näyt-tää siis sa-mal-ta kuin de-fi-ne, pait-si et-tä mi-tään ni-me-ä funk-ti-ol-le ei sa-no-ta. lamb-da:n pe-rässä o-le-vis-sa sul-keis-sa lu-e-tel-laan funk-ti-on saa-mat ar-gu-men-tit ja nii-den jälkeen ker-ro-taan, mi-tä funk-ti-o te-kee (pa-laut-taa). It-se a-si-as-sa Sche-mes-sä funk-ti-oi-den de-fi-ne on määri-tel-ty lamb-da:n pe-rus-teel-la, ja seu-raa-vat määri-tel-mät o-vat kes-ke-nään yh-täpi-tävi-ä:
(de-fi-ne (squ-a-re x) (* x x) <-> (de-fi-ne squ-a-re (lamb-da (x) (* x x))) (de-fi-ne (dis-tan-ce x y) <-> (de-fi-ne dis-tan-ce (lamb-da (x y) (sqrt (+ (squ-a-re x) (squ-a-re y)))) (sqrt (+ (squ-a-re x) (squ-a-re y))))
Tämänkin poh-dis-ke-lu saat-taa tuot-taa kor-ke-am-man tie-toi-suu-den ta-son tai ol-la tuot-ta-mat-ta.