Hello, 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: http://src.seereason.com/haskell-kdmap/ But, to extend it to an arbitrary number of keys may need template haskell. 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. - jeremy 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe