UoL CS Notes
Menu

Lecture 16-1

COMP105 Lectures

Fold

Some functions take lists and turn them into a single value. This type of computation is called a fold. The things that you can change are:

  • The base case.
  • The operation applied to the list.

foldr

foldr' :: (a -> b -> b) -> b -> [a] -> b

foldr' _ init [] = init
foldr' f init (x:xs) = f x (foldr' f init xs)

> foldr' (+) 0 [1..10]
> 55

> foldr' (*) 1 [1..10]
> 3628800

The Folded Function

sum'' list = foldr (\ x acc -> acc + x) 0 list

The folded function f takes two arguments:

  • x is an element form the list.
  • acc is the accumulator.

The function outputs a new value for the accumulator:

  • The initial value for the accumulator is init.
  • The final value for the accumulator is the output of foldr.
Example
foldr (\ x acc -> acc + x) 0 [1,2,3,4]

Values for the accumulator:

init	= 0
0 + 4	= 4
4 + 3	= 7
7 + 2	= 9
9 + 1	= 10

Final output: 10

An Imperative Equivalent:

foldr f init input_list

In python this would be implemented as:

acc = init
input_list.reverse()

for i in range(len(input_list)):
	acc = f(input_list[i], acc)

return acc

foldr Examples

Whenever you fold a binary operator you are putting that operator in-between each element on the list. If you are using foldr then you will put the initial value on the right hand side.

concat' list = foldr (++) [] list

> concat' ["Hello ", "there."]
> "Hello there."

all' list = foldr (&&) True list

> all' [True, True, True]
> True

length' list = foldr (\ _ acc -> acc + 1) 0 list

> length' [1,2,3,4]
> 4

This example shows that you just need to apply a function to the accumulator for each element in the list. It doesn’t need to be specifically including items in the list:

count_ones list = foldr (\ x acc -> if x == 1 then acc + 1 else acc) 0 list

> count_ones [1,1,2,3,1,4]
> 3

Exercises

  1. any' list = foldr (||) False list
  2. countEs string = foldr (\ x acc -> if x == 'e' then acc + 1 else acc) 0 string
  3. sumOfEvens list = foldr (\ x acc -> if even x then acc + x else acc) 0 list