Prozeduren höherer Ordnung (I)

Aus ProgrammingWiki

(define listequal? (lambda (ls1 ls2) (cond [(and (null? ls1) (null? ls2)) #t] [(or (null? ls1) (null? ls2)) #f] [(and (list? (car ls1)) (list? (car ls1))) (and (listequal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))] [else (and (equal? (car ls1) (car ls2)) (listequal? (cdr ls1) (cdr ls2)))]))) (define sqr (lambda (x) (* x x)))

Inhaltsverzeichnis 1 Prozeduren nehmen Prozeduren entgegen 1.1 Zweistellige Prozeduren höherer Ordnung 1.2 Variabelstellige Prozeduren höherer Ordnung 1.3 Die Prozedur map 1.4 Aufgaben 2 Zum Weiterarbeiten 2.1 Primzahlfilter

Prozeduren nehmen Prozeduren entgegen

Wir betrachten folgende zweistellige Prozeduren:

(define add2 (lambda (x y) (+ x y))) (add2 3 4) ausführen

(define sub2 (lambda (x y) (- x y))) (sub2 3 4) ausführen

(define mult2 (lambda (x y) (* x y))) (mult2 3 4) ausführen

(define div2 (lambda (x y) (/ x y))) (div2 3 4) ausführen

Zweistellige Prozeduren höherer Ordnung

Die Prozeduren unterscheiden sich nur durch die Verwendung des Operators. Wir entwickeln deshalb eine (zunächst) zweistellige Universalprozedur:

(define verarbeiten2 (lambda (op x y) (op x y)))

(verarbeiten2 + 3 4)

ausführen

Die Prozedur verarbeiten2 nimmt neben den beiden Operanden x und y einen Operator bzw. eine Prozedur entgegen.
Sie ist damit eine Prozedur höherer Ordnung.
Prozeduren höherer Ordnung nehmen Prozeduren als Argumente entgegen oder geben Prozeduren als Funktionswerte zurück.

Gegeben sei die zweistellige Prozedur:

(define maximum2 (lambda (x y) (if (> x y) x y)))

Wir testen unsere Universalprozedur:

(verarbeiten2 maximum2 3 4)

ausführen

Variabelstellige Prozeduren höherer Ordnung

Es ist bekannt, dass die Standard-Prozeduren +, -, * und / variabelstellige Prozeduren sind, die eine beliebige Anzahl von Operanden entgegen nehmen können, mindestens aber einen Operanden benötigen.
Wir generalisieren deshalb unsere Universalprozedur zur variabelstelligen Prozedur verarbeiten:

(define verarbeiten (lambda (op x . y) (eval (cons op (cons x y)))))

(verarbeiten '+ 1 2 3 4 5 6 7 8 9 10)

ausführen

Aus der Syntax der Prozedurdefinition ist erkennbar, dass die Argumente op und x zwingend erforderlich sind, während alle weiteren Parameter zu einer Liste zusammengefasst werden. Diese Liste kann durchaus leer sein.
Beachte: In dieser Implementation muss aber der Operator quotiert übergeben werden.
Die Nacheinanderausführung von cons und eval wird deshalb mit der Prozedur apply zusammengefasst:

(define verarbeiten (lambda (op x . y) (apply op (cons x y))))

(verarbeiten + 1 2 3 4 5 6 7 8 9 10)

ausführen

bzw.

(define verarbeiten (lambda (op x . y) (apply op x y)))

(verarbeiten + 1 2 3 4 5 6 7 8 9 10)

ausführen

Im Gegensatz zur ersten Definition wird hier der Operator nicht quotiert, so dass verarbeiten wieder eine "echte" Prozedur höherer Ordnung ist.
Nun können wir auch die Maximum-Prozedur zu einer variabelstelligen Prozedur erweitern:

(define maximum (lambda (x . y) (max-help x y))) (define max-help (lambda (x ls) ...))

Ergänzen Sie die Hilfsprozedur max-help, mit der aus dem Argument x sowie einer weiteren Zahlenliste ls das Maximum zurückgegeben werden soll.

(verarbeiten maximum 2 3 6 3 6 1 4)

ausführen

Die Prozedur map

Testen Sie die Standard-Prozedur map an verschiedenen Beispielen:

(map sqr '(1 2 3 4 5 6 7 8 9 10))

ausführen

Beschreiben Sie die Signatur dieser Prozedur.
Begründen Sie, warum map eine Prozedur höherer Ordnung ist.
Bilden Sie nun diese Standard-Prozedur mit der benutzerdefinierten Prozedur my-map nach.

(define my-map (lambda (proz ls) ...))

(my-map sqr '(1 2 3 4 5 6 7 8 9 10))

ausführen

Wir definieren die Bildungsvorschrift ungerader Zahlen und wenden sie mit my-map an:

(define ungerade (lambda (n) (+ (* 2 n) 1)))

(my-map ungerade '(1 2 3 4 5 6 7 8 9 10))

ausführen

Es muss klar sein, dass auch unbenannte Prozeduren übergeben werden können:

(my-map (lambda (n) (+ (* 2 n) 1)) '(1 2 3 4 5 6 7 8 9 10))

ausführen

Aufgaben

1. Entwickeln Sie eine Prozedur höherer Ordnung, mit der die 3. Potenzen (Kubikzahlen) aller Elemente einer numerischen Liste berechnet werden können.

   (define kubik (lambda (n) ...))

   (my-map kubik '(1 2 3 4 5 6 7 8 9 10))

   ausführen

2. Entwickeln Sie die Prozedur (my-filter <proz> <ls>), mit der Elemente mit bestimmten Eigenschaften aus einer Zahlenliste herausgefiltert werden können.
   Testen Sie diese Prozedur mit dem Prädikat gerade?, z.B.:

   (my-filter gerade? '(1 2 3 4 5 6 7 8 9 10))
   --> (2 4 6 8 10)
   

   Hinweis: Mit der Prozedur modulo kann der Rest einer ganzzahligen Division ermittelt werden:

   (modulo 7 3)  --> 1
   (modulo 12 2) --> 0
   

   (define gerade? (lambda (n) ...)) (define my-filter (lambda (proz ls) ...))

    

   Quelltext überprüfen:

   jetzt prüfen

   (my-filter gerade? '(1 2 3 4 5 6 7 8 9 10))

   ausführen

Zum Weiterarbeiten

Primzahlfilter

Mit einem Prädikat primzahl?, das zu einer natürlichen Zahl entscheidet, ob sie eine Primzahl ist, könnte die Prozedur my-filter aus einer Liste beliebiger natürlicher Zahlen alle Primzahlen herausfiltern.
Setzen Sie diese Idee um!

Zur Problemlösung.