How does foldr work?

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

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