1

The typical academic example is to sum a list. Are there real world examples of the use of fold that will shed light on its utility ?

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
canadadry
  • 8,115
  • 12
  • 51
  • 68
  • 2
    Are you saying you never had to calculate the sum of a list in the real world? – sepp2k May 04 '12 at 05:48
  • I use python, so to sum a list, I just do `sum(alist)`. Thus, I don't normally need to run fold (or `reduce` in python) to achieve the same effect. – canadadry May 04 '12 at 05:54
  • 2
    Okay, then take the next best thing: finding the product of a list. Python doesn't have that built-in. Of course that's just another very simplistic example. Every time you have a for-loop where the body consists of reassigning a variable, you can replace that with a fold. – sepp2k May 04 '12 at 06:05
  • Other examples are: finding the minimum, the maximum, building a tree or hash-map (from a list of key value pairs) – Ingo May 04 '12 at 06:27
  • 3
    Just about any computation in which you process the elements of a collection to build some result that depends on all of the elements can be expressed as some sort of fold. The utility of the fold functions isn't that they naturally express some particular concrete examples; the most natural concrete folds can be trivially rewritten with other techniques. The utility is that you don't *have* to write each different trivial example, because folding covers *all* of them. – Ben May 04 '12 at 07:44

3 Answers3

8

fold is perhaps the most fundamental operation on sequences. Asking for its utility is like asking for the utility of a for loop in an imperative language.

Given a list (or array, or tree, or ..), a starting value, and a function, the fold operator reduces the list to a single result. It is also the natural catamorphism (destructor) for lists.

Any operations that take a list as input, and produce an output after inspecting the elements of the list can be encoded as folds. E.g.

sum      = fold (+) 0

length   = fold (λx n → 1 + n) 0

reverse  = fold (λx xs → xs ++ [x]) []

map f    = fold (λx ys → f x : ys) []

filter p = fold (λx xs → if p x then x : xs else xs) []

The fold operator is not specific to lists, but can be generalised in a uniform way to ‘regular’ datatypes.

So, as one of the most fundamental operations on a wide variety of data types, it certainly does have some use out there. Being able to recognize when an algorithm can be described as a fold is a useful skill that will lead to cleaner code.

References:

Community
  • 1
  • 1
Don Stewart
  • 137,316
  • 36
  • 365
  • 468
1

Lots And Lots Of foldLeft Examples lists the following functions:

  • sum
  • product
  • count
  • average
  • last
  • penultimate
  • contains
  • get
  • to string
  • reverse
  • unique
  • to set
  • double
  • insertion sort
  • pivot (part of quicksort)
  • encode (count consecutive elements)
  • decode (generate consecutive elements)
  • group (into sublists of even sizes)
thSoft
  • 21,755
  • 5
  • 88
  • 103
0

My lame answer is that:

  • foldr is for reducing the problem to the primitive case and then assembling back up (behaves as a non tail-recursion)
  • foldl is for reducing the problem and assembling the solution at every step, where at the primitive case you have the solution ready (bahaves as a tail recursion / iteration)

This question reminded me immediately of a talk by Ralf Lämmel Going Bananas (as the rfold operator notation looks like a banana (| and |)). There are quite illustrative examples of mapping recursion to folds and even one fold to the other.

The classic paper (that is quite difficult at first) is Functional Programming with Bananas, Lenses,. Envelopes and Barbed Wire named after the look of other operators.

jJ'
  • 3,038
  • 32
  • 25