Göm menyn

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!

Se svar

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)

Se svar

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))

Se svar

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

Se svar

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))

Se svar

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.

Se svar

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)

Se svar

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.

Se svar


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2004-11-08