Folding

Haskell programmers might refer to them as one of the most important functions in the entire language - folding. The following is the type signature of foldr (fold right):

foldr :: (a -> b -> b) -> b -> [a] -> b
 
foldr (+) 0 [1,2,...,n]
---  => 1+2+...+n+0

Using the above, we can perform operations that involve all the elements of a list. The following are some functions we have seen written using foldr:

sum = foldr (+) 0
and = foldr (&&) True
or = foldr (||) False

The above functions all use predefined operations like +, &&, and ||. However, we can apply custom functions in foldr as well:

foldr (\elem acc -> <term>) <start_acc> <list>
--- <elem>: element in a list
--- acc: accumulator
--- <term>: expressions using elem and/or acc
--- <start_acc>: starting accumulator
--- <list>: list to iterate over
 
count e = foldr (\x acc -> if e == x then acc+1 else acc) 0
--- We start from 0 and add 1 to the accumulator when the element is the same as e, 
--- thereby counting the number of elements in the list that are equal to e.

We can construct previously covered functions using this technique:

length = foldr (\x -> (+) 1) 0
--- add 1 to accumulator for every element
length = foldr (const $ (+) 1) 0
--- if we don't use x for <term>, we can use const. 
 
map = foldr ((:) . f) []
--- apply function f and prepend to a list

Foldr vs Foldl

In addition to foldr, we have foldl:

foldl (\acc elem -> <term>) <start_acc> <list>

What is the difference? It is more intuitive than you might assume. Let's visualize foldr and foldl with an example of sum:

--- foldr
sum [1,2,3] = foldr (+) 0 [1,2,3]
--- 1+(2+(3+0))
 
--- foldl
sum [1,2,3] = foldl (+) 0 [1,2,3]
--- ((1+0)+2)+3

As we can observe from the above, foldr starts its operation on elements and accumulator from the right-hand side of a list, while foldl starts from the left-hand side. If you are an imperative programmer, the following might help understand the difference:

def sum_foldr(nums):
  acc = 0
  for i in range(len(nums)-1, -1, -1):
    acc += nums[i]
  return acc
 
def sum_foldl(nums):
  acc = 0
  for i in range(len(nums)):
    acc += nums[i]
  return acc

In the case of sum, both foldr and foldl could be used, but in many cases, only one of them works.

IMPORTANT: When using folding, use import Prelude hiding (foldr, foldl) and define types of functions manually to avoid errors.

Exercises

This is an exercise section where you can test your understanding of the material introduced in the article. I highly recommend solving these questions by yourself after reading the main part of the article. You can click on each question to see its answer.

Resources

• Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #9 - Folding (foldr, foldl). YouTube.
• Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #11 - Folding Exercises. YouTube.