f# - Ejemplo de la diferencia entre List.fold y List.foldBack

folding

Question

Mi comprensión de la diferencia entre List.fold y List.foldBack es que foldBack itera sobre su lista en orden inverso. Ambas funciones acumulan un resultado de los elementos en la lista.

Tengo problemas para encontrar un buen ejemplo en el que sea preferible doblarVolver sobre una lista. En los ejemplos que he encontrado, los resultados son los mismos para fold y foldback, si la lógica de función hace lo mismo.

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

La respuesta de Tarmil ya ha demostrado la diferencia entre los dos de una manera buena y concisa. Voy a dar un ejemplo que usa un tipo de datos algo más complejo. (En realidad, si ignoras el nombre, mi ejemplo es una lista vinculada, pero puedes imaginar cómo se podría expandir a algo mucho más complejo).

El propósito de fold vs. foldBack no es necesariamente obvio cuando se calcula un valor escalar, pero cuando comienzas a usarlo para construir estructuras de datos, queda claro que la mayoría de esas estructuras deben construirse en una dirección particular. Esto es especialmente cierto si usa estructuras de datos inmutables, ya que no tiene la opción de construir un nodo y luego actualizarlo para apuntar a otro nodo.

En este ejemplo, he definido una estructura para un lenguaje de programación trivial que no hace más que imprimir números. Reconoce dos instrucciones, Print y End . Cada instrucción de impresión almacena un puntero a la siguiente instrucción. Por lo tanto, un programa consiste en una cadena de instrucciones, cada una apuntando a la siguiente. (La razón por la que he usado este ejemplo en particular es porque, al ejecutar el programa, demuestras su estructura).

El programa usa tres métodos diferentes para construir el programa a partir de una lista de enteros. El primero, make_list_printer , se define recursivamente sin pliegue, para demostrar lo que estamos tratando de lograr. El segundo, make_list_printer_foldBack , usa foldBack para lograr el mismo resultado. El tercero, make_list_printer_fold , usa fold para demostrar cómo produce el resultado incorrecto.

En su mayoría, he codificado en OCaml, no en F #, así que me disculpo si algunas de las convenciones de codificación que se utilizan a continuación no se consideran estilo correcto en F #. Lo probé en el intérprete F #, sin embargo, y funciona.

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

El resultado que obtengo cuando ejecuto esto es:

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

Answer 2

No ve una diferencia en su ejemplo porque eligió una función tal que para cualquier x1 y x2 :

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

Por lo tanto, no importa en qué orden vaya a la lista, obtendrá el mismo resultado.

La construcción de lista es un ejemplo de función para la cual no es el caso:

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

Entonces, lo siguiente arrojará resultados diferentes:

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 comienza con una lista de resultados vacía y avanza a través de la entrada, agregando cada elemento al frente de la lista de resultados; por lo tanto, el resultado final está en el orden inverso.

List.foldBack , por otro lado, retrocede en la entrada; por lo que cada elemento recién agregado al frente de la lista de resultados estaba en primer plano en la lista original. Entonces, el resultado final es la misma lista que el original.