Ich nehme eine Klasse in Haskell, und wir müssen die Faltungsoperation für einen Baum definieren, der definiert ist durch:
%Vor%Ich kann anscheinend keine Informationen über die "tfold" -Operation finden oder wirklich, was sie tun sollte. Jede Hilfe würde sehr geschätzt werden.
Ich denke immer an Falten als einen Weg, Konstruktoren systematisch durch andere Funktionen zu ersetzen. Wenn Sie zum Beispiel einen do-it-yourself List -Typ haben (definiert als data List a = Nil | Cons a (List a) ), kann die entsprechende Faltung wie folgt geschrieben werden:
oder, vielleicht prägnanter, als:
%Vor% Der Typ von listfold ist b -> (a -> b -> b) -> List a -> b . Das heißt, es braucht zwei Ersatzkonstruktoren; einer sagt, wie ein Nil -Wert in ein b , ein anderer Ersetzungskonstruktor für den Cons -Konstruktor umgewandelt werden soll, wie der erste Wert des Cons -Konstruktors (vom Typ a ) mit a kombiniert werden soll Wert des Typs b (warum b ? weil die Faltung bereits rekursiv angewendet wurde!), um eine neue b und schließlich eine List a zu erhalten, auf die der gesamte Shebang angewendet wird - mit einem Ergebnis von b .
In Ihrem Fall sollte die Art von tfold durch analoge Argumentation (a -> b) -> (b -> b -> b) -> Tree a -> b sein; Hoffentlich kannst du es von dort aus nehmen!
Stellen Sie sich vor, Sie definieren, dass ein Baum in der folgenden Weise angezeigt werden soll, z. B .: "<1#<<2#3>#<4#5>>>" . Das Falten eines solchen Baums bedeutet das Ersetzen jedes Verzweigungsknotens durch eine tatsächlich gelieferte Operation, die an den Ergebnissen der rekursiv durchgeführten Faltung an den Bestandteilen des Datentyps (hier die zwei untergeordneten Knoten des Knotens, die jeweils selbst sind) durchgeführt wird , ein Baum), zum Beispiel mit + , produziert (1+((2+3)+(4+5))) .
Für Blätter sollten Sie einfach die Werte in ihnen nehmen, und für Zweige rekursiv die Falte für jedes der beiden anwenden, und kombinieren die zwei Ergebnisse mit der angegebenen Funktion, die mit wo der Baum gefaltet ist. ( edit: ) Wenn Sie Werte aus Blättern übernehmen, können Sie sie zusätzlich transformieren, indem Sie eine unäre Funktion anwenden. Im Allgemeinen benötigt Ihre Faltung daher zwei zwei benutzerdefinierte Funktionen, eine für Blätter und eine weitere, um die Ergebnisse der rekursiven Faltung der Bestandteile von Zweigen
Ihr Baumdatentyp könnte anders definiert sein, z. mit möglicherweise leeren Blättern und mit internen Knoten, die auch die Werte tragen. Dann müssten Sie einen Standardwert angeben, der anstelle von leeren Blattknoten verwendet werden soll, und eine dreifache Kombinationsoperation.
Ein weiterer Unterschied, den Sie hier erkennen können, ist was Sie falten und wie Sie es falten. I.e. Du könntest deinen Baum auf eine lineare Weise falten, (1+(2+(3+(4+5)))) , oder du könntest eine lineare Liste in baumartiger Weise falten. Es geht darum, wie Sie den resultierenden "Ausdruck" in Klammern setzen. In der klassischen Faltung folgt natürlich die Struktur der Exression der Struktur der gefalteten Datenstruktur; aber Variationen existieren . Beachten Sie auch, dass die Kombinationsoperation möglicherweise nicht streng ist und dass sie Verbindung und atomare Werte konsumieren / produzieren kann.
Eine Falte in einer Liste ist eine Reduktion von einer Liste in ein einzelnes Element. Es nimmt eine Funktion und wendet diese Funktion dann auf zwei Elemente an, bis es nur noch ein Element hat. Zum Beispiel:
%Vor%... wird gefunden, indem Operationen nacheinander ausgeführt werden:
%Vor%Eine Falte kann geschrieben werden
%Vor%Eine Baumfalte würde das tun, aber die Zweige des Baumes auf und ab bewegen. Um dies zu tun, muss zuerst eine Musterübereinstimmung gefunden werden, um zu sehen, ob Sie auf einem Blatt oder einer Verzweigung operieren.
%Vor%Der Rest bleibt Ihnen überlassen, da es Hausaufgaben sind. Wenn du nicht weiterkommst, versuche zuerst darüber nachzudenken, was der Typ sein soll.
Eine Faltung ist eine Operation, die eine Datenstruktur unter Verwendung einer Operation zu einem einzigen Wert "komprimiert". Abhängig davon, ob Sie einen Startwert und eine Ausführungsreihenfolge haben (z. B. für Listen haben Sie foldl , foldr , foldl1 und foldr1 ), hängt die korrekte Implementierung von Ihrer Aufgabe ab.
Ich denke, Ihr tfold sollte einfach alle Blätter mit ihren Werten und alle Zweige mit den Anwendungen der gegebenen Operation ersetzen. Zeichne einen Beispielbaum mit einigen Zahlen, ein "Kollaps" gibt ihm eine Operation wie (+) . Danach sollte es einfach sein, eine Funktion zu schreiben, die dasselbe macht.