Version franēaise
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
algorithm question
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2006-02-27 (10:31)
From: Jean-Christophe Filliatre <filliatr@l...>
Subject: Re: [Caml-list] algorithm question

 > > I want to implement the dancing link algorithm as described here:
 > >
 > >
 > > 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 (