Grundlagen der funktionsorientierten Programmierung mit SCHEME/Prozeduren höherer Ordnung (I)

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
<code id="4b66d627c6bda" hidden>
(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)))
</code>

== Prozeduren nehmen Prozeduren entgegen ==

Wir betrachten folgende zweistellige Prozeduren:

<table>
<tr>
<td>
<code id="4c83712e85e71">
(define add2
  (lambda (x y)
    (+ x y)))
</code>
<run id="4c83712e863bd">(add2 3 4)</run>
</td>
<td>
<code id="4c83712e85fba">
(define sub2
  (lambda (x y)
    (- x y)))
</code>
<run id="4c83712e864f8">(sub2 3 4)</run>
</td>
<td>
<code id="4c83712e860fb">
(define mult2
  (lambda (x y)
    (* x y)))
</code>
<run id="4c83712e86697">(mult2 3 4)</run>
</td>
<td>
<code id="4c83712e8623d">
(define div2
  (lambda (x y)
    (/ x y)))
</code>
<run id="4c83712e867d4">(div2 3 4)</run>
</td>
</tr>
</table>

=== Zweistellige Prozeduren höherer Ordnung ===

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

<code id="4b1107f5d732e">
(define verarbeiten2
  (lambda (op x y)
    (op x y)))
</code>
<run id="4b1107f5e2eb2">(verarbeiten2 + 3 4)</run>

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

<blockquote>[[Bild:Hoeher1.GIF]]</blockquote>

Gegeben sei die zweistellige Prozedur:
<code id="4b1107f5d82cb">
(define maximum2
  (lambda (x y)
    (if (> x y)
        x
        y)))
</code>
Wir testen unsere Universalprozedur:
<run id="4b1107f5e3e4e">
(verarbeiten2 maximum2 3 4)
</run>

=== Variabelstellige Prozeduren höherer Ordnung ===

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

<code id="4b1107f5d9272">
(define verarbeiten
  (lambda (op x . y)
    (eval (cons op (cons x y)))))
</code>

<run id="5ba5faae51306">(verarbeiten '+ 1 2 3 4 5 6 7 8 9 10)</run>

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

<code id="5ba5faae5119c">
(define verarbeiten
  (lambda (op x . y)
    (apply op (cons x y))))
</code>

<run id="5ba5faae51390">(verarbeiten + 1 2 3 4 5 6 7 8 9 10)</run>

bzw.

<code id="5ba5faae5123d">
(define verarbeiten
  (lambda (op x . y)
    (apply op x y)))
</code>

<run id="5ba5faae5140f">(verarbeiten + 1 2 3 4 5 6 7 8 9 10)</run>

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

<code id="4b1107f5da210">
(define maximum
  (lambda (x . y)
    (max-help x y)))

(define max-help
  (lambda (x ls)
    ...))
</code>

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

<check>
(and (= (maximum 27) 27) (= (maximum 9 8 7 6 5 4 3 2 1) 9))
</check>

<run id="4b1107f5e5d94">(verarbeiten maximum 2 3 6 3 6 1 4)</run>

=== Die Prozedur <tt>map</tt> ===

Testen Sie die Standard-Prozedur <tt>map</tt> an verschiedenen Beispielen:

<run id="4b1107f5e6d30">(map sqr '(1 2 3 4 5 6 7 8 9 10))</run>

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

<code id="4b1107f5db1ad">
(define my-map
  (lambda (proz ls)
    ...))
</code>

<check>
(and (listequal? (my-map sqr '(1 2 3 4 5)) '(1 4 9 16 25))
     (listequal? (my-map (lambda (x) (* 2 x)) '(1 2 3 4 5)) '(2 4 6 8 10)))
</check>

<run id="4b1107f5e7ccf">(my-map sqr '(1 2 3 4 5 6 7 8 9 10))</run>

Wir definieren die Bildungsvorschrift ungerader Zahlen und wenden sie mit <tt>my-map</tt> an:

<code id="4b1107f5dc14c">
(define ungerade
  (lambda (n)
    (+ (* 2 n) 1)))
</code>

<run id="4b1107f5e8c73">(my-map ungerade '(1 2 3 4 5 6 7 8 9 10))</run>

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

<run id="4b1107f5e9c11">(my-map (lambda (n) (+ (* 2 n) 1)) '(1 2 3 4 5 6 7 8 9 10))</run>

=== Aufgaben ===

<ol>
<li>
Entwickeln Sie eine Prozedur höherer Ordnung, mit der die 3. Potenzen (Kubikzahlen) aller Elemente einer numerischen Liste berechnet werden können.
<code id="4b1107f5dd0f0"">
(define kubik
  (lambda (n)
    ...))
</code>

<run id="4b1107f5eabb0">(my-map kubik '(1 2 3 4 5 6 7 8 9 10))</run>
</li>

<li>
Entwickeln Sie die Prozedur <tt>(my-filter &lt;proz&gt; &lt;ls&gt;)</tt>, mit der Elemente mit bestimmten Eigenschaften aus einer Zahlenliste herausgefiltert werden können.<br />
Testen Sie diese Prozedur mit dem Prädikat <tt>gerade?</tt>, z.B.:
<pre>
(my-filter gerade? '(1 2 3 4 5 6 7 8 9 10))
--> (2 4 6 8 10)
</pre>
'''Hinweis:''' Mit der Prozedur <tt>modulo</tt> kann der Rest einer ganzzahligen Division ermittelt werden:
<pre>
(modulo 7 3)  --> 1
(modulo 12 2) --> 0
</pre>
<code id="4b1107f5de08d">
(define gerade?
  (lambda (n)
    ...))

(define my-filter
  (lambda (proz ls)
    ...))
</code>

<check>
(and (gerade? 2) (not (gerade? 99)) (listequal? (my-filter gerade? '(1 2 3 4 5 6 7 8 9 10)) '(2 4 6 8 10))) 
</check>

<run id="4b1107f5ebb54">(my-filter gerade? '(1 2 3 4 5 6 7 8 9 10))</run>
</li>
</ol>

== Zum Weiterarbeiten ==

=== Primzahlfilter ===

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

Zur [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Primzahlfilter|Problemlösung]].