Beispiel für den Unterschied zwischen List.fold und List.foldBack

Question

Mein Verständnis des Unterschieds zwischen List.fold und List.foldBack ist, dass FoldBack in umgekehrter Reihenfolge über seine Liste iteriert. Beide Funktionen akkumulieren ein Ergebnis aus den Elementen in der Liste.

Ich habe Probleme mit einem guten Beispiel, wo es besser ist, foldBack über eine Liste. In den Beispielen, die ich mir ausgedacht habe, sind die Ergebnisse sowohl für fold als auch für foldBack gleich, wenn die Funktionslogik dasselbe tut.

[<Fact>] 
let ``List.foldBack accumulating a value from the right to the left``() = 
    let list = [1..5]  
    let fFoldBack x acc = 
     acc - x 

    let fFold acc x = 
     acc - x 

    let foldBackResult = List.foldBack fFoldBack list 0 
    let foldResult = List.fold fFold 0 list 

    Assert.Equal(-15, foldBackResult) // 0 - 5 - 4 - 3 - 2 - 1 
    Assert.Equal(-15, foldResult) //  0 - 1 - 2 - 3 - 4 - 5 

Answer 1

Sie keinen Unterschied in Ihrem Beispiel, weil Sie eine Funktion gewählt, so dass für jeden x1 und x2:

(acc - x1) - x2 = (acc - x2) - x1 

So ist es nicht in egal welcher Reihenfolge Sie die durch Liste, erhalten Sie das gleiche Ergebnis.

Liste Konstruktion ist ein Beispiel für Funktion, für die es nicht der Fall ist:

x1 :: (x2 :: acc) <> x2 :: (x1 :: acc) 

So wird folgendes ergeben unterschiedliche Ergebnisse:

List.fold (fun acc x -> x :: acc) [] [1; 2; 3; 4; 5] 
// val it : int list = [5; 4; 3; 2; 1] 

List.foldBack (fun x acc -> x :: acc) [1; 2; 3; 4; 5] [];; 
// val it : int list = [1; 2; 3; 4; 5] 

List.fold beginnt mit einer leeren Ergebnisliste und geht Weiterleiten durch die Eingabe, Hinzufügen jedes Elements zur Vorderseite der Ergebnisliste; daher ist das Endergebnis in umgekehrter Reihenfolge.

List.foldBack, auf der anderen Seite, geht rückwärts durch den Eingang; Jedes Element, das neu an der Vorderseite der Ergebnisliste hinzugefügt wurde, war also selbst in der ursprünglichen Liste nach vorne. Das Endergebnis ist also die gleiche Liste wie das Original.

Answer 2

Tarmil's Antwort hat bereits den Unterschied zwischen den beiden auf eine gute, prägnante Art und Weise gezeigt. Ich werde ein Beispiel geben, das einen etwas komplexeren Datentyp verwendet. (Eigentlich, wenn Sie die Namensgebung dann mein Beispiel ignorieren ist eine verknüpfte Liste, aber man kann sich vorstellen, wie es um etwas viel komplexer erweitert werden könnte.)

Der Zweck fold vs. foldBack nicht unbedingt offensichtlich ist Wenn Sie einen skalaren Wert berechnen, aber wenn Sie damit beginnen, Datenstrukturen zu erstellen, wird klar, dass die meisten dieser Strukturen in eine bestimmte Richtung gebaut werden müssen. Dies gilt insbesondere, wenn Sie unveränderliche Datenstrukturen verwenden, da Sie nicht die Möglichkeit haben, einen Knoten zu erstellen und ihn dann so zu aktualisieren, dass er auf einen anderen Knoten zeigt.

In diesem Beispiel habe ich eine Struktur für eine triviale Programmiersprache definiert, die nur Zahlen ausgibt. Es erkennt zwei Anweisungen, Print und End. Jeder Druckbefehl speichert einen Zeiger auf den nächsten Befehl. Ein Programm besteht also aus einer Kette von Anweisungen, die jeweils zum nächsten zeigen. (Der Grund, warum ich dieses spezielle Beispiel verwendet habe, ist, dass Sie durch Ausführen des Programms seine Struktur demonstrieren.)

Das Programm verwendet drei verschiedene Methoden, um das Programm aus einer Liste von Ganzzahlen zu konstruieren. Der erste, make_list_printer, wird rekursiv ohne Faltung definiert, um zu demonstrieren, was wir erreichen wollen. Der zweite, make_list_printer_foldBack, verwendet foldBack, um das gleiche Ergebnis zu erzielen. Der dritte, make_list_printer_fold, verwendet fold, um zu demonstrieren, wie es das falsche Ergebnis erzeugt.

Ich habe meistens in OCaml codiert, nicht F #, so dass ich entschuldige mich, wenn einige der Codierung Konventionen unten verwendet werden, nicht wirklich stilecht in F # berücksichtigt. Ich habe es allerdings im F # -Interpreter getestet und es funktioniert.

(* Data structure of our mini-language. *) 
type prog = 
| End 
| Print of int * prog 

(* Builds a program recursively. *) 
let rec make_list_printer = function 
| [] -> End 
| i :: program -> Print (i, make_list_printer program) 

(* Builds a program using foldBack. *) 
let make_list_printer_foldBack ints = 
    List.foldBack (fun i p -> Print (i, p)) ints End 

(* Builds a program in the wrong direction. *) 
let make_list_printer_fold ints = 
    List.fold (fun p i -> Print (i, p)) End ints 

(* The interpreter for our mini-language. *) 
let rec run_list_printer = function 
| End -> 
    printfn "" 
| Print (i, program) -> 
    printf "%d " i; 
    run_list_printer program 

(* Build and run three different programs based on the same list of numbers. *) 
let() = 
    let base_list = [1; 2; 3; 4; 5] in 
    let a = make_list_printer   base_list in 
    let b = make_list_printer_foldBack base_list in 
    let c = make_list_printer_fold  base_list in 
    run_list_printer a; 
    run_list_printer b; 
    run_list_printer c 

Die Ausgabe, die ich bekomme, wenn ich laufe dies:

1 2 3 4 5 
1 2 3 4 5 
5 4 3 2 1