Search code examples
collectionslanguage-agnosticpipelinetheory

Is there a particular use case for fold() function


When accumulating a collection (just collection, not list) of values into a single value, there are two options.

  1. reduce(). Which takes a List<T>, and a function (T, T) -> T, and applies that function iteratively until the whole list is reduced into a single value.

  2. fold(). Which takes a List<T>, an initial value V, and a function (V, T) -> V, and applies that function iteratively until the whole list is folded into a single value.

I know that both of them have their own use cases. For eg, reduce() can be used to find maximum value in a list and fold() can be used to find sum of all values in a list.

But, in that example, instead of using fold(), you can add(0), and then reduce(). Another use case of fold is to join all elements into a string. But this can also be done without using fold, by map |> toString() followed by reduce().

Just out of curiosity, the question is, can every use case of fold() be avoided given functions map(), filter(), reduce() and add()? (also remove() if required.)


Solution

  • It's the other way around. reduce(L,f) = fold(first(L), rest(L), f), so there's no special need for reduce -- it's just a short form for a common fold pattern.

    fold has lots of use cases of its own, though.

    The example you gave for string concatenation is one of them -- you can fold items into a special string accumulator much more efficiently than you can build strings by incremental accumulation. (exactly how depends on the language, but it's true pretty much everywhere).

    Applying a list of incremental changes to a target object is a pretty common pattern. Adding files to a folder, drawing shapes on a canvas, turning a list into a set, crossing off completed items in a to-do list, etc., are all examples of this pattern.

    Also map(L,f) = fold(newMap(), L, (M,v) -> add(M,f(v)), so map is also just a common fold pattern. Similarly, filter(L,f) = fold(newList(), L, (L,v) -> f(v) ? add(L,v) : L).