How does foldr work?

Question

Can anybody explain how does foldr work?

Take these examples:

Prelude> foldr (-) 54 [10, 11]
53
Prelude> foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6]
12.0

I am confused about these executions. Any suggestions?

Answer 1

The easiest way to understand foldr is to rewrite the list you're folding over without the sugar.

[1,2,3,4,5] => 1:(2:(3:(4:(5:[]))))

now what foldr f x does is that it replaces each : with f in infix form and [] with x and evaluates the result.

For example:

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

[1,2,3] === 1:(2:(3:[]))

so

sum [1,2,3] === 1+(2+(3+0)) = 6

Answer 2

foldr begins at the right-hand end of the list and combines each list entry with the accumulator value using the function you give it. The result is the final value of the accumulator after "folding" in all the list elements. Its type is:

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

and from this you can see that the list element (of type a) is the first argument to the given function, and the accumulator (of type b) is the second.

For your first example:

Starting accumulator = 54
11 -   54  = -43
10 - (-43) =  53

        ^  Result from the previous line

 ^ Next list item

So the answer you got was 53.

The second example:

Starting accumulator = 54
(6  + 54) / 2 = 30
(10 + 30) / 2 = 20
(4  + 20) / 2 = 12
(12 + 12) / 2 = 12

So the result is 12.

Edit: I meant to add, that's for finite lists. foldr can also work on infinite lists but it's best to get your head around the finite case first, I think.

Answer 3

It helps to understand the distinction between foldr and foldl. Why is foldr called "fold right"?

Initially I thought it was because it consumed elements from right to left. Yet both foldr and foldl consume the list from left to right.

• foldl evaluates from left to right (left-associative)
• foldr evaluates from right to left (right-associative)

We can make this distinction clear with an example that uses an operator for which associativity matters. We could use a human example, such as the operator, "eats":

foodChain = (human : (shark : (fish : (algae : []))))

foldl step [] foodChain
  where step eater food = eater `eats` food  -- note that "eater" is the accumulator and "food" is the element

foldl `eats` [] (human : (shark : (fish : (algae : []))))
  == foldl eats (human `eats` shark)                              (fish : (algae : []))
  == foldl eats ((human `eats` shark) `eats` fish)                (algae : [])
  == foldl eats (((human `eats` shark) `eats` fish) `eats` algae) []
  ==            (((human `eats` shark) `eats` fish) `eats` algae)

The semantics of this foldl is: A human eats some shark, and then the same human who has eaten shark then eats some fish, etc. The eater is the accumulator.

Contrast this with:

foldr step [] foodChain
    where step food eater = eater `eats` food.   -- note that "eater" is the element and "food" is the accumulator

