List.fold和List.foldBack之间的区别示例

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

你没有看到你的例子有什么不同,因为你选择了一个函数,对于any 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）的回答已经很好，简洁地证明了两者之间的区别。我将举一个使用稍微复杂一些的数据类型的例子。（实际上，如果您忽略命名，那么我的示例是一个链表，但是您可以想象如何将其扩展为更复杂的东西。）

在计算标量值时，foldvs 。的目的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