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 1C62BBBBC for ; Mon, 27 Feb 2006 11:31:10 +0100 (CET) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id k1RAV9YA005684 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Mon, 27 Feb 2006 11:31:09 +0100 Received: from smtp.lri.fr (serveur3-5 [129.175.3.5]) by ext.lri.fr (Postfix) with ESMTP id 8FC50202467; Mon, 27 Feb 2006 11:31:09 +0100 (CET) Received: from pc9-152 (pc9-152 [129.175.9.152]) by smtp.lri.fr (Postfix) with ESMTP id 6019DCED98; Mon, 27 Feb 2006 11:31:08 +0100 (CET) Received: from filliatr by pc9-152 with local (Exim 3.36 #1 (Debian)) id 1FDfe9-0006tU-00; Mon, 27 Feb 2006 11:30:29 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <17410.54463.981731.409109@gargle.gargle.HOWL> Date: Mon, 27 Feb 2006 11:30:23 +0100 To: Brian Hurt Cc: Michael Wohlwend , OCaml Mailing List Subject: Re: [Caml-list] algorithm question In-Reply-To: References: <200602262121.52645.micha-1@fantasymail.de> X-Mailer: VM 7.19 under Emacs 21.4.1 From: Jean-Christophe Filliatre X-Virus-Scanned: by amavisd-new at lri.fr X-Miltered: at nez-perce with ID 4402D4ED.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 filliatre:01 filliatr:01 lri:01 knuth:01 applicative:01 knuth:01 backtracking:01 surprising:01 filliatre:01 lri:01 filliatr:01 dancing:98 dancing:98 structures:01 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 > > 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)