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?
On Sun, Jun 13, 2010 at 01:09:24PM +0100, Andrew Coppin wrote:
Does anybody have a less-insane way of doing this?
Did you take a look at happstack-ixset[1]? [1] http://hackage.haskell.org/package/happstack-ixset -- Felipe.
Felipe Lessa wrote:
On Sun, Jun 13, 2010 at 01:09:24PM +0100, Andrew Coppin wrote:
Does anybody have a less-insane way of doing this?
Did you take a look at happstack-ixset[1]?
No. I'll take a look at it. (From the looks of it, it seems to be using TH and/or run-time checks to get around the type-system problems...)
On 13 June 2010 15:23, Andrew Coppin
Felipe Lessa wrote:
On Sun, Jun 13, 2010 at 01:09:24PM +0100, Andrew Coppin wrote:
Does anybody have a less-insane way of doing this?
Did you take a look at happstack-ixset[1]?
No. I'll take a look at it.
(From the looks of it, it seems to be using TH and/or run-time checks to get around the type-system problems...)
A while ago I've written a simple version of ixset that uses type classes (without TH) as a proof of concept: http://darcs.monoid.at/tbox/Data/Index.hs Peter
What I ended up writing is this: http://www.hpaste.org/fastcgi/hpaste.fcgi/view?id=25782 lookup :: KeyID -> Key -> Container -> Maybe Value
Does anybody have a less-insane way of doing this?
Sure: type MyMap = Map (KeyID, Key) Value Don't use multiple keys. Put the keys into a tuple and use that as key. Let me know whether this is what you were looking for. I tried writing something like this. Yet SQL gives all this stiff for free. I still wonder which is the nicest way to express this data in Haskell without coding everything yourself.. Yours Marc Weber
Marc Weber wrote:
Does anybody have a less-insane way of doing this?
Sure:
type MyMap = Map (KeyID, Key) Value
Don't use multiple keys. Put the keys into a tuple and use that as key.
Let me know whether this is what you were looking for.
Trouble is, this requires you to have *all* the keys to perform a single lookup. You can't do a lookup on just one attribute.
I tried writing something like this. Yet SQL gives all this stiff for free.
[Except that SQL bindings don't work on Windows. Besides, I'm only working with small data volumes, I don't need persistence or transaction guarantees, etc.]
I still wonder which is the nicest way to express this data in Haskell without coding everything yourself..
Indeed.
Marc Weber wrote:
Andrew Coppin wrote:
What I ended up writing is this: http://www.hpaste.org/fastcgi/hpaste.fcgi/view?id=25782 lookup :: KeyID -> Key -> Container -> Maybe Value
Does anybody have a less-insane way of doing this?
Sure:
type MyMap = Map (KeyID, Key) Value
Don't use multiple keys. Put the keys into a tuple and use that as key.
Actually, it's a disjoint sum type: data a :+: b = Inl a | Inr b -- also known as Either type DB3 e k1 k2 k2 = D1 e (k1 :+: k2 :+: k3) Hm, that's not quite right either because every e has multiple keys. The following should work, however: type DB3 e k1 k2 k2 = D1 e k1 :*: DB1 e k2 :*: DB2 e k3 lookup :: (k1 :+: k2 :+: k3) -> DB3 e k1 k2 k3 -> Maybe e In any case, I recommend using a special key type for combining keys anyway, as explained here http://article.gmane.org/gmane.comp.lang.haskell.cafe/23648 Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com
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
Excerpts from Jeremy Shaw's message of Sun Jun 13 19:16:02 +0200 2010:
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.
I tried this. TH changed a little bit so it may be broken. I mapped multi keys to Data.Map Key1 (Data.Map Key 2) http://github.com/MarcWeber/rdmhaskell/ I gave up the project that time due to lack of time and because spending so much time on this project was not worth the time because Postgres and MYSQL already did what I was looking for.. The idea was to model kind of database because I wasn't satisfied with IxSet that time. line 50 shows how to define a combined index on two fields: http://github.com/MarcWeber/rdmhaskell/blob/master/test/TestCase.hs I'm not even sure whether I should recommend reading my code :) All I want to say: Its a little bit of work which is highly appreciated by many Haskellers IMHO. If you start such a project keep posting updates to the list. I'll read them. Marc Weber
participants (6)
-
Andrew Coppin -
Felipe Lessa -
Heinrich Apfelmus -
Jeremy Shaw -
Marc Weber -
Peter Robinson