<div dir="ltr">If you're comfortable with imperative data structures, then you can go for Okasaki's book: <a href="http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504">http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504</a><div>Which developed from his Ph.D thesis available here: <a href="http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf">http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf</a></div><div><br></div><div>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.</div></div><div class="gmail_extra"><br><div class="gmail_quote">On 4 December 2015 at 13:19, Joachim Durchholz <span dir="ltr"><<a href="mailto:jo@durchholz.org" target="_blank">jo@durchholz.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hi all,<br>
<br>
is there an easy-to read introductory paper on reasoning about performance in Haskell?<br>
Stuff like big-Oh space and time complexity of a function.<br>
<br>
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.<br>
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?<br>
<br>
Example: Performance of<br>
  length xs<br>
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).<br>
I have no idea how to even write that down. What notation to use so one can formally reason about it.<br>
<br>
Any pointers?<br>
<br>
Regards,<br>
Jo<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div>Regards</div><div dir="ltr"><div><br></div><div>Sumit Sahrawat</div></div></div></div></div></div></div>
</div>