Пример разницы между List.fold и List.foldBack

Мое понимание разницы между List.fold и List.foldBack заключается в том, что foldBack выполняет итерацию по списку в обратном порядке. Обе функции накапливают результат из элементов в списке.

У меня возникли проблемы с хорошим примером, где лучше сбросить список. В примерах, которые я придумал, результаты одинаковы для fold и foldBack, если логика функций делает то же самое.

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

Ответ 1

Вы не видите разницы в вашем примере, потому что вы выбрали такую функцию, что для любых x1 и x2:

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

Итак, неважно, в каком порядке вы проходите список, вы получите тот же результат.

Конструкция списка - это пример функции, для которой это не так:

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

Таким образом, следующие результаты будут иметь разные результаты:

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 начинается с пустого списка результатов и идет вперед через вход, добавляя каждый элемент в начало списка результатов; поэтому конечный результат в обратном порядке.

List.foldBack, с другой стороны, идет назад через вход; поэтому каждый элемент, недавно добавленный к фронту списка результатов, сам был в начале в исходном списке. Итак, конечный результат - тот же список, что и оригинал.

Ответ 2

Ответ Tarmil уже продемонстрировал разницу между ними в хорошем, сжатом виде. Я приведу пример, который использует несколько более сложный тип данных. (На самом деле, если вы игнорируете имя, то мой пример - это связанный список, но вы можете себе представить, как его можно расширить до чего-то более сложного.)

Цель fold vs. foldBack не обязательно очевидна при вычислении скалярного значения, но когда вы начинаете использовать его для построения структур данных, становится ясно, что большинство таких структур должны быть построены в особое направление. Это особенно актуально, если вы используете неизменяемые структуры данных, так как у вас нет возможности построить node, а затем обновить его, чтобы указать на другой node.

В этом примере я определил структуру для тривиального языка программирования, который ничего не делает, кроме номеров печати. Он распознает две инструкции: Print и End. Каждая команда печати содержит указатель на следующую команду. Таким образом, программа состоит из цепочки инструкций, каждая из которых указывает на следующую. (Причина, по которой я использовал этот конкретный пример, состоит в том, что, выполняя программу, вы демонстрируете ее структуру.)

Программа использует три разных метода построения программы из списка целых чисел. Первый, make_list_printer, определяется рекурсивно без фонового изображения, чтобы продемонстрировать, чего мы пытаемся достичь. Второй, make_list_printer_foldBack, использует foldBack для достижения того же результата. Третий, make_list_printer_fold, использует fold, чтобы продемонстрировать, как он производит неверный результат.

Я больше всего кодировал в OCaml, а не F #, поэтому прошу прощения, если некоторые из приведенных ниже правил кодирования на самом деле не считаются правильным стилем в F #. Я тестировал его в интерпретаторе F #, но он работает.

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

Результат, который я получаю при запуске, это:

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