[plt-scheme] Great books on algorithms?

What is this mutation you all speak of? (set! )ing?

On Nov 4, 2007 3:43 PM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
>
> 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
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>