Why is the signature of foldBack so much different from fold in F#?

Question

There are at least 2 things I don't understand about it:

• refactoring from left side to right side folding requires a lot of changes not only in signature but in every place depended on the folder function
• there is no way to chain it with regard to the list without flipping the parameters

List.foldBack : ('T -> 'State -> 'State) -> 'T list -> 'State -> 'State

List.fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State

Any good reason for why would someone put all parameters in reverse in the signature of foldBack compared to fold?

Answer 1

It's just a useful mnemonic to help the programmer remember how the list is iterated. Imagine your list is laid out with the beginning on the left and the end on the right. fold starts with an initial state on the left and accumulates state going to right. foldBack does the opposite, it starts with an initial state on the right and goes back over the list to the left.

This is definitely showing F#'s OCaml heritage as some other functional languages (Haskell, Scala, ML) keep the list as the last argument to allow for the more common partial application scenarios.

If I really needed a version of foldBack that looked exactly like fold, I would define my own helper function:

module List = 
  let foldBack' f acc lst =
    let flip f a b = f b a
    List.foldBack (flip f) lst acc

Answer 2

It's a relic of F#'s beginnings in OCaml. You can see that the F# function signatures for List.fold and List.foldBack are the same in the OCaml documentation (where they are called List.fold_left and List.fold_right, respectively).