English web site
Del E: Högre ordningens funktioner
Exempel E1
Skriv en funktion produkt som beräknar följande:
b
-----
| |
| | f(n) = f(a) * f(a+1) * ... * f(b)
| |
n = a
dvs produkten av att applicera f på talen a till b. För att beräkna:
10
-----
| | 2 2 2 2
| | n = 1 * 2 * ... 10
| |
n = 1
dvs produkten av kvadraterna på talen 1 till 10, skulle vi med hjälp av vår nya funktion kunna skriva:
(produkt #'(lambda (x) (* x x)) 1 10)
Funktionen kan skrivas med rekursiv eller iterativ processlösning. Ge båda lösningarna!
Exempel E2
Skriv en funktion filtrerad-summa som beräknar summan av f(n) från a till b där n uppfyller predikatet g(n). För att summera kvadraterna på alla tal från 1 till 10 som är delbara med 3 kan man alltså skriva:
(filtrerad-summa
#'(lambda (x) (* x x))
#'(lambda (x) (= 0 (rem x 3)))
1 10)
Exempel E3
Skriv en funktion map-all som tar en funktion med
två argument samt två listor. De två listorna ska ha samma struktur,
dvs underlistor på samma ställen, och en lista med likadan struktur
ska returneras. I den nya listan ska elementen vara resultaten av
att applicera den givna funktionen på två element, ett från vardera
listan. Antag att listorna har samma struktur. Exempel:
CL-USER(31): (map-all #'+ '(1 (2 (3) 4)) '(10 (20 (30) 49))) (11 (22 (33) 53)) CL-USER(32): (map-all #'eq '(a (b c)) '(a (x c))) (T (NIL T))
Exempel E4
Skriv en funktion hur-många? som tar en funktion
och en lista och anger för hur många element (på alla nivåer) som
funktionen returnerar sant. Exempel:
CL-USER(33): (hur-många? #'numberp '(1 a 2 (b 3 c))) 3 CL-USER(34): (hur-många? #'(lambda (x) (eq x 'a)) '(a (a b c) a x a)) 4
Exempel E5
Skriv en funktion ack som tar en funktion och en lista
och returnerar en ny lista som är resultaten av att först applicera
funktionen på hela ursprungslistan, därefter på listan utom det första
elementet, utom det andra elementet, osv. Exempel:
CL-USER(39): (ack #'+ '(1 2 3 4 5)) (15 14 12 9 5) CL-USER(40): (ack #'append '((1 2) (a b) (x y))) ((1 2 A B X Y) (A B X Y) (X Y))
Exempel E6
Skriv en funktion samla-ihop som tar en funktion
och en lista. Funktionen ska appliceras på varje element i listan
och en ny lista ska returneras med resultaten. Element som blir
nil ska dock inte tas med. Exempel:
CL-USER(48): (samla-ihop #'cdr
'((a b c) (a) (x y) (x)))
((B C) (Y))
CL-USER(49): (samla-ihop #'(lambda (e) (if (numberp e) (+ e 10) nil))
'(1 a 2 3 b 4))
(11 12 13 14)
Definiera funktionen utan att använda några av Lisps
map-funktioner.
Exempel E7
Skriv en funktion finns? som i ett binärt träd
representerat av punkterade par undersöker om det finns minst ett
element som uppfyller ett givet villkor. Exempel:
CL-USER(50): (finns? #'numberp '(a . ((b . 1) . (c . 2)))) T
Antag vidare att vi har en funktion f definierad som:
(defun f (träd a b)
(finns? #'(lambda (e) (and (> e a) (< e b))) träd))
Vad gör funktionen f? Vad kommer resultatet av följande
uttryck att bli?
(f '(1 . ((2 . 7) . (10 . 5))) 4 9)
Exempel E8
För att hitta nollstället inom ett intervall till en funktion kan man använda sig av intervalldelning. Genom att dela intervallet i mitten och jämföra tecken kan man avgöra i vilket delintervall nollstället finns. Processen upprepas med det halverade intervallet ända tills nollstället ringats in med önskad noggrannhet. Antag att vi söker nollstället till funktionen
2
f(x) = x - x - 2
i intervallet 0 till 3 med en noggrannhet av +-0,005. Vi kan då ställa upp följande tabell:
Övre Undre
gräns (a) Mitt (c) gräns (c) f(a) f(b) f(c)
--------- --------- --------- --------- --------- ---------
3 1,5 0 4 -1,25 -2
3 2,25 1,5 4 0,5625 -1,25
2,25 1,875 1,5
Ovanstående funktion ska alltså kunna testas genom följande anrop:
CL-USER(55): (float (nollställe #'(lambda (x) (+ (* x x) (- x) -2))
3 0 0.005))
2.0009766
Notera att vi använder float för att omvandla bråk
till flyttal.
Sidansvarig: Peter Dalenius
Senast uppdaterad: 2004-11-08
