[Haskell-cafe] Harder than you'd think
jeremy at n-heptane.com
Sun Jun 13 13:16:02 EDT 2010
My idea for solving this problem was to try to use something similar
to a kd-tree. I have a proof of concept for 2 keys here:
But, to extend it to an arbitrary number of keys may need template
The basic concept is to build a (balanced) tree (the same way Data.Map
does). But instead of using the same key at every level of the tree,
you cycle through the keys.
For example, if you are inserting a type which has keys that are Int
and Char. At the first level of the tree you might use the Int key to
decide if you should insert on the left or right. At the second level,
you use the Char to decide left or right, at the third level Int
again, and so on.
It is fine if the keys are the same type (Int, Int). The first level
you would use the first Int, the second level the second Int, the
third level the first Int, and so on.
Unlike multiple maps, each value only appears in one place. This
should make it easier to handle updates/deletes, which are pretty
tricky in the multiple map solution.
You can do lookups on a single (or multiple keys). For example, if you
want to do a lookup only the Int value, then at the first level you
compare the int key and go left or right. At the Char level you go
both left and right, and join the results. At the next Int levels you
go left or right, and so on.
There is a also supposedly a more type-safe variant of IxSet
somewhere, but I am not sure where it is offhand.
On Jun 13, 2010, at 7:09 AM, Andrew Coppin wrote:
> So the other day I was writing some code, and I ended up wanting to
> have a collection of data indexed in more than one way. In other
> words, I wanted fast lookup with several different keys.
> Initially I built something using two Data.Map objects to represent
> the two lookup keys, but then I needed up needing more keys per
> value than that, so I decided I should write a small library to
> abstract the whole thing.
> What I ended up writing is this: http://www.hpaste.org/fastcgi/hpaste.fcgi/view?id=25782
> It sorta kinda works, but man, take a look at the first line. That's
> *a lot* of type-system abuse to make it go. And it strikes me that
> if you had two keys, both of which happen to have the same type
> (e.g., String)... what then?
> On the other hand, it's not like you can go
> lookup :: KeyID -> Key -> Container -> Maybe Value
> since the type of both the container and the key depend on which key
> you want to access.
> Man, this is way, way harder than I realised!
> Does anybody have a less-insane way of doing this?
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe