Tracing can produce crease inversion

Question

When I compile the "modified amount" file ("_sum_folds.hs"):

*--------------------------- [ 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 

(the order for the "foldl" process is fine ...)

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

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

 *Main > _sum ([1..5]) * 5 * 4 * 3 * 2 * 1 * 15 * it :: Integer 

...: the processing order of the elements inside <[1..5]> ("x") seems to be upside down (this is "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 the tree like this:

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

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

_sum2

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

If this happens in _sum2 , 3 will be printed.

Then, acc is evaluated, so tr ___ 2 is evaluated, which results in a mapping of 2.

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

_sum

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

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

Step 1) Since you also print acc in _sum , Haskell should evaluate it, i.e. tr ___ 2 . When this assessment is completed, it will print out acc and then 3.

Step 2) To evaluate tr ___ 2 , since you type acc , Haskell must evaluate it, i.e. The tree to the left of 2, namely tr ___ 1 . When this assessment is completed, it will print acc , and then 2.

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

Then control proceeds to step 2 and acc (1) is displayed, and then 2.

Then control proceeds to step 1 and acc (3) and 3 are displayed.