List.fold 和 List.fold 之间的区别示例返回

Question

我对 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

Answer 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 向后遍历输入；所以每个新添加到结果列表前面的元素本身就是原始列表中的前面。所以最后的结果和原来的一样。

Answer 2

Tarmil 的回答已经很好、简洁地展示了两者之间的区别。我将举一个使用稍微复杂一些的数据类型的例子。（实际上，如果您忽略命名，那么我的示例是一个链表，但您可以想象如何将它扩展为更复杂的东西。）

当您计算标量值时，fold 与 foldBack 的目的并不明显，但是当您开始使用它来构建数据结构时，很明显大多数此类结构必须按特定方向建造。如果您使用不可变数据结构，则尤其如此，因为您没有构建节点然后更新它以指向另一个节点的选项。

在这个例子中，我为一种简单的编程语言定义了一个结构，它除了打印数字外什么都不做。它识别两条指令，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

List.fold 和 List.fold 之间的区别示例返回

Example of the difference between List.fold and List.foldBack

f#

folding

fold