foldr `eats` [] (human : (shark : (fish : (algae : []))))
  == foldr eats (human `eats` shark)                              (fish : (algae : []))))
  == foldr eats (human `eats` (shark `eats` (fish))               (algae : [])
  == foldr eats (human `eats` (shark `eats` (fish `eats` algae))) []
  ==            (human `eats` (shark `eats` (fish `eats` algae) 

The semantics of this foldr is: A human eats a shark which has already eaten a fish, which has already eaten some algae. The food is the accumulator.

Both foldl and foldr "peel off" eaters from left to right, so that's not the reason we refer to foldl as "left fold". Instead, the order of evaluation matters.

Answer 4

Think about foldr's very definition:

 -- if the list is empty, the result is the initial value z
 foldr f z []     = z                  
 -- if not, apply f to the first element and the result of folding the rest 
 foldr f z (x:xs) = f x (foldr f z xs)

So for example foldr (-) 54 [10,11] must equal (-) 10 (foldr (-) 54 [11]), i.e. expanding again, equal (-) 10 ((-) 11 54). So the inner operation is 11 - 54, that is, -43; and the outer operation is 10 - (-43), that is, 10 + 43, therefore 53 as you observe. Go through similar steps for your second case, and again you'll see how the result forms!

Answer 5

foldr means fold from the right, so foldr (-) 0 [1, 2, 3] produces (1 - (2 - (3 - 0))). In comparison foldl produces (((0 - 1) - 2) - 3).

When the operators are not commutative foldl and foldr will get different results.

In your case, the first example expands to (10 - (11 - 54)) which gives 53.

Answer 6

An easy way to understand foldr is this: It replaces every list constructor with an application of the function provided. Your first example would translate to:

10 - (11 - 54)

from:

10 : (11 : [])

A good piece of advice that I got from the Haskell Wikibook might be of some use here:

As a rule you should use foldr on lists that might be infinite or where the fold is building up a data structure, and foldl' if the list is known to be finite and comes down to a single value. foldl (without the tick) should rarely be used at all.

Answer 7

I've always thought http://foldr.com to be a fun illustration. See the Lambda the Ultimate post.

Answer 8

Careful readings of -- and comparisons between -- the other answers provided here should already make this clear, but it's worth noting that the accepted answer might be a bit misleading to beginners. As other commenters have noted, the computation foldr performs in Haskell does not "begin at the right hand end of the list"; otherwise, foldr could never work on infinite lists (which it does in Haskell, under the right conditions).

The source code for Haskell's foldr function should make this clear:

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Each recursive computation combines the left-most atomic list item with a recursive computation over the tail of the list, viz:

a\[1\] `f` (a[2] `f` (a[3] `f` ... (a[n-1] `f` a[n])  ...))

where a[n] is the initial accumulator.

Because reduction is done "lazily in Haskell," it actually begins at the left. This is what we mean by "lazy evaluation," and it's famously a distinguishing feature of Haskell. And it's important in understanding the operation of Haskell's foldr; because, in fact, foldr builds up and reduces computations recursively from the left, binary operators that can short-circuit have an opportunity to, allowing infinite lists to be reduced by foldr under appropriate circumstances.

It will lead to far less confusion to beginners to say rather that the r ("right") and l ("left") in foldr and foldl refer to right associativity and left associativity and either leave it at that, or try and explain the implications of Haskell's lazy evaluation mechanism.

To work through your examples, following the foldr source code, we build up the following expression:

Prelude> foldr (-) 54 [10, 11]

->

10 - [11 - 54] = 53

And again:

foldr (\x y -> (x + y) / 2) 54 [12, 4, 10, 6]

->

(12 + (4 + (10 + (6 + 54) / 2) / 2) / 2) / 2 = 12

Answer 9

I think that implementing map, foldl and foldr in a simple fashion helps explain how they work. Worked examples also aid in our understanding.

  myMap f [] = []
  myMap f (x:xs) = f x : myMap f xs

  myFoldL f i [] = i
  myFoldL f i (x:xs) = myFoldL f (f i x) xs

  > tail [1,2,3,4] ==> [2,3,4]
  > last [1,2,3,4] ==> 4
  > head [1,2,3,4] ==> 1
  > init [1,2,3,4] ==> [1,2,3]

  -- where f is a function,
  --  acc is an accumulator which is given initially
  --  l is a list.
  --
  myFoldR' f acc [] = acc
  myFoldR' f acc l = myFoldR' f (f acc (last l)) (init l)

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

  > map (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0]
  > myMap (\x -> x/2) [12,4,10,6] ==> [6.0,2.0,5.0,3.0]

  > foldl (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125
  > myFoldL (\x y -> (x+y)/2) 54 [12, 4, 10, 6] ==> 10.125

    foldl from above: Starting accumulator = 54
      (12  + 54) / 2 = 33
      (4 + 33) / 2 = 18.5
      (10  + 18.5) / 2 = 14.25
      (6 + 14.25) / 2 = 10.125`

 > foldr (++) "5" ["1", "2", "3", "4"] ==> "12345"

 > foldl (++) "5" ["1", "2", "3", "4"] ==> “51234"

 > foldr (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12
 > myFoldR' (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12
 > myFoldR (\x y -> (x+y)/2) 54 [12,4,10,6] ==> 12

    foldr from above: Starting accumulator = 54
        (6  + 54) / 2 = 30
        (10 + 30) / 2 = 20
        (4  + 20) / 2 = 12
        (12 + 12) / 2 = 12

Answer 10

Ok, lets look at the arguments:

• a function (that takes a list element and a value (a possible partial result) of the same kind of the value it returns);
• a specification of the initial result for the empty list special case
• a list;

return value:

• some final result

It first applies the function to the last element in the list and the empty list result. It then reapplies the function with this result and the previous element, and so forth until it takes some current result and the first element of the list to return the final result.

Fold "folds" a list around an initial result using a function that takes an element and some previous folding result. It repeats this for each element. So, foldr does this starting at the end off the list, or the right side of it.

folr f emptyresult [1,2,3,4] turns into f(1, f(2, f(3, f(4, emptyresult) ) ) ) . Now just follow parenthesis in evaluation and that's it.

One important thing to notice is that the supplied function f must handle its own return value as its second argument which implies both must have the same type.

Source: my post where I look at it from an imperative uncurried javascript perspective if you think it might help.

Answer 11

The images in this wiki page visualize the idea of foldr (and foldl also):

• https://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

For example, the result of foldr (-) 0 [1,2,3] is 2. It can be visualized as:

  -
 / \
1   -
   / \
  2   -
     / \
    3   0

That is (from bottom to the top):

1 - ( -1 )      = 2
    2 - ( 3 )
        3 - 0

So foldr (\x y -> (x+y)/2) 54 [12, 4, 10, 6] is being computed through:

12 `f` (12.0)          = 12.0
     4 `f` (20.0)
        10 `f` (30.0)
             6 `f` 54