Re: [Caml-list] algorithm question

[Brian Hurt <bhurt@spnz.org>]

On Sun, 26 Feb 2006, Michael Wohlwend 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? The method in the paper seems pretty good, just adjusting a the
> linksfields of the structure...

It's solving a problem that doesn't show up in functional programming.

Basically, he's trying to avoid having to duplicate an entire data 
structure in order to preserve a snapshot of the data structure to support 
undoing operations.  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.

Also, he's skating a fine edge.  Operation (2) implicitly assumes that 
L[x] and R[x] have not been modified before the reinsertion happens.  If 
they have been modified, the results depend upon exactly how they've been 
modified, but can easily lead to corrupt data structures.  If you're 
precisely backtracking, it'll be OK, other than that...

Brian