Folds as a general concept are called catamorphisms.
Catamorphisms are a means of deconstructing data.
Let's take a look at a function called foldr which means "fold right":
foldr :: (a -> b -> b) -> b -> [a] -> b
-- or
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b`
map and folds have a parallel between them. map applies a function to each member of a list and returns a list, and a fold replaces the cons constructors with the function and reduces the list.
We call foldr the "right fold" because the fold is right associative.
If we change the semantics of foldr it'll make it easier to work with:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z xs =
case xs of
[] -> z
(x:xs) -> f x (foldr f z xs)
If we take the example foldr (+) 0 [1,2,3]:
foldr (+) 0 [1,2,3] =
case [1,2,3] of
[] -> 0,
(1 : [2, 3]) -> f 1 (foldr f 0 [2,3])
-- next
foldr (+) 0 [2,3] =
case [2,3] of
[] -> 0 -- didn't match again
(2 : [3]) -> f 2 (foldr f 0 [3]) -- there is an implicitly wrapped (+) 1 around this
-- next
foldr (+) 0 [3]
case [3] of
[] -> 0 -- no match
(3 : []) -> (+) 3 (foldr (+) 0 [])
foldr (+) 0 [] =
case [] of
[] -> 0 -- matched
-- started with:
1 + (2 + (3 + 0))
-- ended with:
6
Folds must recurse over the spine of a list from the beginning to the end.
Left folds traverse the spine in the same direction as right folds, but their folding process is left associative and proceeds in the opposite direction as that of foldr.
Here is the definition of foldl:
foldl :: (b -> a -> b) -> b -> [a] -> b
Given the list [1,2,3]:
-- associates like this
((0 + 1) + 2) + 3
When we write folds, we need to first think about the start value for the fold. This is usually the identity value for the function.
For example, when we sum the elements of a list, the identity of summation is 0.
When we multiply the elements of a list, the identity is 1.
This start value can also act as a fall-back in the case where the list is empty.
Next, we consider the arguments a and b. a is always going to be one of the elements in the list and b is either the start value or the value accumulated as the list is being processed.
Learn You a Haskell - http://learnyouahaskell.com/types-and-typeclasses
Haskell Book - https://haskellbook.com/