« Fibonnaci, Bäume und Quadrate | Main| Typen ettiketieren ? »

Fibonacci, Bäume und Quadrate (2)

0
Category  
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ß

Post A Comment

:-D:-o:-p:-x:-(:-):-\:angry::cool::cry::emb::grin::huh::laugh::lips::rolleyes:;-)

Amazon


Impressum

Firmenname: Peanuts-Soft
Straße Nummer: Biinger Strasse 8
PLZ Ort: 55263 Wackernheim
Telefon: +491772134526
E-Mail: joerg.reck @ peanuts-soft.de
Disclaimer: Peanuts-Soft übernimmt keine Garantie dafür, dass die auf dieser Website bereitgestellten Informationen vollständig, richtig und stets aktuell sind. Dies gilt auch für alle Links, auf die verwiesen wird. Peanuts-Soft ist für die Inhalte, auf die per Link verwiesen wird, nicht verantwortlich. Peanuts-Soft haftet nicht für konkrete, mittelbare und unmittelbare Schäden oder Schäden, die durch fehlende Nutzungsmöglichkeiten, Datenverluste oder entgangene Gewinne – sei es aufgrund der Nichteinhaltung vertraglicher Verpflichtungen, durch Fahrlässigkeit oder eine andere unerlaubte Handlung – im Zusammenhang mit der Nutzung von Dokumenten oder Informationen bzw. der Erbringung von Dienstleistungen entstehen, die auf dieser Web Site zugänglich sind.
Datenschutz: Inhalt und Gestaltung der Internetseiten sind urheberrechtlich geschützt. Eine Vervielfältigung der Seiten oder deren Inhalte bedarf der vorherigen schriftlichen Zustimmung von Peanuts-Soft.


Locations of visitors to this page

Powered By

Domino BlogSphere
Version 3.0.2