Why does printing affects order when right folding in Haskell?

Question

I'm sure it has something to do with lazy evaluation, but still, I just can't give myself an explanation of why it acts this way. Why does evaluating the right hand side in verboseAdd2 reverse the debug traces output?

This is the code:

import Debug.Trace

data BinaryTree = Empty | Node Int BinaryTree BinaryTree

instance Show BinaryTree where
  show Empty = "_"
  show (Node x Empty right) = unwords [           show x, show right]
  show (Node x left  right) = unwords [show left, show x, show right]

add :: Int -> BinaryTree -> BinaryTree
add v Empty = Node v Empty Empty
add v a@(Node x left right)
  | v == x = a
  | v <  x = Node x (add v left) right
  | v >  x = Node x left (add v right)

verboseAdd :: Int -> BinaryTree -> BinaryTree
verboseAdd v a = trace ("[1] Adding v=" ++ show v) (add v a)

verboseAdd2 :: Int -> BinaryTree -> BinaryTree
verboseAdd2 v a = trace ("[2] Adding v=" ++ show v ++ " to " ++ show a) (add v a)

verbosePlus :: (Num a, Show a) => a -> a -> a
verbosePlus left right = trace (show left ++ " + " ++ show right)
                               (left + right)

main :: IO()
main = do
  let seq = [1,2,3,4,5]
  in do print $ foldr verbosePlus 0 seq
        putStrLn ""
        print $ foldr verboseAdd Empty seq
        putStrLn ""
        print $ foldr verboseAdd2 Empty seq

This is the output:

5 + 0
4 + 5
3 + 9
2 + 12
1 + 14
15

[1] Adding v=1
[1] Adding v=2
[1] Adding v=3
[1] Adding v=4
[1] Adding v=5
1 _ 2 _ 3 _ 4 _ 5 _

[2] Adding v=5 to _
[2] Adding v=4 to 5 _
[2] Adding v=3 to 4 _ 5 _
[2] Adding v=2 to 3 _ 4 _ 5 _
[2] Adding v=1 to 2 _ 3 _ 4 _ 5 _
1 _ 2 _ 3 _ 4 _ 5 _

Answer 1

Let's expand the foldr in

foldr verboseAdd2 Empty [1, 2, 3, 4, 5]

using its definition (abbreviating verboseAdd2 as va):

1 `va` (2 `va` (3 `va` (4 `va` (5 `va` Empty))))

or, in this case, maybe it's simpler if we use prefix notation:

va 1 $ va 2 $ va 3 $ va 4 $ va 5 Empty

By the definition of va, this reduces to

let y1 = va 2 $ va 3 $ va 4 $ va 5 Empty
in trace ("Adding v=1 to " ++ show y1) (add 1 y1)

By unrolling more occurrences of va, we get

let y4 = trace ("Adding v=5 to " ++ show Empty) (add 5 Empty) in
let y3 = trace ("Adding v=4 to " ++ show y4) (add 4 y4) in
let y2 = trace ("Adding v=3 to " ++ show y3) (add 3 y3) in
let y1 = trace ("Adding v=2 to " ++ show y2) (add 2 y2) in
trace ("Adding v=1 to " ++ show y1) (add 1 y1)

Hopefully you can see from this that to show y1 in the outmost trace, we first need to evaluate y1, which causes trace ("Adding v=2 to " ++ show y2") to fire, which forces y3, and so on, until we get to y4. The trace in y4 doesn't need to force anything else, so it can finally print its message, then go on to evaluate add 5 Empty, which is then used by the trace in the definition of y3, and so on.