Re: [Caml-list] algorithm question

[Brian Hurt <bhurt@spnz.org>]

On Mon, 27 Feb 2006, Jean-Christophe Filliatre wrote:

>
> > > I want to implement the dancing link algorithm as described here:
> > > http://www-cs-faculty.stanford.edu/~knuth/papers/dancing-color.ps.gz
> > >
> > > has someone an idea if there is an equally fast way to implent
> > > this more functional?
> > [...]
> > With a purely functional (aka applicative aka
> > immutable) data structure, modifications are not destructive.  After you
> > add a new element into a map, for example, the old map is still valid and
> > not changed.  So you can support undoing operations by just keeping
> > references to the old copy of the data structure around, and dropping the
> > new (modified) data structure and returning to the old one.
>
> For the little story, I heard  this ``dancing links'' talk by Knuth at
> Stanford,  which was simply  delightful, and  at the  end I  asked him
> about  the   use  of   persistent  data  structures   in  backtracking
> algorithms. I had to give a  few explainations about what I meant, and
> when  I mentioned  ML, Knuth  simply replied:  ``oh, the  stuff  by Mc
> Carthy? I've never been convinced about it...''

Which is something I find vaguely humorous.  When he wrote the first 
version of AoCP, he wrote all the examples in assembler, because he wanted 
to use a language that wouldn't go out of date in 50 years.  Of course, 
what happened was the architecture design changed so radically over the 
next couple of decades that he needed to rewrite the books in a new 
assembly.

On the other hand, a core, simplified Lisp was relevent thirty years ago, 
is relevent today, and is the most likely language to still be relevent 
thirty years from now.

Brian