[Haskell-cafe] Reasoning about performance

[Joachim Durchholz]

Hi all,

is there an easy-to read introductory paper on reasoning about 
performance in Haskell?
Stuff like big-Oh space and time complexity of a function.

What I'm mostly after is how to organize complexity reasoning given 
non-strict evaluation. In that situation, a function's complexity 
depends on what subexpressions of the parameters have already been 
evaluated, so you get rather complicated conditional formulae, and you 
also need to somehow express what parts of a passed-in parameter may get 
evaluated under what conditions.
Is there even a good notation for that kind of stuff? Is there advice on 
how to organize the code to make performance formulae manageable?

Example: Performance of
   length xs
Turns out it is the number of items in xs, plus whatever you need to 
evaluate the list spine, as far as the list spine elements have not yet 
been evaluated (but you do not need to evaluate the list items).
I have no idea how to even write that down. What notation to use so one 
can formally reason about it.

Any pointers?

Regards,
Jo