From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA28410; Thu, 29 Jul 2004 19:44:51 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA28194 for ; Thu, 29 Jul 2004 19:44:50 +0200 (MET DST) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from wetware.com (wetware.wetware.com [199.108.16.1]) by nez-perce.inria.fr (8.12.10/8.12.10) with ESMTP id i6THimEV027312 for ; Thu, 29 Jul 2004 19:44:49 +0200 Received: from [208.177.152.17] (helo=[10.0.1.9]) by wetware.com with esmtp (Exim 4.20) id 1BqExQ-0007R3-4s; Thu, 29 Jul 2004 10:44:44 -0700 In-Reply-To: References: <16646.64470.304530.264731@soggy.deldotd.com> <16647.5177.849829.421587@soggy.deldotd.com> <4107544C.4040502@baretta.com> <410898F0.6030804@baretta.com> Mime-Version: 1.0 (Apple Message framework v618) Content-Type: text/plain; charset=ISO-2022-JP; format=flowed Message-Id: Content-Transfer-Encoding: 7bit Cc: Ocaml From: james woodyatt Subject: Re: [Caml-list] looping recursion Date: Thu, 29 Jul 2004 10:44:42 -0700 To: brogoff X-Mailer: Apple Mail (2.618) X-Miltered: at nez-perce with ID 41093790.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; woodyatt:01 jhw:01 wetware:01 caml-list:01 recursion:01 brogoff:01 catenable:01 deques:01 deques:01 doubly:01 catenable:01 hugely:01 implemented:01 marshalled:01 kot:99 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On 29 Jul 2004, at 07:58, brogoff wrote: > > Some problems are just way easier to solve with imperative programming > though. Have you ever taken a look at purely functional catenable > deques? > If you don't need persistence (if your deques are used in a single > threaded > manner that is) would you use those instead of the obvious doubly > linked > list implementation? That's not an abstract question either, catenable > deques > come up quite naturally when implementing some 2D computational > geometry > algorithms.I took a look at the latest algorithm by Kaplan and Tarjan > and > quickly realized that it was hugely complicated if persistence is not > needed. As it happens, I have some experience with this problem. I have implemented purely functional, catenable deques in Ocaml. (I need the persistence.) Yes, the Kaplan-Okasaki-Tarjan deques are hideously complicated. However. I have found a significantly simpler algorithm that uses lazy evaluation, still offers near real-time performance, and only adds the limitation that persistence is only available in program memory (lazy cells can't be marshalled, you know). I can live with that limitation quite happily, and my deques are about three times as fast as the KOT deques. My algorithm can be reviewed in the [Cf_deque] module of my Cf library. The Ocaml HUMP has a link to it. And the good news is that the algorithm is *not* patented as far as I know (the deadline for me to file an application has lapsed too), and the library is released under a BSD two-clause style license. (I should be releasing an update to the library this week, but the [Cf_deque] module will not be changing.) All that said, I can say that I have found I need persistent data structures to make other functional algorithms work well. In those cases where I feel safe and comfortable mixing imperative and functional styles (fraught with peril!), then I certainly use the standard [Queue] module. I'll be using that tactic in the [Cf_gadget] module when I make the next release (the current version uses [Cf_deque] unnecessarily). [Off topic: there are also cases where I find the standard [Queue] module to be insufficiently well-endowed with utility functions, so I use my [Cf_deque] module instead. It performs almost as well as [Queue], and it allows for more convenient transformation and manipulations of the represented sequence (see the [Cf_poll] module for an example of my thinking there).] ― ∴ ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners