On 7/14/07, Aaron Denney
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@gmail.com Silence is the perfectest herald of joy: I were but little happy, if I could say how much.