[m-dev.] bimap

Zoltan Somogyi zs at cs.mu.OZ.AU
Thu Jan 8 16:35:28 AEDT 2004


I am in the process of changing a compiler data structure from a map to a
bimap, and in the process of adding some needed new operations to bimap,
found a couple of problems.

The first is that bimap__set wasn't ensuring the bijective property.
If you had a bimap containing 1 <-> "one", and called bimap__set with
key 1 and value "uno", then the final forward map would be correct, but
the reverse map would still map "one" as well as "uno" to 1. Does anyone
have code that depends on the old, incorrect semantics of bimap__set?

The second is that bimap__reverse_lookup has signature
	bimap__reverse_lookup(bimap(K, V)::in, K::out, V::in)
instead of
	bimap__reverse_lookup(bimap(K, V)::in, V::in, K::out)
when the latter is better for currying and corresponds to a function form
more closely. Changing the signature of the existing predicate is out,
since existing code would silently do the wrong thing if K=V.
I added a function with signature
	bimap__reverse_lookup(bimap(K, V), V) = K
Do we need a predicate form with this argument order as well, and if so
what should be its name?

The third is that the bimap exports the concrete implementation of the
bimap(K, V) type, as well as an abstract declaration. I think this is
just a mistake, a matter of the :- implementation being a few lines too
late. Does anyone object to making the type abstract, with two new functions
to return the forward and reverse maps respectively? Without this, we
cannot to ensure the bijective property.

Zoltan.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------



More information about the developers mailing list