f# - Example of the difference between List.fold and List.foldBack

Question

My understanding of the difference between List.fold and List.foldBack is that foldBack iterates over its list in a reverse order. Both functions accumulate a result from the items in the list.

I'm having trouble coming up with a good example where it is preferable to foldBack over a list. In the examples I have come up with, the results are the same for both fold and foldBack, if the function logic does the same thing.

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

You don't see a difference in your example because you chose a function such that for any x1 and x2:

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

So it doesn't matter in what order you go through the list, you will get the same result.

List construction is an example of function for which it is not the case:

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

So the following will yield different results:

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 starts with an empty result list and goes forward through the input, adding each element to the front of the result list; therefore the final result is in the reverse order.

List.foldBack, on the other hand, goes backward through the input; so each element newly added to the front of the result list was itself to the front in the original list. So the final result is the same list as the original.