[Haskell-cafe] Reasoning about performance

Fri Dec 4 08:01:16 UTC 2015

If you're comfortable with imperative data structures, then you can go for
Okasaki's book:
http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504
Which developed from his Ph.D thesis available here:
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

People say both are very similar in their contents, but I can't say for
sure. I've read the first two chapters and found them to be enlightening.

On 4 December 2015 at 13:19, Joachim Durchholz <jo at durchholz.org> wrote:

> 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>

-- 
Regards

Sumit Sahrawat
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151204/f852f099/attachment.html>