haskellcombinatorsfold

How does foldr work?

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?

Solution

  • 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.