[Haskell-cafe] Harder than you'd think

[Jeremy Shaw]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe