From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 4AE65BBBB for ; Sun, 26 Feb 2006 21:51:26 +0100 (CET) Received: from conn.mc.mpls.visi.com (conn.mc.mpls.visi.com [208.42.156.2]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k1QKpP6L028516 for ; Sun, 26 Feb 2006 21:51:25 +0100 Received: from [192.168.42.2] (bhurt.dsl.visi.com [208.42.141.66]) by conn.mc.mpls.visi.com (Postfix) with ESMTP id 3BFE28131; Sun, 26 Feb 2006 14:51:24 -0600 (CST) Date: Sun, 26 Feb 2006 14:51:40 -0600 (CST) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Michael Wohlwend Cc: OCaml Mailing List Subject: Re: [Caml-list] algorithm question In-Reply-To: <200602262121.52645.micha-1@fantasymail.de> Message-ID: References: <200602262121.52645.micha-1@fantasymail.de> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at nez-perce with ID 440214CD.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 knuth:01 applicative:01 implicitly:01 backtracking:01 dancing:98 wrote:01 structures:01 immutable:01 precisely:01 algorithm:01 algorithm:01 snapshot:01 data:02 data:02 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 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