caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
From: james woodyatt <jhw@wetware.com>
To: brogoff <brogoff@speakeasy.net>
Cc: Ocaml <caml-list@inria.fr>
Subject: Re: [Caml-list] looping recursion
Date: Thu, 29 Jul 2004 10:44:42 -0700	[thread overview]
Message-ID: <F92BA00A-E186-11D8-9C86-000A958FF2FE@wetware.com> (raw)
In-Reply-To: <Pine.LNX.4.58.0407290715410.22555@shell1.speakeasy.net>

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


  parent reply	other threads:[~2004-07-29 17:44 UTC|newest]

Thread overview: 44+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2004-07-27 23:43 briand
2004-07-28  0:27 ` John Prevost
2004-07-28  0:38   ` John Prevost
2004-07-28  1:17     ` skaller
2004-07-28  1:05   ` briand
2004-07-28  1:43     ` Brian Hurt
2004-07-28  2:49       ` briand
2004-07-28  3:12         ` Brian Hurt
2004-07-28  3:20         ` Brian Hurt
2004-07-28  5:54         ` brogoff
2004-07-28  7:22           ` Alex Baretta
2004-07-28 16:38             ` brogoff
2004-07-28 19:40               ` Jon Harrop
2004-07-28 20:18                 ` Brandon J. Van Every
2004-07-29  6:01                   ` Alex Baretta
2004-07-28 21:22                 ` brogoff
2004-07-29  9:13                   ` Daniel Andor
2004-07-29  9:25                     ` Keith Wansbrough
2004-07-29  9:41                       ` Nicolas Cannasse
2004-07-29  9:57                       ` Xavier Leroy
2004-07-29 10:44                         ` Daniel Andor
2004-07-29 12:56                           ` brogoff
2004-07-29 10:11                     ` skaller
2004-07-29 12:41                     ` brogoff
2004-07-29  6:28               ` Alex Baretta
2004-07-29 14:58                 ` brogoff
2004-07-29 16:12                   ` Brian Hurt
2004-07-29 17:49                     ` james woodyatt
2004-07-29 19:25                       ` Brian Hurt
2004-07-29 20:01                         ` brogoff
2004-07-30  4:42                           ` james woodyatt
2004-07-29 17:44                   ` james woodyatt [this message]
2004-07-29 23:12                     ` skaller
2004-07-29 22:42                   ` Alex Baretta
2004-07-30  2:38                     ` Corey O'Connor
     [not found]                     ` <200407300136.14042.jon@jdh30.plus.com>
2004-07-30 12:45                       ` Alex Baretta
2004-07-30 17:07                     ` brogoff
2004-07-30 18:25                       ` [Caml-list] kaplan-okasaki-tarjan deque (was "looping recursion") james woodyatt
2004-07-30 21:20                         ` brogoff
2004-07-31  5:37                           ` james woodyatt
2004-07-28  7:27       ` [Caml-list] looping recursion skaller
2004-07-28 14:36         ` Brian Hurt
2004-07-28 22:05           ` skaller
2004-07-28  0:37 ` skaller

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=F92BA00A-E186-11D8-9C86-000A958FF2FE@wetware.com \
    --to=jhw@wetware.com \
    --cc=brogoff@speakeasy.net \
    --cc=caml-list@inria.fr \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).