Hi folks! So, in writing my chess engine, I've been trying to maintain 2 Map objects. One maps squares on the board to Ints, the other maps Ints to actual Pieces. It occurred to me that it would be useful to explicitly have a Bi-directional Map, which does the maintenance of keeping the Maps synchronized behind the scenes. Thus, Bimap was born! I've taken the API for Data.Map (which you can find at ), and cannibalized it for Bimap. The new API is at http://hpaste.org/2344 . The idea is that if you have a Bimap k a, and you want to treat the k's as keys, and use a function like Data.Map.foo, it will be called Data.Map.left_foo in Bimap. And if they want to do the same thing, but using the a's as keys, then they simply use right_foo. The metaphor is that we can view it as a Map in 2 directions, manipulating it from the left (on the k's), or from the right (on the a's). Is this useful? Is there a better way? Is the API too big, and if so, how can it be pared down?
Andrew Wagner wrote:
So, in writing my chess engine, I've been trying to maintain 2 Map objects. One maps squares on the board to Ints, the other maps Ints to actual Pieces. It occurred to me that it would be useful to explicitly have a Bi-directional Map, which does the maintenance of keeping the Maps synchronized behind the scenes. Thus, Bimap was born! I've taken the API for Data.Map (which you can find at ), and cannibalized it for Bimap. The new API is at http://hpaste.org/2344 . The idea is that if you have a Bimap k a, and you want to treat the k's as keys, and use a function like Data.Map.foo, it will be called Data.Map.left_foo in Bimap. And if they want to do the same thing, but using the a's as keys, then they simply use right_foo. The metaphor is that we can view it as a Map in 2 directions, manipulating it from the left (on the k's), or from the right (on the a's).
Is this useful? Is there a better way? Is the API too big, and if so, how can it be pared down?
IMHO, the API is too big and not beautiful enough. How about a function flip :: Bimap a b -> Bimap b a that interchanges the role of keys and values? Or maybe keep every functions symmetric in a and b , like in update :: ((a,b) -> Maybe (a,b)) -> Either a b -> Bimap a b -> Bimap a b The changer functions take pairs and the search key to look for is Either a b . But most of the map functions (including update above) probably won't work anyway, what should left_insertWith (\new old -> new) 'a' 1 (fromList [('a',2),('b',1)]) do? I can't yield fromList [('a',1),('b',1)] since 1 has two keys now. Regards, apfelmus
On 8/20/07, apfelmus
Andrew Wagner wrote:
It occurred to me that it would be useful to explicitly have a Bi-directional Map, which does the maintenance of keeping the Maps synchronized behind the scenes. Thus, Bimap was born!
... most of the map functions (including update above) probably won't work anyway, what should
left_insertWith (\new old -> new) 'a' 1 (fromList [('a',2),('b',1)])
do? I can't yield
fromList [('a',1),('b',1)]
since 1 has two keys now.
Exactly. For this to work there needs to be the constraint that there's a one-to-one mapping in each direction. The Bimap should have the uniqueness promise that "Set (k, v)" gives. Yet you should be able to search on either tuple value. -- Rich JID: rich@neswold.homeunix.net AIM: rnezzy
Exactly. For this to work there needs to be the constraint that there's a one-to-one mapping in each direction. The Bimap should have the uniqueness promise that "Set (k, v)" gives. Yet you should be able to search on either tuple value.
Or... have the possibility of returning a list of values. Arguably there are two possible implementations, one that enforces one-to-one mapping, and one which allows multiple values, in either direction. "But how can you change a value if there are non-unique keys?". Well, you dont change a value, you change a list of values ;-) So, let's say our bimap is: 1,1 1,2 5,2 5,3 then: bimap_getvalue ourbimap 1 gives [1,2] bimap_getkey ourbimap 2 gives [1,5] Executing bimap_setkey ourbimap 2 [1,4] changes the bimap to: 1,1 1,2 4,2 5,3
Hugh Perkins wrote:
Exactly. For this to work there needs to be the constraint that there's a one-to-one mapping in each direction. The Bimap should have the uniqueness promise that "Set (k, v)" gives. Yet you should be able to search on either tuple value.
Or... have the possibility of returning a list of values.
Arguably there are two possible implementations, one that enforces one-to-one mapping, and one which allows multiple values, in either direction.
Terminology reminder :) - the latter is called "(binary) relation" http://en.wikipedia.org/wiki/Binary_relation - the former would be a "bijection" http://en.wikipedia.org/wiki/Bijective_map Regards, apfelmus
apfelmus wrote:
Hugh Perkins wrote:
Arguably there are two possible implementations, one that enforces one-to-one mapping, and one which allows multiple values, in either direction.
Terminology reminder :) - the latter is called "(binary) relation" http://en.wikipedia.org/wiki/Binary_relation - the former would be a "bijection" http://en.wikipedia.org/wiki/Bijective_map
Following a great tradition, "That's just semantics."
Just noticed, erlang has the second kind of bimap (a "bijection"?) built into each process:
From http://www.erlang.org/doc/reference_manual/processes.html :
"10.9 Process Dictionary Each process has its own process dictionary, accessed by calling the following BIFs: put(Key, Value) get(Key) get() get_keys(Value) erase(Key) erase()" That's interesting.
participants (5)
-
Albert Y. C. Lai -
Andrew Wagner -
apfelmus -
Hugh Perkins -
Rich Neswold