Seite 1 von 4

foldr foldl wat?

Verfasst: 10. Nov 2006 03:24
von baerchen
Hallo hab mal eine Frage wegen der Übung 6, teil 2. Da sollen wir eine Funktion foldr benutzen die ich bis jetzt noch nicht kannte. Da dachte ich mir 'Hey gar nicht schlimm, schaust du halt mal ins Skript'. Jetzt ist aber alles was ich an Information über foldr bzw. fold finde der folgende Satz.

;; fold: X (X Y -> Y) (listof Y) -> Y

fold stellt ein übliches Pattern für Operationen auf Listen dar
Anwendung einer binären Operation auf dem ersten Element und
auf dem Ergebnis der Anwendung von fold auf dem Rest der Liste

Vom Googlen bin ich übrigens auch nicht schlauer geworden.

Mein Problem und meine Frage ist jetzt: WAS macht dieses komische fold mit WAS und WAS kommt dabei raus. Und kann man das so formulieren dass das sogar in einen mittelmäßigen Verstand wie meinen irgendwie reinpasst?

Verfasst: 10. Nov 2006 13:49
von E.d.u.
das hat mir sehr geholfen (beim verstehen von foldr, bin noch bei der aufgabe ;-) )

purpose:
(foldr f base (list x-1 ... x-n)) = (f x-1 ... (f x-n base))

Z.b. Liste: myList: '(4 5 3)
Deine Funktion f:
(define (f x y)
(+ x y) )

dann wuerde (foldr f 0 myList) folgendes bewirken:
(f 4 (f 5 (f 3 0))) also 12, also er addiert alle zahlen der liste auf (weil ich meine f funktion so definiert hab) , und beim letzten mal addiert dein "base" parameter, in diesem fall 0.

Ich hoffe es ist klarer geworden :-)

Verfasst: 10. Nov 2006 22:42
von Silverspring
Die Definition von foldl bzw. foldr war im deutschen Foliensatz irgendwie rausgefallen, ist dort aber mittlerweile aktualisiert. Das wurde auf der GDI Homepage unter "aktuelles" auch angekündigt.
Die Definition von E.d.u. stimmt auf jeden Fall für foldr. Foldr steht dabei für "falten von rechts" und foldl für "falten von links". Du "faltest" mit foldr also deine Liste von rechts nach Links zusammen, mit verschachtelten Aufrufen der Funktion f.

Verfasst: 11. Nov 2006 14:25
von murri
Hmm ich bin gerade ein wenig am verzweifeln.
Könnt ihr mir nur sagen, ob ihr mit (third list) arbeitet?

Verfasst: 12. Nov 2006 02:51
von MisterD123
warum third? o_O für was denn? Also ich hab die Hausübung 3 grade gemacht, man braucht nicht mal second, geschweige denn third..

Verfasst: 13. Nov 2006 15:13
von gobbledygook
und foldr brauch ma auch nicht
- haett wohl die aufgabenstellung vor ner stunde mal genauer lesen sollen, damn

aber die folien gehn schon ab bei foldr und foldl :)

Verfasst: 13. Nov 2006 15:39
von E.d.u.
gobbledygook hat geschrieben:und foldr brauch ma auch nicht
- haett wohl die aufgabenstellung vor ner stunde mal genauer lesen sollen, damn

aber die folien gehn schon ab bei foldr und foldl :)
aeh man soll aber foldr benutzen, also foldr braucht man schon .. oder was meinst du?

Verfasst: 13. Nov 2006 16:06
von gobbledygook
yeah. steht nun mal so in der aufgabenstellung :(

Verfasst: 14. Nov 2006 16:13
von murri
geb mal jemand ein denkanstoß...

habt ihr die funktion die ihr ins foldr reinschreibt seperat geschrieben??
oder reicht eine vorgegebene?

Verfasst: 14. Nov 2006 21:06
von Xelord
Meines Wissens nach sollte es keine Funktion in Scheme geben, die genau das bucket bilden macht.
Die Funktion müsst ihr also schreiben.
Natürlich geht es ohne foldr/l, aber ihr sollt grade üben, für was und wie man es benutzt.

Verfasst: 15. Nov 2006 16:19
von XaVoR
also wenn ich zurück schaue finde ich die 6.2 gegenüber den restlichen teilaufgaben unverhältnismässig schwer ... die paar zeilen code haben von mir ein paar stunden gefordert :( (mit musik und icq). hab die funktion für die buckets ausgelagert , man kann sie aber auch local machen , aber das ist zu krass für mein kopf

Verfasst: 15. Nov 2006 19:08
von MisterD123
stimmt schon, die 6.2 ist bei weitem am schwersten. Aber umso schöner wenn mans dann geschafft hat, oder? ;)

Verfasst: 15. Nov 2006 22:46
von murri
Was übergibt denn foldr bei einem Durchlauf?
Bei einer Funktion mit 2 Variablen ist bei mir die erste ne Zahl und die Zweite komischerweiße immer ne Liste mit einem Element?!?!?

Verfasst: 16. Nov 2006 11:03
von Robert
ich hab das heut mal in der übung einigen leuten erklärt .. ich wills hier nochmal schnell machen, ich hoffe dann wird das benutzen von foldr klarer.
stellt euch einfach vor foldr würde intern folgendes machen:
es wird aufgerufen mit: (mal etwas mathematische schreibweise)
foldl ( f , y0 , [x1,...,xn] )
dann wird intern folgendes gemacht:
y1 = f ( x1 , y0)
y2 = f ( x2 , y1)
.
.
.
yn = f ( xn , yn-1)

und dann wird yn als Ergebniss geliefert

heißt also er wendet die funktion f einfach von links auf alle elemente einzeln an .. dabei kennt f aber auch gleichzeitig y .. es wird ihm ja übergeben.

(Anmerkung, das dient nur dem verständniss, es wird in wirklichkeit anders gemacht, wenn man es sich aber so vorstellt dann kappiert man recht gut WAS foldl so macht, das WIE braucht man für DIE Aufgaben nicht)

[EDIT:] ich hab eben gemerkt das ich heut morgen aus versehen foldl erklärt hab aber gesagt hab es sei foldr .. hab das eben mal angepasst. hier nochmal kurz zum foldr .. das würde ganz analog so funktionieren intern:
y1 = f ( xn , y0)
y2 = f ( xn-1 , y1 )
y3 = f ( xn-2 , y2 )
.
.
.
yn = f ( x1 , yn-1 )

also einfach nur rückwärts angefangen.

Verfasst: 17. Nov 2006 18:11
von neffs
wie sieht es eigentlich mit lambda aus? auf dem übungsblatt steht: zwischenstufe, nicht zwischenstufe mit lambda
wie wird das gehandhabt, wenn ich eine lösung mit lambda abgeben?

danke schon mal!