quchen on Turn O(n^2) reverse into O(n)

Comment on Turn O(n^2) reverse into O(n)parent

One thing to note is that this walks the list 'backward'

No, foldr walks through the list forward, and exactly once. Your example is evaluated as

    foldr (+) 0 [1, 2, 3, 4]
    = 1 + foldr (+) 0 [2,3,4]
    = 1 + (2 + foldr (+) 0 [3,4])
    = 1 + (2 + (3 + foldr (+) 0 [4]))
    = 1 + (2 + (3 + (4 + foldr (+) 0 [])))
    = 1 + (2 + (3 + (4 + 0)))

e12e 12y

Is there an (easy) way to see what/how haskell evaluates such code (ie: step through)? Something like explain from sql or disassemble from lisp?

jerf 12y

GHCI has a debugger. You can step into an expression and watch as Haskell evaluates it, in full lazy order.

Even if you understand lazy evaluation in theory, I recommend taking some non-trivial (but not too large) expression and :step'ing through the whole evaluation sometime, just to train your intuition.

Comments