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
next prev 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).