foldr and foldl further explanations and examples

Question

I've looked at different folds and folding in general as well as a few others and they explain it fairly well.

I'm still having trouble on how a lambda would work in this case.

foldr (\y ys -> ys ++ [y]) [] [1,2,3]

Could someone go through that step-by-step and try to explain that to me?

And also how would foldl work?

Answer 1

foldr is an easy thing:

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

It takes a function which is somehow similar to (:),

(:) :: a -> [a] -> [a]

and a value which is similar to the empty list [],

[] :: [a]

and replaces each : and [] in some list.

It looks like this:

foldr f e (1:2:3:[]) = 1 `f` (2 `f` (3 `f` e))

You can imagine foldr as some state-machine-evaluator, too:

f is the transition,

f :: input -> state -> state

and e is the start state.

e :: state

foldr (foldRIGHT) runs the state-machine with the transition f and the start state e over the list of inputs, starting at the right end. Imagine f in infix notation as the pacman coming from-RIGHT.

foldl (foldLEFT) does the same from-LEFT, but the transition function, written in infix notation, takes its input argument from right. So the machine consumes the list starting at the left end. Pacman consumes the list from-LEFT with an open mouth to the right, because of the mouth (b->a->b) instead of (a->b->b).

foldl :: (b->a->b) -> b -> [a] -> b

To make this clear, imagine the function (-) as transition:

foldl (-) 100 [1]         = 99 = ((100)-1)
foldl (-) 100 [1,2]       = 97 = (( 99)-2) = (((100)-1)-2)
foldl (-) 100 [1,2,3]     = 94 = (( 97)-3)
foldl (-) 100 [1,2,3,4]   = 90 = (( 94)-4)
foldl (-) 100 [1,2,3,4,5] = 85 = (( 90)-5)

foldr (-) 100 [1]         = -99 = (1-(100))
foldr (-) 100 [2,1]       = 101 = (2-(-99)) = (2-(1-(100)))
foldr (-) 100 [3,2,1]     = -98 = (3-(101))
foldr (-) 100 [4,3,2,1]   = 102 = (4-(-98))
foldr (-) 100 [5,4,3,2,1] = -97 = (5-(102))

You probably want to use foldr in situations where the list can be infinite, and where the evaluation should be lazy:

foldr (either (\l ~(ls,rs)->(l:ls,rs))
              (\r ~(ls,rs)->(ls,r:rs))
      ) ([],[]) :: [Either l r]->([l],[r])

And you probably want to use the strict version of foldl, which is foldl', when you consume the whole list to produce its output. It might perform better and might prevent you from having stack-overflow or out-of-memory exceptions (depending on compiler) due to extreme long lists in combination with lazy evaluation:

foldl' (+) 0 [1..100000000] = 5000000050000000
foldl  (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci
foldr  (+) 0 [1..100000000] = error "stack overflow or out of memory" -- dont try in ghci

The first one –step by step– creates one entry of the list, evaluates it, and consumes it.

The second one creates a very long formula first, wasting memory with ((...((0+1)+2)+3)+...), and evaluates all of it afterwards.

The third one is like the second, but with the other formula.

Answer 2

Using

foldr f z []     = z
foldr f z (x:xs) = x `f` foldr f z xs

And

k y ys = ys ++ [y]

Let's unpack:

foldr k [] [1,2,3]
= k 1 (foldr k [] [2,3]
= k 1 (k 2 (foldr k [] [3]))
= k 1 (k 2 (k 3 (foldr k [] [])))
= (k 2 (k 3 (foldr k [] []))) ++ [1]
= ((k 3 (foldr k [] [])) ++ [2]) ++ [1]
= (((foldr k [] []) ++ [3]) ++ [2]) ++ [1]
= ((([]) ++ [3]) ++ [2]) ++ [1]
= (([3]) ++ [2]) ++ [1]
= ([3,2]) ++ [1]
= [3,2,1]

Answer 3

The definition of foldr is:

foldr f z []     = z
foldr f z (x:xs) = f x (foldr f z xs)

So here's a step by step reduction of your example:

  foldr (\y ys -> ys ++ [y]) [] [1,2,3]
= (\y ys -> ys ++ [y]) 1 (foldr (\y ys -> ys ++ [y]) [] [2,3])
= (foldr (\y ys -> ys ++ [y]) [] [2,3]) ++ [1]
= (\y ys -> ys ++ [y]) 2 (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] [3]) ++ [2] ++ [1]
= (\y ys -> ys ++ [y]) 3 (foldr (\y ys -> ys ++ [y]) [] []) ++ [2] ++ [1]
= (foldr (\y ys -> ys ++ [y]) [] []) ++ [3] ++ [2] ++ [1]
= [] ++ [3] ++ [2] ++ [1]
= [3,2,1]

Answer 4

Infix notation will probably be clearer here.

Let's start with the definition:

foldr f z []     = z
foldr f z (x:xs) = x `f` (foldr f z xs)

For the sake of brevity, let's write g instead of (\y ys -> ys ++ [y]). The following lines are equivalent:

foldr g [] [1,2,3]
1 `g` (foldr g [] [2,3])
1 `g` (2 `g` (foldr g [] [3]))
1 `g` (2 `g` (3 `g` (foldr g [] [])))
1 `g` (2 `g` (3 `g` []))
(2 `g` (3 `g` [])) ++ [1]
(3 `g` []) ++ [2] ++ [1]
[3] ++ [2] ++ [1]
[3,2,1]

Answer 5

My way of remembering this firstly, is through the use of an associative sensitive subtraction operation:

foldl (\a b -> a - b) 1 [2] = -1
foldr (\a b -> a - b) 1 [2] = 1

Then secondly , foldl starts at the leftmost or first element of the list whereas foldr starts at the rightmost or last element of the list. It is not obvious above since the list has only one element.

My mnemonic is this: The left or right describes two things:

• the placement of the minus (-) symbol
• the starting element of the list

Answer 6

I tend to remember things with movement, so I imagine and visualize values flying around. This is my internal representation of foldl and foldr.

The diagram below does a few things:

1. names the arguments of the fold functions in a way that is intuitive (for me),
2. shows which end each particular fold works from, (foldl from the left, foldr from the right),
3. color codes the accumulator and current values,
4. traces the values through the lambda function, mapping them onto the next iteration of the fold.

Mnemonically, I remember the arguments of foldl as being in alphabetical order (\a c ->), and the arguments of foldr to be in reverse alphabetical order (\c a ->). The l means take from the left, the r means take from the right.