Ist das ein richtiger Weg, um die Haskell foldr Funktion des Schreibens?

Question

ich mache die Übungen von yaht der rekursive Datentyp Abschnitt, und fand die listFoldr Funktion etwas zu schreiben herausfordernde (vor allem, weil ich nicht wirklich den Unterschied zwischen foldl und foldr zunächst verstehen). Wenn ich genau endlich erkannt, wie die foldr Funktion arbeitete, habe ich beschlossen, dass ein einfacher Tausch von Funktionsargumenten wäre alles, was benötigt würde meine listFoldl Funktion auf eine listFoldr Funktion zu ändern:

listFoldl f i [] = i
listFoldl f i (x:xs) = listFoldl f (f i x) xs

listFoldr f i [] = i
listFoldr f i (x:xs) = listFoldr f (f x i) xs

Das scheint zu funktionieren (ich habe mehr Tests als diese):

Main> foldr (-) 4 [1, 2, 3]
-2
Main> listFoldr (-) 4 [1, 2, 3]
-2

Aber die Lösung gegeben für die Ausübung viel anders als meine. Ihre listFoldl ist genau das gleiche wie meine, aber Blick auf ihre listFoldr:

listFoldr f i [] = i
listFoldr f i (x:xs) = f x (listFoldr f i xs)

Welche Lösung ist besser, meine oder ihre? Ist einer von ihnen nicht richtig? (In meinen Tests, sie beide am Ende mit dem exakt gleichen Ergebnis nach oben ...)

Answer 1

Ich glaube, Sie die Elemente verarbeiten in der ‚umgekehrten Reihenfolge‘, und so ist dein nicht richtig.

Es soll möglich sein, dies mit einem Beispiel zu zeigen, wo ‚bestellen Sachen‘. Zum Beispiel so etwas wie

listfoldr f "" ["a", "b", "c"]

wobei ‚f‘ ist eine Funktion entlang der Linien von

f s1 s2 = "now processing f(" @ s1 @ "," @ s2 @ ")\n"

Dabei steht '@' ist ein String-Append-Operator (ich vergessen, was es in Haskell ist). Der Punkt ist nur zu ‚Instrument‘ die Funktion, so können Sie sehen, welche um es mit den verschiedenen args genannt zu werden.

(Beachten Sie, dass dies nicht in Ihrem Beispiel zeigen, haben, weil die Mathematik „4-1-2-3“ ergibt sich die gleiche Antwort wie „4-3-2-1“).

Answer 2

Ihre Lösung ist definitiv falsch. Sie haben einfach eine foldl in dem die Funktion f nimmt Argumente in umgekehrter Reihenfolge durchgeführt. Zum Beispiel von dem, was falsch ist, wird foldr (:) [] soll eine Identifizierung seiner Funktion auf Listen, aber Ihre Funktion kehrt die Liste. Es gibt viele andere Gründe, warum Ihre Funktion nicht foldr ist, wie, wie foldr arbeitet auf unendliche Listen und Ihnen nicht der Fall. Es ist ein reiner Zufall, dass sie das gleiche in Ihrem Beispiel sind, weil 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)). Ich denke, Sie sollten von vorne anfangen und schauen, wie foldr funktionieren soll.

Answer 3

Mit freundlichen Grüßen ist gebrochen. Versuchen Sie es mit etwas, das nicht mit einem einzigen numerischen Ergebnis enden.

eg: listFoldr (++) "a" ["b", "c", "d"]

Sie sind die Verarbeitung in der falschen Richtung.

Answer 4

Auf einer Liste [x1, x2, ..., xk], Ihre listFoldr puter

 f xk (... (f x2 (f x1 i)) ...)

während foldr sollte berechnen

 f x1 (f x2 (... (f xk i) ...))

(Im Vergleich dazu foldl puter

f (... (f (f i x1) x2) ...) xk

Im Wesentlichen listFoldr f = foldl (flip f).)

Sie sind Testfall ist bedauerlich, weil

3 - (2 - (1 - 4)) = 1 - (2  - (3 - 4))

Wenn Sie Funktionen wie diese testen, müssen Sie in einem f zu übergeben, die nicht-kommutativ ist und nicht assoziativ (das heißt Argument und Anwendung, um Materie), so dass Sie den Ausdruck sicher sein kann, richtig ausgewertet wird. Natürlich Subtraktion ist nichtkommutative und nicht-assoziativ und man einfach Pech bekommt.