Prozeduren höherer Ordnung-Loesung

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
[[Programmierparadigmen_-_Computerübungen|zur Übungsübersicht]]

<code id="4af43622f15f4" hidden>
(define listvergleich
 (lambda(l1 l2)
  (cond
   ((and (null? l1) (null? l2)) #t)
   ((not (= (length l1) (length l2))) #f)
   ((not (= (car l1) (car l2) )) #f)
   (else (listvergleich (cdr l1) (cdr l2)))
  )
 )
)
(define groesser
  (lambda (w)
     (> w 0)))
</code>


==Filter==
Schreiben Sie eine Prozedur <tt>filter</tt>, die eine Liste und eine Filterprozedur nimmt, und eine "gefilterte" Liste zurückgibt.

'''Hinweis:''' Die Filterprozedur ist eine einstellige Prozedur, welche <tt>#t</tt> bzw. <tt>#f</tt> zurückgibt.

'''Aufrufbeispiele'''
 >(filter '(1 2 3 4 5 6 7 8 9) even?)
 (2 4 6 8)
 >(filter '(1 2 3 4 5) (lambda (x) (not (or (= x 2) (= x 5)))))
 (1 3 4)
 >(filter '(#\a 276 "blubb" 5 blah 3 5 (4 995 54)) number?)
 (276 5 3 5)
<code id="4af43622f1dda">
(define filter 
  (lambda (liste funktion)
    (cond
      ((null? liste) '())
      ((funktion (car liste)) (cons (car liste) (filter (cdr liste) funktion)))
      (else
        (filter (cdr liste) funktion)))))
</code>
<run id="4af4362300acb">(filter '(1 2 3 4 5 6 7 8 9) even?)</run>
<check>
(listvergleich '(1 2 3 4) (filter '(-1 1 -2 2 0 -3 3 -4 4) groesser)) 
</check>

==Tabellieren==

Schreiben Sie eine Prozedur <tt>tabelliere</tt> zur Ausgabe einer Wertetabelle mit den Spalten <math>x</math> und <math>f(x)</math>, wobei <math>f</math> eine einstellige Funktion ist, die für <math>x=a,a+1,\ldots,b</math> protokolliert werden soll. <math>f</math>, <math>a</math> und <math>b</math> sollen beim Aufruf als Parameter übergeben werden.
     
'''Hinweis:''' Testen Sie auch mit Lambda-Ausdrücken für <math>f</math>.

'''Aufrufbeispiel:'''
 > (tabelliere (lambda (x) (* x x)) 0 5)
 (0 1 4 9 16 25)
<code id="4af43622f2627">
(define tabelliere
  (lambda (funktion untergrenze obergrenze)
    (display untergrenze) (display #\tab) (display (funktion untergrenze)) (newline)
    (if (>= untergrenze obergrenze)
      'schluss
      (tabelliere funktion (+ untergrenze 1) obergrenze))))
</code>
<run id="4af43623012b8">(tabelliere (lambda (x) (* x x)) 0 5)</run>
<check>listvergleich '(0 2 6 12 20 30) (tabelliere (lambda (x) (* (+ x 1) x)) 0 5)</check>

<language>Scheme</language>
==Compose==
Schreiben Sie eine Prozedur <tt>compose</tt>, die zwei einstellige Prozeduren <tt>proc1</tt> und <tt>proc2</tt> nimmt, diese verkettet und die Verkettungsprozedur "<tt>proc2</tt> nach <tt>proc1</tt>" zurückgibt. Wenden Sie <tt>compose</tt> auf geeignete Argumente an.
        
'''Aufrufbeispiel:'''
 > ((compose (lambda (n) (+ n n)) (lambda (n) (* n n))) 4)
 64
'''Wichtig:''' Die Klammersetzung im Aufrufbeispiel ist korrekt!     
                                     
<code id="4af43622f2d70">
(define compose 
  (lambda (proc1 proc2)
    (lambda (x) (proc2 (proc1 x)))))
</code>
<run id="4af4362301a70">((compose (lambda (n) (+ n n)) (lambda (n) (* n n))) 4)</run>
<check>(= ((compose (lambda (n) (* n n)) (lambda (n) (+ n 5))) 5) 30)</check>

==Primzahlen==
Verwenden Sie die oben definierte Prozedur <tt>filter</tt>, um aus der Liste der natürlichen Zahlen von 1 bis 1000 alle Primzahlen herauszusieben. Die verbleibenden Primzahlen sollen als Liste zurückgegeben werden.

<language>Scheme</language>
<language>Scheme</language>
===Natürliche Zahlen===                                                          
Sie benötigen eine Hilfsprozedur <tt>nliste</tt>, die eine Liste mit natürlichen Zahlen von 1 bis <tt>n</tt> erzeugt.

'''Aufrufbeispiel:'''
 > (nliste 5)
 (1 2 3 4 5)

<code id="4af43622f35a4">
(define nliste 
  (lambda (zahl)
    (if (= zahl 0)
       '()
       (append (nliste (- zahl 1)) (list zahl)))))
</code>
<run id="4af43623022e5">(nliste 1000)</run>

Außerdem benötigen Sie eine Prozedur <tt>prim?</tt>, die für eine gegebene natürliche Zahl <math>n</math> feststellt, ob sie eine Primzahl ist oder nicht. Verwenden Sie die folgende Prozedur <tt>alle-teiler</tt> zur Definition von <tt>prim?</tt>.

<code id="4af444a7e4af5">
(define alle-teiler
  (lambda (n t)
    (cond
      ((= t 1) '())
      ((zero? (remainder n t)) (cons t (alle-teiler n (- t 1))))
      (else
       (alle-teiler n (- t 1))))))
</code>
<run id="4af444a7e5e7b">(alle-teiler 24 24)</run>

Beachten Sie, dass die Prozedur <tt>alle-teiler</tt> die Zahl 1 nicht enthält. Mathematisch ist 1 Teiler jeder Zahl.

<code id="4af444a7e52c5">
(define prim?
  (lambda (n)
    (if (< n 2) 
        #f
        (equal? (list n)(alle-teiler n n)))))
</code>
<run id="4af444a7e6645">(prim? 11)</run>

Nun kann die Liste der Primzahlen berechnet werden:

'''Aufrufbeispiel:'''
 (filter (nliste 1000) prim?)
 >(2 3 5 7 11 13 17 19 ...)

<run id="4af4362302a67"> (filter (nliste 1000) prim?)</run>
<check>(equal? '(2 3 5 7 11 13 17 19) (filter (nliste 20) prim?))</check>

==Filter-Out==
Schreiben Sie analog zu <tt>filter</tt> eine Prozedur <tt>filter-out</tt>, die statt der Liste mit Primzahlen die Restliste ohne Primzahlen liefert. Die Primzahlen werden sozusagen herausgefiltert und aus der Ursprungsliste entfernt.

'''Aufrufbeispiel:'''
 > (filter-out (nliste 1000) prim?)
 (1 4 6 8 9 10 12 14 15 ...)
<code id="4af43623002f8">
(define filter-out
  (lambda (ls pred)
    (cond
      ((null? ls) '())
      ((pred (car ls)) (filter-out (cdr ls) pred))
      (else
        (cons (car ls) (filter-out (cdr ls) pred))))))
</code>
<run id="4af43623031d9"> (filter-out (nliste 1000) prim?)</run>
<check>(listvergleich '(1 4 6 8 9 10 12 14 15 16 18 20) (filter-out (nliste 20) prim?))</check>

[[Programmierparadigmen_-_Computerübungen|zur Übungsübersicht]]