[Haskell-cafe] Re: Indentation Creep

[Thomas Conway]

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.

cheers,
T.
-- 
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.