Fibonacci, Bäume und Quadrate (2)
Kategorie Allgemein Scheme
Also jetzt geht es an die Abstraktion.
Man stelle sich for man hätte eine Methode, welche eine Funktion / Operation einen Startwert und eine Liste als Parameter bekommt
Und dann?
Also jetzt geht es an die Abstraktion.
Man stelle sich for man hätte eine Methode, welche eine Funktion / Operation einen Startwert und eine Liste als Parameter bekommt
Und dann?
Die Funktion könnte z.B. accumulate heißen
und wie folgt aussehen ->
(define (accumulate op startvalue sequence)
(if (null? sequence)
startvalue
(op
(car sequence)
(accumulate op startvalue (cdr sequence))
)
)
)
Im wesentlichen macht die Funktion nichts anderes, als über eine Liste iterieren, die übergebene Methode auf das erste Element der Liste und sich selbst auf den Rest der Liste anwenden.
Irgendwann in der Rekursion kommt die Funktion auf die leere Liste und gibt den Startwert zurück, ist op z.B. plus (+), dann hätte man die Summe der Zahlen in der Liste!!!!
z.B.:
(accumulate + 0 (list 1 2 3 4 5 6 7 8 9 10))
Ergibt 55
OK, wenn ich nun eine Funktion z.B. step-tree hätte, welche aus einem Baum eine Liste machen würde, dann könnte ich z.B. alle Zahlen in meinem Baum zusammenzählen durch ->
(accumulate + 0 (step-tree tree))
Gut wieder einen Schritt weiter -> nun sollte man evtl. die Ungeraden rausfiltern, eine Filterprozedur würde helfen ->
(define (filter proof sequence)
(cond
((null? sequence) nil)
((proof (car sequence))
(cons (car sequence) (filter proof (cdr sequence)))
)
(else (filter proof (cdr sequence)))
)
)
Am einfachsten wir geben der Filterprozedur was mit, welches ein true zurückgibt, wenn der Wert zu den zu Filternden gehört. Weiters ist als Parameter eine Liste nötig und der Rückgabewert ist eine Liste mit den gefilterten Inhalten.
Die Summe der ungeraden Zahlen in dem Baum würde dann wie folgt aussehen ->
(accumulate + 0 (filter odd? (step-tree tree)))
So jetzt das gefilterte Extrakt nur noch quadrieren und fertig der Salat ->
(accumulate + 0 (apply-all square (filter odd? (step-tree tree)))
Hierzu benötigen wir natürlich noch eine Funktion apply-all, welche als Parameter eine Operation und eine Liste bekommt und die Operation / Funktion auf alle Listenelemente anwendet und das Ergebnis als Liste zurückgibt.
OK, hätte man evtl. der Funktion aus dem ersten Beispiel einfacher gehabt.
Aber auf dem Weg dahin haben wir auch gleich zwei weitere "Funktionen" nebenbei implementiert -> Summe über alle Zahlen eines Baumes, Summe über alle ungeraden Zahlen in einem Baum.
Und wenn jemand jetzt das Produkt haben möchte, ersetzen wir nur + durch *.
Die Liste der geraden Fibonacci's würden wir so erhalten ->
(accumulate cons nil(filter equal? (apply-all fib (step-interval 0 n))))
D.h. wir bilden eine Liste aus den Zahlen 0 ...n (step-interval), berechnen zu jedem Element der Liste die zugehörige Fibonacci-Zahl (apply-all fib) filtern die geraden aus und bilden daraus eine Liste (cons) mit dem Startwert nil
Gruß JJR
P.S.: Hier noch ein kleines Quiz, die Antworten stehen untendrunter in weiß auf weiß
a) (accumulate (lambda (x y) (cons (p x) y)) nil sequence)
b) (accumulate cons list2 list1)
c) (accumulate (lambda (x y) (+ 1 y)) 0 sequence)
a) Ist die Implementierung eine apply-all mittels accumulate
b) Hängt list2 and list1 an
c) Ermittelt die Länge von der Liste sequence
Hier oben drüber die Auflösung in weiß auf weiß
(define (accumulate op startvalue sequence)
(if (null? sequence)
startvalue
(op
(car sequence)
(accumulate op startvalue (cdr sequence))
)
)
)
Im wesentlichen macht die Funktion nichts anderes, als über eine Liste iterieren, die übergebene Methode auf das erste Element der Liste und sich selbst auf den Rest der Liste anwenden.
Irgendwann in der Rekursion kommt die Funktion auf die leere Liste und gibt den Startwert zurück, ist op z.B. plus (+), dann hätte man die Summe der Zahlen in der Liste!!!!
z.B.:
(accumulate + 0 (list 1 2 3 4 5 6 7 8 9 10))
Ergibt 55
OK, wenn ich nun eine Funktion z.B. step-tree hätte, welche aus einem Baum eine Liste machen würde, dann könnte ich z.B. alle Zahlen in meinem Baum zusammenzählen durch ->
(accumulate + 0 (step-tree tree))
Gut wieder einen Schritt weiter -> nun sollte man evtl. die Ungeraden rausfiltern, eine Filterprozedur würde helfen ->
(define (filter proof sequence)
(cond
((null? sequence) nil)
((proof (car sequence))
(cons (car sequence) (filter proof (cdr sequence)))
)
(else (filter proof (cdr sequence)))
)
)
Am einfachsten wir geben der Filterprozedur was mit, welches ein true zurückgibt, wenn der Wert zu den zu Filternden gehört. Weiters ist als Parameter eine Liste nötig und der Rückgabewert ist eine Liste mit den gefilterten Inhalten.
Die Summe der ungeraden Zahlen in dem Baum würde dann wie folgt aussehen ->
(accumulate + 0 (filter odd? (step-tree tree)))
So jetzt das gefilterte Extrakt nur noch quadrieren und fertig der Salat ->
(accumulate + 0 (apply-all square (filter odd? (step-tree tree)))
Hierzu benötigen wir natürlich noch eine Funktion apply-all, welche als Parameter eine Operation und eine Liste bekommt und die Operation / Funktion auf alle Listenelemente anwendet und das Ergebnis als Liste zurückgibt.
OK, hätte man evtl. der Funktion aus dem ersten Beispiel einfacher gehabt.
Aber auf dem Weg dahin haben wir auch gleich zwei weitere "Funktionen" nebenbei implementiert -> Summe über alle Zahlen eines Baumes, Summe über alle ungeraden Zahlen in einem Baum.
Und wenn jemand jetzt das Produkt haben möchte, ersetzen wir nur + durch *.
Die Liste der geraden Fibonacci's würden wir so erhalten ->
(accumulate cons nil(filter equal? (apply-all fib (step-interval 0 n))))
D.h. wir bilden eine Liste aus den Zahlen 0 ...n (step-interval), berechnen zu jedem Element der Liste die zugehörige Fibonacci-Zahl (apply-all fib) filtern die geraden aus und bilden daraus eine Liste (cons) mit dem Startwert nil
Gruß JJR
P.S.: Hier noch ein kleines Quiz, die Antworten stehen untendrunter in weiß auf weiß
a) (accumulate (lambda (x y) (cons (p x) y)) nil sequence)
b) (accumulate cons list2 list1)
c) (accumulate (lambda (x y) (+ 1 y)) 0 sequence)
a) Ist die Implementierung eine apply-all mittels accumulate
b) Hängt list2 and list1 an
c) Ermittelt die Länge von der Liste sequence
Hier oben drüber die Auflösung in weiß auf weiß
| Permalink | 
