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).]


$B!=(B $B!h(B

-------------------
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