Sumit Sahrawat, Maths & Computing, IIT (BHU) sumit.sahrawat.apm13 at iitbhu.ac.in
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
> 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
>

--
Regards

Sumit Sahrawat
-------------- next part --------------
An HTML attachment was scrubbed...