[Haskell-cafe] Re: Bi-directional Maps

apfelmus apfelmus at quantentunnel.de
Mon Aug 20 03:55:58 EDT 2007

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.


More information about the Haskell-Cafe mailing list