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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 2FA38BBBB for ; Mon, 27 Feb 2006 15:48:35 +0100 (CET) Received: from cenn.mc.mpls.visi.com (cenn.mc.mpls.visi.com [208.42.156.9]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id k1REmYD8004065 for ; Mon, 27 Feb 2006 15:48:34 +0100 Received: from [192.168.42.2] (bhurt.dsl.visi.com [208.42.141.66]) by cenn.mc.mpls.visi.com (Postfix) with ESMTP id 48691843A; Mon, 27 Feb 2006 08:48:33 -0600 (CST) Date: Mon, 27 Feb 2006 08:48:53 -0600 (CST) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Jean-Christophe Filliatre Cc: Michael Wohlwend , OCaml Mailing List Subject: Re: [Caml-list] algorithm question In-Reply-To: <17410.54463.981731.409109@gargle.gargle.HOWL> Message-ID: References: <200602262121.52645.micha-1@fantasymail.de> <17410.54463.981731.409109@gargle.gargle.HOWL> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Miltered: at concorde with ID 44031142.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 filliatre:01 knuth:01 applicative:01 knuth:01 backtracking:01 vaguely:01 dancing:98 dancing:98 wrote:01 wrote:01 rewrite:01 structures:01 lisp:01 immutable: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 On Mon, 27 Feb 2006, Jean-Christophe Filliatre 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? > > [...] > > 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...'' Which is something I find vaguely humorous. When he wrote the first version of AoCP, he wrote all the examples in assembler, because he wanted to use a language that wouldn't go out of date in 50 years. Of course, what happened was the architecture design changed so radically over the next couple of decades that he needed to rewrite the books in a new assembly. On the other hand, a core, simplified Lisp was relevent thirty years ago, is relevent today, and is the most likely language to still be relevent thirty years from now. Brian