Re: [Caml-list] algorithm question

[Jean-Christophe Filliatre <filliatr@lri.fr>]

 > > 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...''

Though it was not very surprising, I still was a bit disappointed :-)

-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)