Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
ADT-Aufgabe 5 WS11
Die Operation filter soll aus einer gegebenen Tabelle alle Messwerte zu einem bestimmten (als Argument übergebenen) Ort in eine neue (leere) Tabelle kopieren und letztere zurückgeben. Ergänzen Sie den ADT um Signatur und Axiome für filter.
Die Operation "in"ergänzt die Tabelle um einen Messwert für einen bestimmten Ort.
ops
in: Tabelle x String x Double -->Tabelle
filter: Tabelle x String → Tabelle
axs
filter(leer, ort) = leer
filter( in(tab, ort, wert), ort2) [color=orange]= in(filter(tab, ort2), ort, wert) falls equals(ort, ort2)
= filter (tab, ort2) sonst[/color]
Was passiert im orange markierten Bereich?
-
“equals(ort, ort2)” definiert das Verhalten, wenn der hinzuzufügende ort (ort2) bereits in der Tabelle existiert?
Erstelle ich dann mit “in” eine neue Tabelle und verwende “in” statt “leer”(konstruiert leere Tabelle) um auszudrücken, dass sich in diesem Fall ja schon zumindest der doppelte Ort darin befindet? In der Aufgabenstellung steht ja, dass in eine leere Tabelle kopiert wird, deswegen bin ich mir da unsicher. -
Warum wende ich die filter Operation im equals Fall nochmal rekursiv an und übergebe nicht einfach “tab” als Parameter?
-
Was passiert im sonst Fall? Warum wird hier nochmal rekursiv filter verwendet? Ist das Ergebnis nicht einfach in(tab, ort2, wert)?
Gibt es im Netz noch Ressourcen zum Thema ADTs die euch geläufig sind? Besonders weitere Übungsaufgaben wären toll.
Liebe Grüße
Speedy
eqals == Gleichheit?
Sonst: Ungleichheit?
Bei adts erstellt man immer ein neues Objekt, man kann sie eh nicht verändern.
Rekursion, da der rest der Tabelle auch berücksichtigt werden sollte.
Ein wird schritt für schritt je ein element bearbeitet!
Und einmal möchte man das element „ort“ behalten (eqals) und einmal nicht.
Klären wir doch erstmal grundlegende Fragen:
-
Wie sieht eine Tabelle aus?
Beispiele:
Leere Tabelle: leer
Eine Tabelle mit nur Erlangen: in(leer, “Erlangen”, 4,2)
Eine Tabelle mit Erlangen, Nürnberg, Fürth und Braunschweig und nochmal Erlangen: in(in(in(in(in(leer, “Erlangen”, 4,2), “Nürnberg”, 2,5), “Fürth”, 0,1), “Braunschweig”, 4,1), “Erlangen”, 9,8) -
Was macht filter?
Die Funktionsweise ist ganz einfach, dass wir den Filter auf eine Tabelle jagen, damit er alles rausnimmt, was nicht zu dem Ort gehört.
filter besitzt zwei Definitionen, die jeden möglichen Fall abdecken, mit denen filter konfrontiert werden könnte. Filter stößt entweder auf einen Ort mit Resttabelle, oder auf eine leere Tabelle.
Filter möchte also eine Tabelle und einen String und gibt eine neue Tabelle aus. In dieser sind ALLE Einträge zum gefilterten Ort.
z.B.: filter( in(in(in(in(in(leer, “Erlangen”, 4,2), “Nürnberg”, 2,5), “Fürth”, 0,1), “Braunschweig”, 4,1), “Erlangen”, 9,8) , “Erlangen”) hätte als Ergebnis in(in(leer, “Erlangen”, 4,2), “Erlangen”, 9,8). Und das kann man nachrechnen! Und sollte auch, um es ganz zu verstehen. Wichtig ist dabei, dass die Definitionen pattern-matching benutzen, also filter( in(tab,ort,wert), ort2) beim ersten Schritt vom Beispiel wäre:
filter(in(in(in(in(in(leer, “Erlangen”, 4,2), “Nürnberg”, 2,5), “Fürth”, 0,1), “Braunschweig”, 4,1), “Erlangen”, 9,8), “Erlangen”)
Und wir sehen ja was laut Definition passiert. Versuch’s einfach mal nachzurechnen! Das sollte die allermeisten Fragen klären.
2 „Gefällt mir“
ADTs sollten nichts anderes als induktive Datentypen sein, die Ops eine Obermenge der Konstruktoren und die Axiome rekursive Funktionsdefinitionen.
Stichworte wären „inductive datatypes“, „fold“, „inductive datatypes recursion“. Warnung: Die formalen Grundlagen dieser Dinge sind nicht so einfach und ich bezweifle sehr stark, dass es für dich etwas bringen würde, sich da einzulesen. Insbesondere wäre z. B. Lambdakalkül eine nützliche Grundlage, die du zuvor beherrschen solltest.
Danke euch allen!
@Marcel, ja das denke ich auch. Habe mit Ressourcen eher gemeint etwas zu finden, dass ähnlich zu den Klausuraufgaben ist um mich da noch etwas weiter vorzubereiten.
Alte Klausuren + alte Übungsaufgaben