trace can give 'inversion' of processing in folds

Question

When I compile the "modified sum" (« _sum_folds.hs ») file :

*--------------------------- [

import Debug.Trace 

_sum = 
    foldl ( \ acc x -> 
            trace (
              show x
              ++ " - " ++ show acc
              )
          acc + x
        ) 
        0

*--------------------------- ]

[1 of 1] Compiling Main             ( _sum_folds .hs, interpreted )
Ok, modules loaded: Main.

... and apply it to '[1..5]', I get :

*Main > _sum ([1..5])

* 1 - 0
* 2 - 1
* 3 - 3
* 4 - 6
* 5 - 10
* 15
* it :: Integer

(order for a 'foldl' process is OK ...)

If I remove the < ++ " - " ++ show acc > , I get :

( we have only < trace (show x) > )

*Main > _sum ([1..5])

* 5
* 4
* 3
* 2
* 1
* 15
* it :: Integer

... : the order of processing of the elements inside < [1..5] > (the 'x's) seems have been inverted (it is a 'foldl')...!?

What does it mean ?

Answer 1

The expression foldl (+) 0 [1..3] creates the following expression tree:

              +
             / \
            +   3
           / \
          +   2
         / \
        0   1

In your case both _sum and _sum2 build a tree like this:

              tr
             / \
            tr  3
           / \
          tr   2
         / \
        0   1

Here tr is the function in the fold which does the accumulation and tracing.

_sum2

The first operation to be visited is the tr ___ 3 at top of the tree. The 3 is x and ___ is acc in the tr function.

When this happens in _sum2 the 3 is printed.

Then acc is evaluated, so tr ___ 2 is evaluated which results in 2 getting displayed.

Then tr ___ 1 is evaluated, so 1 is printed.

_sum

However, in _sum a difference course of events unfolds (no pun intended).

We again start at the top of the tree: tr ___ 3.

Step 1) Since in _sum you are also printing out acc, Haskell needs to evaluate it, i.e. tr ___ 2. When this evaluation is complete it will print out acc and then 3.

Step 2) To evaluate tr ___ 2, since you are printing out the acc, Haskell needs to evaluate it, i.e. the tree to the left of the 2 - namely tr ___ 1. When this evaluation is complete it will print out acc and then 2.

Step 3) To evaluate tr ___ 1, since you are printing out the acc, Haskell needs to evaluate the tree to the left of the 1, i.e. 0. When this evaluation is complete it will print out acc and then 1. In this case 0 is already evaluated, so it prints out 0 and then 1.

Control then transfers back to step 2 and acc is displayed (1) and then 2.

Control then transfers back to step 1 and acc is displayed (3) and the 3.