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.
Listengeneratoren
Servus,
da ich leider die Woche zu keiner Übung gehen kann, hab ich mal eine Verständnisfrage zu diesen Listengeneratoren:
Also wenn ich das richtig verstanden habe (Am Beispiel von Prim):
def getPossibleEdges: List[List[(Int, Int)]] => List[Int] => List[(Int, Int, Int)] = xss => { for (x<-xss) …}
der erste Wert repräsentiert ja die Liste aller verfügbarer Knoten bzw. wiederum Listen die die Nachfolger des Knoten mit Kosten enhält, die zweite eine Liste bereits besuchter Knoten (kriegt die Methode beides übergeben) und zurückgegeben wird eine Liste mit Start und Endknoten sowie dessen Kosten die dann Teil des Baumes sind.
und aus den Beispielen der Übungsfolien wende ich das von Liste 1 auf Liste 2 an und habe als Ergebnis Liste 3
mir ist noch nicht ganz klar wie ich jetzt an die erste Liste überhaupt rankomme, wenn ich es mit einer for schleife versuche, will er mir immer weis machen das er hier ein List[(Int, Int, Int)] erwartet.
Ich bin mir nicht sicher, ob ich aus deinem Text heraus verstehe, was dein Problem ist. Rein vom Code her würde ich sagen, dir fehlt eine Parameterliste. Du definierst die erste Parameterliste (mit dem Parameter [m]xss[/m], der die Adjazenzliste darstellt). Nun folgt hinter deinem Pfeil die zurückgegebene Funktion, die aber auch eine Parameterliste konsumieren möchte (die du aber nicht definiert hast). Vermutlich rückt es dein Problem also in ein anderes Licht, wenn du nach [m]xss =>[/m] noch eine Parameterliste (z.B. [m]visited =>[/m]) für die Liste der besuchten Knoten einfügst.
Ach ja: Listengeneratoren ≠ for-Schleife. 
Guten Morgen,
das mit der For-Schleife ist klar 
also in diesem Stand wie gesagt erwartet er ein List[(Int,Int,Int)] im Kopf der For-Schleife, ich wäre jetzt davon ausgegangen das dort eigentlich ein List[List[(Int,Int)]] erscheint und ich mir mit der For-Schleife die List[(Int,Int)] hole :), was aber ja offensichtlich nicht der Fall ist.
Mir ist irgendwie der ganze aufbau dieser Listengeneratoren noch nicht so ganz klar, wie es funktioniert.
Wenn ich es also richtig verstehe müsste der aufbaue so sein:
def methode: ÜbergabeParameter1 => ÜbergabeParameter2 => Erg = ÜP1_var => ÜP2_var => Erg_var => { … }
sowas wie das beispiel hier: def curry: ((Int, Int ) => Int) => (Int => Int => Int) = f => a => b => f(a, b)
wobei das vermutlich aber nicht ganz so einfach ist.
Nicht ganz, du hast bei deiner Methode auch das Ergebnis benannt, dies musst du allerdings weglassen (dies gilt es ja zu definieren/programmieren). Also:
def methode: ÜbergabeParameter1 => ÜbergabeParameter2 => Erg = ÜP1_var => ÜP2_var => { ... }Vielleicht zum besseren Verständnis auf die Aufgabe angewendet (ohne das ich hier zu viel der Lösung verrate ;-)):
def getPossibleEdges: List[List[(Int, Int)]] => List[Int] => List[(Int, Int, Int)] = edges => visited => {/* for ... yield ... */}Ich glaub ich check einfach dieses ganze Scalakonzept nicht so wirklich… selbst mach mehrmaligem durchforsten der vl/ü-folien oder irgendwelcher foren… scala und ich werden glaube ich nicht wirklich grün. 
Da die Aufgabenstellung nicht ganz trivial ist, hier ein paar Hinweise:
Zuerst einmal zur Darstellung des Graphen selbst: es handelt sich um eine [m]List[List[(Int, Int)]][/m], also z.B. [m]List(List((1,3)), List((2,3)), List())[/m] ergibt folgenden “Graphen” (Knoten werden anhand des Indizes der äußeren Liste dargestellt, die Liste an diesem Index enthält die Nachfolger dieses Knotens und die Kosten der jeweiligen Kante, man sieht also z.B. dass Knoten 2 keine Nachfolger hat):
3 3
0 ----> 1 ----> 2Außerdem bekommt [m]getPossibleEdges[/m] eine Liste bereits besuchter Knoten, um obiges Beispiel fortzuführen z.B. [m]List(0)[/m] (dem Startknoten). Um nun alle infrage kommenden Nachfolgeknoten zu bekommen, muss man wie folgt vorgehen:
1. Gehe die Liste der bereits besuchten Knoten durch, für jeden dieser:
2. Gehe die Liste dessen Nachfolgerknoten durch:
3. Falls noch nicht besucht, gebe das Tupel (betrachteter besuchter Knoten, Nachfolgerknoten, Kosten) zurückIm obigem Beispiel also: unser einziger besuchter Knoten ist [m]0[/m], dieser hat die Nachfolger [m]List((1,3))[/m] (die Liste am Index [m]0[/m]), da dieser noch nicht besucht ist wird also m[/m] zurückgegeben.
Das ganze gilt es nun in einen Listengenerator zu gießen, dazu ist es wahrscheinlich hilfreich folgendes zu wissen:
- Man kann über mehrere Indizes gleichzeitig iterieren, z.B. [m]for (x ← 0 until 10; y ← 0 until 10) yield (x, y)[/m] liefert alle möglichen Tupel mit einstelligen Zahlenwerten
- Man kann Bedingungen hinzufügen, z.B. [m]for (x ← 0 until 10; if (x % 2 == 0)) yield x[/m] liefert alle einstelligen geraden Zahlen
Ich denke mit diesem Wissen sollte man zumindest [m]getPossibleEdges[/m] hinbekommen. Sollten noch weitere Fragen bestehen einfach melden
Frage bezüglich des yields, muss diesem eine if anweisung oder etwas adneres vorausgehen?
im Fall das nur ein element in der besuchten Knotenliste ist, nehme ich aktuell einfach dessen kopf und hole mir über die graphenlisten, alle nachfolger:
List(0) | 1
getPossibleEdges: failed for graph = [example] and visited = 0 (Expected: (0,1,2)|(0,3,1), Found: )
List(0, 3) | 2
getPossibleEdges: failed for graph = [example] and visited = 0|3 (Expected: (0,1,2)|(3,4,1), Found: (3,1,2)|(3,2,7)|(3,4,2))
Wie man aber sieht ist warum auch immer beim ersten durchlauf die liste leer (Danke auch hier nochmal an Thomas für die Tests :-)) und erst beim zweiten durchlauf wird sie gefüllt - wenn auch noch nicht korrekt ich weis.
der einzige unterschied zwischen der ersten und der zweiten ausgabe ist, das bei der zweiten eine if-Anweisung vorangestellt ist, wäre jetzt aber nicht davon ausgegangen das es notwendig ist.
Any Hints?
Greets
Exar
edit: fehler gefunden, apply statt take wärs gewesen
Hier ist keine Unterscheidung zwischen einer Liste mit mehreren Elementen und mit einem Element notwenig, es reicht einfach über die Liste der bereits besuchten Knoten zu laufen. Also als grobes Schema sollte das jedem weiterhelfen der noch Probleme hat (und das ist wirklich nahe dran jetzt an meiner Lösung, aber ein paar Elemente gilt es noch zu ergänzen):
for (v <- visNodes; n <- /* hier die Nachfolger von v anhand des übergebenen graph bestimmen */; if (/* hier die Bedingung, dass n noch nicht besucht ist */)) yield /* hier das passende Tupel zurückgeben*/Das ganze entspricht geschachtelten Schleifen und Bedingungen, wie man sie sonst sieht (hier eine an Java angelehnte Syntax):
for (Int v : visNodes) {
for ((Int, Int) n : /* ... */) {
if (/* noch nicht besucht */) {
yield /* ... */
}
}
}Ok ich steige irgendwie nicht durch bei der mst.
mst erwartet ja als eingabe die Rückgabe von getPossibleEdges und dazu einen Int wert mit dem startknoten, wie es ja auch das beispiel zeigt, die frage ist aber was übergebe ich an gPE als Input, den grpahen selbst habe ich ja nicht zur Verfügung und die besuchten Liste muss ich natürlich erstellen, soweit ist klar.
Was kann man machen wenn man da einfach nicht weiterkommt und einfach nur das Aufgabenblatt ausdrucken und feierlich verbennen will, weil die Motivation gegen NULL geht? 
[m]mst[/m] erwartet als erstes Argument eine Funktion, die eine Liste von Knoten nimmt und eine Liste von 3-Tupeln (Kanten in der Form (Von, Nach, Kosten)) zurückgibt. Diese Funktion berechnet im Prinzip für eine Liste von schon besuchten Knoten die Liste aller Kanten, die von den besuchten Knoten zu unbesuchten führen. Hier sollte jetzt die erste Einsicht kommen: Diese Funktion, nennen wir sie mal [m]f[/m], hat die gleiche Signatur wie der Teil von [m]getPossibleEdges[/m] ab dem ersten [m]=>[/m] (und soll auch das Gleiche tun). Wenn wir also die Funktion [m]f[/m] aus [m]getPossibleEdges[/m] ableiten können, haben wir das nötige [m]f[/m]. [m]getPossibleEdges[/m], und das ist wichtig, brauchen wir dann gar nicht mehr in [m]mst[/m] (und soll auch dort nicht verwendet werden). Wir holen uns einfach solange mit [m]f[/m] mögliche Kanten, bis keine mehr möglich sind (und ergo die leere Liste zurückgegeben wird).
Schauen wir uns nochmal genau die Signatur von [m]getPossibleEdges[/m] an: [m]getPossibleEdges: List[List[(Int, Int)]] => List[Int] => List[(Int, Int, Int)][/m]. Man kann diese Signatur auch vollständig klammern, dann erhält man die äquivalente Signatur [m]getPossibleEdges: (List[List[(Int, Int)]] => (List[Int] => List[(Int, Int, Int)]))[/m]. Das bedeutet, dass [m]getPossibleEdges[/m] also eine Funktion ist, die eine Liste von Listen als (einziges) Argument nimmt, und eine weitere Funktion zurückgibt, die wiederum eine Liste von Ints nimmt. Das verdeutlicht auch die Art und Weise, wie man in Scala diese Funktion aufruft: [m]getPossibleEdges(g)(List(1, 2, 3))[/m]. Wenn wir aber eine Funktion haben, die eine andere Funktion zurückgibt, müssen wir diese Funktion ja gar nicht bis zum bitteren Ende auswerten, sondern können zum Beispiel auch nur die erste Parameterliste befüllen, z.B. so: [m]getPossibleEdges(g)[/m]. Aus vollständig geklammerter Signatur oben folgt, dass wir nun eine Funktion der Form [m]List[Int] => List[(Int, Int, Int)][/m] als Ergebnis dieses Funktionsaufrufs erhalten. Und diese Funktion hat, das sollte die zweite wichtige Einsicht sein, die gleiche Signatur wie die Funktion [m]f[/m] von vorhin.
Wenn wir dann noch aufs Aufgabenblatt schauen, finden wir im Beispiel folgenden Aufruf: [m]mst(getPossibleEdges(g))(0)[/m]. Wie in vorherigem Absatz erklärt, wird also [m]getPossibleEdges[/m] partiell ausgewertet an [m]mst[/m] übergeben, um so die Funktion [m]f[/m] zu bilden. Das Konzept der partiellen Auswertung zu verstehen ist sicherlich nicht einfach, aber ein wichtiger Bestandteil vieler funktionaler Sprachen. Wenn man die [m]Prim[/m]-Aufgabe verstanden und gelöst hat, hat man höchstwahrscheinlich auch das ganze Konzept durchschaut.
to mkmdl
wie kann man dann auf das Ergebnis dieser Funktion f zugreifen?
zmb
def funcx: ( List[Int] => List[(Int, Int)], Int) => Int = {
case (x,y) => …
}
// x das ist übergebene Function List[Int] => List[(Int, Int)] wie kann ich dann mit dem Ergebnis dieser Funktion arbeiten? x => ??? || x.???
In diesem Fall einfach [m]x[/m] aufrufen, als wäre sie mit [m]def[/m] irgendwo sichtbar definiert, z.B. so: [m]x(List(1, 2, 3))[/m].
kurz und knapp ich checks net…
ich brauch aufjedenfall irgendwie ne Art Hilfsmethode, die die getPossibleEdges “ersetzt”, prinzipiell das selbe tut und auch das selbe zurückliefert?!
Wie soll aber die Hilfsmethode ohne Graphen die Nachfolger bestimmen, kann nicht einfach irgendwas zurückgeben, was nicht da ist.
Aus dem langen Beitrag von @mkmdl sollte man doch zumindest zu einer Erkenntnis gelangt sein: die bei [m]mst[/m] übergebene Funktion kann dazu genutzt werden die infrage kommenden Knoten zu bestimmen, der Graph muss dabei nicht mehr übergeben werden, sondern nur noch die Liste besuchter Knoten. Also ist die Verwendung der Funktion mehr oder weniger trivial (ohne Hilfsfunktion):
def mst: (List[Int] => List[(Int, Int, Int)]) => Int => List[(Int, Int)] = function => start => {
/* hier irgendwo bzw. in Hilfsfunktionen folgendes verwenden */
val possibleEdges = function(visNodes)
}Das reicht aus dank des Funktionskonzeptes von Scala, wie es im Beitrag von @mkmdl eh schon ausführlich beschrieben ist. Die ganze Magie der Funktion (a.k.a. wieso funktioniert dieser Aufruf ohne Graph) liegt darin, dass dieser schon in der übergebenen Funktion drinsteckt. Der Aufrufer hat sich bereits darum gekümmert, deshalt auch auf dem Übungsblatt der Aufruf:
mst(getPossibleEdges(g))(0)Hier wird offensichtlich eine Funktion übergeben, die den Graphen bereits hat, es ist also nicht mehr notwendig diesen ein weiteres mal zu übergeben innerhalb der [m]mst[/m]-Methode (zumal dieser nicht an sie direkt übergeben wird). Denk dir das einfach so, als hätte sich jemand die Mühe gemacht extra für diesen einen übergebenen Graphen eine eigene Funktion zu schreiben, die die Nachfolgeknoten bestimmt. Diese Mühe nimmt allerdings Scala ab, da sie (funktions)intern den Graphen mitschleppt damit die übergebene Funktion die Knoten korrekt bestimmen kann.
Ich versuch’s noch einmal mit einem ganz einfachen Beispiel. Führe das am besten direkt in der REPL aus, um alle Schritte nachzuvollziehen. Nehmen wir an, wir haben eine Funktion [m]add[/m], die zwei Zahlen addiert:
def add: Int => Int => Int = a => b => a + bDiese können wir ja jetzt z.B. so aufrufen [m]add(1)(2)[/m]. Was passiert jetzt aber, wenn wir nur eine Parameterliste (ein Klammerpaar) übergeben? Schauen wir uns das mal in der REPL an:
scala> add(1)
res0: Int => Int = <function1>Aha, das funktioniert also und das Ergebnis ist eine Funktion. Schauen wir mal, was diese Funktion macht:
scala> val inc = add(1)
scala> inc(41)
res1: Int = 42Diese Funktion, die ich jetzt schon mal treffenderweise als Konstante [m]inc[/m] hinterlegt habe, addiert also 1 zum übergebenen Argument. Also macht sie im Prinzip das, was [m]add[/m] tut, wenn man als erstes Argument 1 übergibt und als zweites Argument dasjenige Argument, das man [m]inc[/m] übergeben hat. Tatsächlich ist die in [m]inc[/m] gespeicherte Funktion auch eine Funktion, die das gleiche wie [m]add[/m] tut, aber sich so verhält, als wäre das erste Argument fest mit 1 verdrahtet.
Definieren wir uns jetzt nochmal eine weitere Funktion:
def twice: (Int => Int) => Int => Int = f => x => f(f(x))Diese Funktion nimmt in der ersten Parameterliste eine weitere Funktion [m]f[/m], die ein [m]Int[/m] nimmt und ein [m]Int[/m] zurückgibt, und in der zweiten Parameterliste ein [m]Int[/m], welches den Namen [m]x[/m] erhält. Die Funktion [m]f[/m] wird dann zweimal aufgerufen.
Was passiert jetzt, wenn wir unsere Funktion [m]inc[/m] an [m]twice[/m] übergeben?
scala> twice(inc)(2)
res2: Int = 4Das war erwartungsgemäß. Wenn man zweimal die 2 um 1 erhöht, erhält man 4. Statt [m]inc[/m] zu übergeben, können wir aber auch [m]add[/m] partiell auswerten (was wir schon gemacht haben, als wir [m]inc[/m] definiert haben):
scala> twice(add(47))(11) == 47 + 47 + 11
res3: Boolean = trueDie Funktion [m]twice[/m] kennt an keiner Stelle die 47 (oder die 1 im vorherigen Beispiel). Wie gesagt, wird beim Verwenden von [m]add(47)[/m] eine neue Funktion auf der Basis von [m]add[/m] erzeugt, in der die 47 fest eingebaut ist. Und genauso verhält es sich bei [m]getPossibleEdges(g)[/m]. Auch hier wird der Graph direkt in die neue Funktion eingebaut, so dass [m]mst[/m] die Darstellung des Graphen nicht kennen muss. Das hat den Vorteil, dass man [m]mst[/m] nur einmal schreiben muss, aber mit beliebigen Graphrepräsentationen verwenden kann, vorausgesetzt, man hat eine passende Variante von [m]getPossibleEdges[/m] zur Hand.