[Haskell-cafe] Re: Indentation Creep

Thomas Conway drtomc at gmail.com
Sat Jul 14 05:38:03 EDT 2007

On 7/14/07, Aaron Denney <wnoise at ofb.net> wrote:
> It might be a bit clearer if every level of the tree were a flat map of
> pointers.  You can even parametrize on this map type...

Yes, this would be an obvious generalization, though if I were to
modify the details of the structure, I'd be inclined to go in exactly
the opposite direction, and rather than have the keys be [Bit], use
Bits b => .... and use an Int argument to recurse down the tree.

The motivation for this structure is that I wanted a queue, from which
I could remove elements from the middle efficiently, and using only
local updates (for high concurrency).

The structure I was replacing used a doubly linked list using TVars as
pointers between nodes. As I hinted in the original post, this was
ugly, and seem to be leaking memory (I actually think there might be
some issues with the GHC implementation of TVars and GC - I'm not
certain, but I think the leak *may* be a bug in GHC, and as I posted
separately, GC was taking an awfully large proportion of the time).
One way of achieving what I wanted was to keep a "timestamp" counter
and use (Map TimeStamp k). The problem with Map is that it is hostile
to concurrency - all modifications are "global" wrt the Map.

The structure that is required in this instance is a structure with
enough TVars linking the pieces that updates are local - a write to
one TVar doesn't interact with reads in other parts of the structure.
For example a binary tree with TVars between the nodes. Except a
(vanilla) binary tree would be rotten in this case because the new
keys arrive in strictly increasing order - a worst case for such a
structure. So I could have modified Map, or my own home-rolled AVL
tree to stick TVars between the nodes, there were reasons not to:

1. Tries are easy to implement and offer O(b) ~= O(1) for keys with b
bits. Thanks to apfelmus for reminding me of this recently.

2. In Haskell, it's *fun* rolling new data structures to see how
elegant you can be. (A favorite quote of mine is "Elegance is not
Optional", I think due to Richard O'Keefe.)

3. This structure is used in an inner loop, so a structure giving O(1)
operations was desirable.

Anyway, the point of the original post was to find tricks for avoiding
indentation creep, rather than the trie itself.

Dr Thomas Conway
drtomc at gmail.com

Silence is the perfectest herald of joy:
I were but little happy, if I could say how much.

More information about the Haskell-Cafe mailing list