Definition of a “fold” in programming

I was just updating my Scala fold/reduce tutorial, and noticed that I start with this definition of a fold in computer programming from the excellent book, Learn You a Haskell for Great Good:

Folds can be used to implement any function where you traverse a list once, element by element, and then return something based on that. Whenever you want to traverse a list to return something, chances are you want a fold. That’s why folds are, along with maps and filters, one of the most useful types of functions in functional programming.”

That’s a great definition because it includes (almost) everything, so I’ll add this:

  • You traverse an entire list, once
  • Element by element
  • You apply your own custom algorithm to the elements as you traverse the list
  • In the end, you return a single value based off of that traversal and the application of your algorithm

If you’re interested in the definition of a fold in computer programming, I hope that’s helpful. See my fold/reduce tutorial for many more details.