When accumulating a collection (just collection, not list) of values into a single value, there are two options.
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.
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.)
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)
.