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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe