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?

Solution 1

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]

Solution 2

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.

Solution 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]

Solution 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]

View more solutions