[plt-scheme] Great books on algorithms?

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