[Haskell-cafe] Reasoning about performance
jo at durchholz.org
Fri Dec 4 07:49:43 UTC 2015
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
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.
More information about the Haskell-Cafe