foldr foldl wat?

baerchen
Computerversteher
Computerversteher
Beiträge: 382
Registriert: 24. Okt 2006 15:42

foldr foldl wat?

Beitrag von baerchen » 10. Nov 2006 03:24

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?

Benutzeravatar
E.d.u.
Nerd
Nerd
Beiträge: 633
Registriert: 3. Feb 2004 17:01
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von E.d.u. » 10. Nov 2006 13:49

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 :-)

Silverspring
Neuling
Neuling
Beiträge: 2
Registriert: 6. Nov 2006 21:04

Beitrag von Silverspring » 10. Nov 2006 22:42

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.

murri
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 196
Registriert: 20. Nov 2005 21:18

Beitrag von murri » 11. Nov 2006 14:25

Hmm ich bin gerade ein wenig am verzweifeln.
Könnt ihr mir nur sagen, ob ihr mit (third list) arbeitet?

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 » 12. Nov 2006 02:51

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..

Benutzeravatar
gobbledygook
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 11. Nov 2006 14:15

Beitrag von gobbledygook » 13. Nov 2006 15:13

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 :)




Ich mag keine Vegetarier.
Die essen meinem Essen das Essen weg.

Benutzeravatar
E.d.u.
Nerd
Nerd
Beiträge: 633
Registriert: 3. Feb 2004 17:01
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von E.d.u. » 13. Nov 2006 15:39

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?

Benutzeravatar
gobbledygook
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 11. Nov 2006 14:15

Beitrag von gobbledygook » 13. Nov 2006 16:06

yeah. steht nun mal so in der aufgabenstellung :(




Ich mag keine Vegetarier.
Die essen meinem Essen das Essen weg.

murri
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 196
Registriert: 20. Nov 2005 21:18

Beitrag von murri » 14. Nov 2006 16:13

geb mal jemand ein denkanstoß...

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

Xelord
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 225
Registriert: 23. Okt 2004 09:49

Beitrag von Xelord » 14. Nov 2006 21:06

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.

XaVoR
Neuling
Neuling
Beiträge: 3
Registriert: 15. Nov 2006 13:15

Beitrag von XaVoR » 15. Nov 2006 16:19

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

Benutzeravatar
MisterD123
Geek
Geek
Beiträge: 811
Registriert: 31. Okt 2006 20:04
Wohnort: Weiterstadt

Beitrag von MisterD123 » 15. Nov 2006 19:08

stimmt schon, die 6.2 ist bei weitem am schwersten. Aber umso schöner wenn mans dann geschafft hat, oder? ;)

murri
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 196
Registriert: 20. Nov 2005 21:18

Beitrag von murri » 15. Nov 2006 22:46

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?!?!?

Benutzeravatar
Robert
Ehemalige Fachschaftler
Beiträge: 511
Registriert: 6. Okt 2004 17:38
Wohnort: DA

Beitrag von Robert » 16. Nov 2006 11:03

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.

neffs
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 16. Okt 2006 19:07
Kontaktdaten:

Beitrag von neffs » 17. Nov 2006 18:11

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!

Antworten

Zurück zu „Archiv“