Ist das eine korrekte Art, die Haskell-Foldr-Funktion zu schreiben?

Question

Ich machte die Übungen von YAHT's Recursive Datatype Abschnitt, und fand das Schreiben der listFoldr Funktion ein bisschen schwierig (vor allem, weil ich den Unterschied zwischen foldl und foldr auf den ersten nicht wirklich verstanden habe). 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 

Dies 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 solution für die Ausübung gegeben ist ganz 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 falsch? (In meinen Tests enden beide mit genau dem gleichen Ergebnis ...)

Answer 1

Ich denke, du verarbeitest die Elemente in der 'umgekehrten Reihenfolge', und deshalb ist deine nicht richtig.

Sie sollten dies anhand eines Beispiels demonstrieren können, in dem "die Bestellung wichtig ist". Zum Beispiel, so etwas wie

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

wo 'f' ist eine Funktion entlang der Linien von

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

wo '@' ist ein String-Append-Operator (ich vergessen, was es in Haskell ist). Der Punkt besteht nur darin, die Funktion zu "instrumentieren", so dass Sie sehen können, welche Reihenfolge mit den verschiedenen Argumenten aufgerufen wird.

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

Answer 2

Dein ist gebrochen. Versuchen Sie es mit etwas, das nicht mit einem einzelnen numerischen Ergebnis endet.

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

Sie arbeiten in die falsche Richtung.

Answer 3

Ihre Lösung ist definitiv falsch. Sie haben einfach eine foldl implementiert, in der die Funktion f Argumente in umgekehrter Reihenfolge übernimmt. Zum Beispiel, was falsch ist, foldr (:) [] soll eine Identifizierungsfunktion für Listen sein, aber Ihre Funktion kehrt die Liste um. Es gibt viele andere Gründe, warum Ihre Funktion nicht foldr ist, wie foldr auf unendliche Listen funktioniert und Ihre nicht funktioniert. Es ist ein reiner Zufall, dass sie in Ihrem Beispiel gleich sind, denn 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)). Ich denke du solltest von vorne anfangen und schauen, wie foldr funktionieren soll.

Answer 4

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

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

während foldr sollte

berechnen berechnet

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

(, listFoldr f = foldl (flip f). Im Vergleich dazu foldl berechnet

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

Im Wesentlichen)

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 nichtkommutative und nicht-assoziativ ist (dh Argument und Anwendung Ordnung), damit Sie sicher sein können, dass der Ausdruck korrekt ausgewertet wird. Natürlich ist die Subtraktion nicht-kommutativ und nicht-assoziativ und du hast gerade Pech gehabt.