[plt-scheme] Great books on algorithms?

Sounds like there is room for a DS/algorithms book that would apply  
to Scheme (and ML).  Ideally, you could even bring in Laziness for  
just data constructors via a library and compare and contrast with  
eager approaches but wrt the formulation of algorithms as well as the  
analysis. Better, you can bring in mutation when appropriate,  
especially in the next release. Someone ought to go for that. --  
Matthias


P.S John Stone at Grinnell started a project like that, though with a  
focus on standard Scheme and multiple-value versions of functions to  
keep things functional. I must admit that I don't know where is  
effort ended and stands. It might be worth checking out.




On Nov 4, 2007, at 11:14 AM, Prabhakar Ragde 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