Esempio della differenza tra List.fold e List.foldBack

Question

La mia comprensione della differenza tra List.fold e List.foldBack è che foldBack esegue l'iterazione sull'elenco in ordine inverso. Entrambe le funzioni accumulano un risultato dagli elementi nell'elenco.

Sto riscontrando problemi con un buon esempio in cui è preferibile eseguire il foldBack su un elenco. Negli esempi che ho trovato, i risultati sono gli stessi sia per il fold che per il foldBack, se la logica della funzione fa la stessa cosa.

[<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

Non si vede una differenza nel tuo esempio perché si è scelto una funzione tale che per ogni x1 e x2:

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

Quindi non importa in quale ordine si passa attraverso il lista, otterrai lo stesso risultato.

costruzione List è un esempio di funzione per la quale non è il caso:

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

Così quanto segue si producono risultati diversi:

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 inizia con una lista risultato vuoto e si ritrova avanti attraverso l'input, aggiungendo ogni elemento in primo piano nella lista dei risultati; quindi il risultato finale è nell'ordine inverso.

List.foldBack, al contrario, va indietro attraverso l'ingresso; quindi ogni elemento aggiunto di recente nella parte anteriore dell'elenco dei risultati era di per sé in primo piano nell'elenco originale. Quindi il risultato finale è la stessa lista dell'originale.

Answer 2

La risposta di Tarmil ha già dimostrato la differenza tra i due in modo buono e conciso. Fornirò un esempio che utilizza un tipo di dati un po 'più complesso. (In realtà, se si ignora la nomina poi il mio esempio è una lista collegata, ma si può immaginare come potrebbe essere esteso a qualcosa di molto più complesso.)

Lo scopo di fold vs foldBack non è necessariamente evidente quando si calcola un valore scalare, ma quando si inizia a usarlo per costruire strutture dati, diventa chiaro che la maggior parte di tali strutture deve essere costruita in una particolare direzione. Ciò è particolarmente vero se si utilizzano strutture dati immutabili, poiché non si ha la possibilità di costruire un nodo e quindi di aggiornarlo per puntare a un altro nodo.

In questo esempio, ho definito una struttura per un linguaggio di programmazione banale che non fa altro che stampare numeri. Riconosce due istruzioni, Print e End. Ogni istruzione di stampa memorizza un puntatore all'istruzione successiva. Pertanto, un programma consiste in una catena di istruzioni, ciascuna orientata al successivo. (La ragione per cui ho usato questo particolare esempio è perché, eseguendo il programma, ne mostri la struttura.)

Il programma utilizza tre diversi metodi di costruzione del programma da un elenco di numeri interi. Il primo, make_list_printer, è definito in modo ricorsivo senza fold, per dimostrare cosa stiamo cercando di ottenere. Il secondo, make_list_printer_foldBack, utilizza foldBack per ottenere lo stesso risultato. Il terzo, make_list_printer_fold, utilizza fold per dimostrare come produce il risultato errato.

Ho codificato per lo più in OCaml, non in F #, quindi mi scuso se alcune delle convenzioni di codifica utilizzate di seguito non sono realmente considerate come lo stile corretto in F #. L'ho provato con l'interprete F #, e funziona.

(* 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 

L'output che provo quando corro questo è:

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