[plt-scheme] Great books on algorithms?

Ah, well I've had my fill of code that optimized for time or space,
far too much that's good enough, so the conceptual beauty of purity
and laziness appeal to me these days.
I'll return to pragmatism eventually, but until I earn my undergrad
I'll nourish my young and stupid side.

On Nov 4, 2007 10:14 AM, Prabhakar Ragde <plragde at uwaterloo.ca> wrote:
> Shriram wrote:
>  >> Anyone had any great fondness of "Functional Data Structures"?
> > I would say something, but I should defer to Prabhakar.
>
> Remember the parable of the goat equidistant between two bales of hay?
> This is a bale of hay equidistant between two goats.
>
> I've spent some time with Okasaki's "Purely Functional Data Structures"
> and there is a lot of good stuff in there. It does tend to lean on
> purity, laziness (these two via Haskell), and amortized analysis.
> Schemers will have to figure out when a judicious application of
> mutation (without going all the way back into traditional DS/Algs
> territory) will make things cleaner. Plus, time and space analysis of
> Haskell programs is not for the faint of heart.
>
> I also have "Algorithms: A Functional Programming Approach" by Rabhi and
> Lapalme, which again is Haskell-based. Again, much good stuff, but not
> quite what Schemers need.
>
> Both these books elide over the places where their approaches don't work
> as well as the traditional ones. Okasaki has a lovely demonstration of
> how pattern-matching makes the implementation of insertion into
> red-black balanced binary search trees super-clean (this is also
> available a functional pearl in JFP and probably from his website as
> well). This yields an implementation with about twenty lines of PLT
> Scheme code using match.ss. But deletion is still messy (not worse than
> conventionally, but getting there) and he doesn't mention that operation
> at all. Rabhi and Lapalme put in space-time analyses when they are
> favourable, but in the case of DFS in graphs, instead of admitting that
> their implementation is O(n^2) and that you can't really do better than
> O(n log n) without using mutation (which makes it linear IF vertices are
> a set of contiguous integers so that arrays can be used), they just
> leave out the analysis.
>
> I can understand the impulse to not be totally open -- how often has
> naive Fibonacci been used to discredit the functional approach? -- but
> it does mean that readers of these books have to read between the lines
> at times. That shouldn't put anyone off. They are part of a well-stocked
> functional programming library. --PR
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>