Calculation steps in Haskell foldr

Question

Does anybody know the steps of haskell 'foldr' use of function?

GHCI Command Window:

foldr (\x y -> 2*x + y) 4 [5,6,7] 

The result after evaluation:

40

Steps on this,

Prelude> foldr (\x y -> 2*x + y) 4 [5,6,7] 
6 * 2 + (7 * 2 + 4)
12 + 18 = 30
5 * 2 + 30 = 40 v

Answer 1

One definition of foldr is:

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f acc []     = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

The wikibook on Haskell has a nice graph on foldr (and on other folds, too):

  :                         f
 / \                       / \
a   :       foldr f acc   a   f
   / \    ------------->     / \
  b   :                     b   f
     / \                       / \
    c  []                     c   acc

I.e. a : b : c : [] (which is just [a, b, c]) becomes f a (f b (f c acc)) (again, taken from wikibook).

So your example is evaluated as let f = (\x y -> 2*x + y) in f 5 (f 6 (f 7 4)) (let-binding only for brevity).

Answer 2

You can actually easily visualize it for yourself:

import Text.Printf

showOp f = f (printf "(%s op %s)") "0" ["1","2","3"]

then

Main> showOp foldr
"(1 op (2 op (3 op 0)))"
Main> showOp foldl
"(((0 op 1) op 2) op 3)"
Main> showOp scanl
["0","(0 op 1)","((0 op 1) op 2)","(((0 op 1) op 2) op 3)"]