[m-rev.] for review: fix behaviour of bimap.from_assoc_list

Julien Fischer juliensf at cs.mu.OZ.AU
Thu Mar 10 16:00:06 AEDT 2005
Previous message: [m-rev.] for review: fix behaviour of bimap.from_assoc_list
Next message: [m-rev.] for review: fix behaviour of bimap.from_assoc_list
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
On Mon, 7 Mar 2005, Zoltan Somogyi wrote:

> On 07-Mar-2005, Julien Fischer <juliensf at cs.mu.OZ.AU> wrote:
> > Arguably we should do that but for the sake of backwards compatibility
> > I thought I would leave the existing version as det.  (I could add a
> > version semidet_from_assoc_list), although in the long run I would
> > prefer your suggestion as well.
> > Opinions?
>
> We should move straight to the long run. Any breakage should be minor and trivially
> fixed.
>

In view of that and the other review comments here is modified diff.  I've
also improved the documentation in the bimap module and added some new
higher-order predicates as well.

Estimated hours taken: 3
Branches: main, release

library/bimap.m:
	Document the procedures in this module much more then
	we currently do.  In particular, note conditions for
	which procedure fail or throw exceptions more carefully
	than we previously did.

	Change bimap.from_assoc_list so that it fails if the
	association list does not implicitly define a bijection.
	Previously, it has been possible to use this to create
	bimaps that were not bijective.  Add a det version
	called bimap.det_from_assoc_list.

	Add bimap.foldl2 and bimap.foldl3.

	Alter the ordering of predicate and function versions
	of the same procedure where they don't conform to
	our coding standard.

	Remove the comment at the head of the file that says
	that the implementation is a pair of maps.  Since the
	type has been abstract for a while now, the details
	of it's implementation are not useful.

	Add an end_module declaration to this module.

Julien.

Index: library/bimap.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/bimap.m,v
retrieving revision 1.16.2.2
diff -u -r1.16.2.2 bimap.m
--- library/bimap.m	7 Mar 2005 03:02:25 -0000	1.16.2.2
+++ library/bimap.m	10 Mar 2005 04:20:41 -0000
@@ -13,8 +13,6 @@
 % of (Key, Data) pairs which allows you to look up any Data item given the
 % Key.  A bimap also allows you to look up the Key given the Data.
 %
-% The implementation is a pair of maps.
-%
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%

@@ -30,150 +28,269 @@

 	% Initialize an empty bimap.
 	%
-:- pred bimap__init(bimap(K, V)::out) is det.
 :- func bimap__init = bimap(K, V).
+:- pred bimap__init(bimap(K, V)::out) is det.

 	% Check whether a bimap is empty.
 	%
 :- pred bimap__is_empty(bimap(K, V)::in) is semidet.

+	% Search the bimap.
+	% The first mode searches for a value given a key and the second
+	% mode searches for a key given a value.
+	%
 :- pred bimap__search(bimap(K, V), K, V).
 :- mode bimap__search(in, in, out) is semidet.
 :- mode bimap__search(in, out, in) is semidet.

-:- pred bimap__forward_search(bimap(K, V)::in, K::in, V::out) is semidet.
+	% Search the bimap for the value corresponding to a given key.
+	%
 :- func bimap__forward_search(bimap(K, V), K) = V is semidet.
+:- pred bimap__forward_search(bimap(K, V)::in, K::in, V::out) is semidet.

-:- pred bimap__reverse_search(bimap(K, V)::in, K::out, V::in) is semidet.
+	% Search the bimap for the key corresponding to the given value.
+	%
 :- func bimap__reverse_search(bimap(K, V), V) = K is semidet.
+:- pred bimap__reverse_search(bimap(K, V)::in, K::out, V::in) is semidet.

-:- pred bimap__lookup(bimap(K, V)::in, K::in, V::out) is det.
+	% Look up the value in the bimap corresponding to the given key.
+	% Throws an exception if the key is not present in the bimap.
+	%
 :- func bimap__lookup(bimap(K, V), K) = V.
+:- pred bimap__lookup(bimap(K, V)::in, K::in, V::out) is det.

-:- pred bimap__reverse_lookup(bimap(K, V)::in, K::out, V::in) is det.
+	% Look up the key in the bimap corresponding to the given value.
+	% Throws an exception if the value is not present in the bimap.
+	%
 :- func bimap__reverse_lookup(bimap(K, V), V) = K.
+:- pred bimap__reverse_lookup(bimap(K, V)::in, K::out, V::in) is det.

 	% Given a bimap, return a list of all the keys in the bimap.
 	%
-:- pred bimap__ordinates(bimap(K, V)::in, list(K)::out) is det.
 :- func bimap__ordinates(bimap(K, V)) = list(K).
+:- pred bimap__ordinates(bimap(K, V)::in, list(K)::out) is det.

 	% Given a bimap, return a list of all the data values in the bimap.
 	%
-:- pred bimap__coordinates(bimap(K, V)::in, list(V)::out) is det.
 :- func bimap__coordinates(bimap(K, V)) = list(V).
+:- pred bimap__coordinates(bimap(K, V)::in, list(V)::out) is det.

+	% Succeeds iff the bimap contains the given key.
+	%
 :- pred bimap__contains_key(bimap(K, V)::in, K::in) is semidet.

+	% Succeeds iff the bimap contains the given value.
+	%
 :- pred bimap__contains_value(bimap(K, V)::in, V::in) is semidet.

+	% Insert a new key-value pair into the bimap.
+	% Fails if either the key or value already exists.
+	%
+:- func bimap__insert(bimap(K, V), K, V) = bimap(K, V) is semidet.
 :- pred bimap__insert(bimap(K, V)::in, K::in, V::in, bimap(K, V)::out)
 	is semidet.
-:- func bimap__insert(bimap(K, V), K, V) = bimap(K, V) is semidet.

+	% As above but throws an exception if the key or value already
+	% exists.
+	%
+:- func bimap__det_insert(bimap(K, V), K, V) = bimap(K, V).
 :- pred bimap__det_insert(bimap(K, V)::in, K::in, V::in, bimap(K, V)::out)
 	is det.
-:- func bimap__det_insert(bimap(K, V), K, V) = bimap(K, V).

-:- pred bimap__set(bimap(K, V)::in, K::in, V::in, bimap(K, V)::out) is det.
+	% Update the key and value if already present, otherwise insert the
+	% new key and value.
+	%
+	% NOTE: setting the key-value pair (K, V) will remove the
+	%       key-value pairs (K, V1) and (K1, V) if they exist.
+	%
 :- func bimap__set(bimap(K, V), K, V) = bimap(K, V).
+:- pred bimap__set(bimap(K, V)::in, K::in, V::in, bimap(K, V)::out) is det.

-:- pred bimap__det_insert_from_assoc_list(assoc_list(K, V)::in,
-	bimap(K, V)::in, bimap(K, V)::out) is det.
+	% Insert key-value pairs from an association list into the given
+	% bimap.  Fails if the contents of the association list and the
+	% initial bimap do not implicitly form a bijection.
+	%
+:- func bimap__insert_from_assoc_list(assoc_list(K, V), bimap(K, V)) =
+	bimap(K, V) is semidet.
+:- pred bimap__insert_from_assoc_list(assoc_list(K, V)::in,
+	bimap(K, V)::in, bimap(K, V)::out) is semidet.
+
+	% As above but throws an exception if the association list and
+	% initial bimap are not implicitly bijective.
+	%
 :- func bimap__det_insert_from_assoc_list(assoc_list(K, V), bimap(K, V))
 	= bimap(K, V).
-
-:- pred bimap__det_insert_from_corresponding_lists(list(K)::in, list(V)::in,
+:- pred bimap__det_insert_from_assoc_list(assoc_list(K, V)::in,
 	bimap(K, V)::in, bimap(K, V)::out) is det.
+
+	% Insert key-value pairs from a pair of corresponding lists.
+	% Throws an exception if the lists are not of equal lengths
+	% or if they do not implicitly define a bijection.
+	%
 :- func bimap__det_insert_from_corresponding_lists(list(K), list(V),
 	bimap(K, V)) = bimap(K, V).
-
-:- pred bimap__set_from_assoc_list(assoc_list(K, V)::in,
+:- pred bimap__det_insert_from_corresponding_lists(list(K)::in, list(V)::in,
 	bimap(K, V)::in, bimap(K, V)::out) is det.
+
+	% Apply bimap.set to each key-value pair in the association
+	% list.  The key-value pairs from the association list may
+	% update existing keys and values in the bimap.
+	%
 :- func bimap__set_from_assoc_list(assoc_list(K, V), bimap(K, V))
 	= bimap(K, V).
-
-:- pred bimap__set_from_corresponding_lists(list(K)::in, list(V)::in,
+:- pred bimap__set_from_assoc_list(assoc_list(K, V)::in,
 	bimap(K, V)::in, bimap(K, V)::out) is det.
+
+	% As above but with a pair of corresponding lists in place
+	% of an association list.  Throws an exception if the lists
+	% are not of equal length.
+	%
 :- func bimap__set_from_corresponding_lists(list(K), list(V),
 	bimap(K, V)) = bimap(K, V).
+:- pred bimap__set_from_corresponding_lists(list(K)::in, list(V)::in,
+	bimap(K, V)::in, bimap(K, V)::out) is det.

 	% Delete a key-value pair from a bimap. If the key is not present,
 	% leave the bimap unchanged.
 	%
-:- pred bimap__delete_key(K::in, bimap(K, V)::in, bimap(K, V)::out) is det.
 :- func bimap__delete_key(bimap(K, V), K) = bimap(K, V).
+:- pred bimap__delete_key(K::in, bimap(K, V)::in, bimap(K, V)::out) is det.

 	% Delete a key-value pair from a bimap. If the value is not present,
 	% leave the bimap unchanged.
 	%
-:- pred bimap__delete_value(V::in, bimap(K, V)::in, bimap(K, V)::out) is det.
 :- func bimap__delete_value(bimap(K, V), V) = bimap(K, V).
+:- pred bimap__delete_value(V::in, bimap(K, V)::in, bimap(K, V)::out) is det.

-	% Apply bimap__delete_key to a list of keys.
+	% Apply bimap.delete_key to a list of keys.
 	%
+:- func bimap__delete_keys(bimap(K, V), list(K)) = bimap(K, V).
 :- pred bimap__delete_keys(list(K)::in, bimap(K, V)::in, bimap(K, V)::out)
 	is det.
-:- func bimap__delete_keys(bimap(K, V), list(K)) = bimap(K, V).

-	% Apply bimap__delete_value to a list of values.
+	% Apply bimap.delete_value to a list of values.
 	%
+:- func bimap__delete_values(bimap(K, V), list(V)) = bimap(K, V).
 :- pred bimap__delete_values(list(V)::in, bimap(K, V)::in, bimap(K, V)::out)
 	is det.
-:- func bimap__delete_values(bimap(K, V), list(V)) = bimap(K, V).

-	% bimap__overlay(BIMapA, BIMapB, BIMap):
+	% bimap.overlay(BIMapA, BIMapB, BIMap):
 	% Apply map__overlay to the forward maps of BIMapA and BIMapB,
 	% and compute the reverse map from the resulting map.
 	%
+:- func bimap__overlay(bimap(K, V), bimap(K, V)) = bimap(K, V).
 :- pred bimap__overlay(bimap(K, V)::in, bimap(K, V)::in, bimap(K, V)::out)
 	is det.
-:- func bimap__overlay(bimap(K, V), bimap(K, V)) = bimap(K, V).

 	% Convert a bimap to an association list.
 	%
-:- pred bimap__to_assoc_list(bimap(K, V)::in, assoc_list(K, V)::out) is det.
 :- func bimap__to_assoc_list(bimap(K, V)) = assoc_list(K, V).
+:- pred bimap__to_assoc_list(bimap(K, V)::in, assoc_list(K, V)::out) is det.

 	% Convert an association list to a bimap.
-	%
-:- pred bimap__from_assoc_list(assoc_list(K, V)::in, bimap(K, V)::out) is det.
-:- func bimap__from_assoc_list(assoc_list(K, V)) = bimap(K, V).
+	% Fails if the association list does not implicitly define
+	% a bijection, i.e. a key or value occurs multiple times in the
+	% association list.
+	%
+:- func bimap__from_assoc_list(assoc_list(K, V)) = bimap(K, V) is semidet.
+:- pred bimap__from_assoc_list(assoc_list(K, V)::in, bimap(K, V)::out)
+	is semidet.
+
+	% As above but throws an exception instead of failing if the
+	% association list does not implicitly defined a bijection.
+	%
+:- func bimap__det_from_assoc_list(assoc_list(K, V)) = bimap(K, V).
+:- pred bimap__det_from_assoc_list(assoc_list(K, V)::in, bimap(K, V)::out) is det.

+	% Convert a pair of lists into a bimap.
+	% Fails if the lists do not implicitly define a bijection or
+	% if the lists are of unequal length.
+	%
+:- func bimap__from_corresponding_lists(list(K), list(V)) = bimap(K, V)
+	is semidet.
 :- pred bimap__from_corresponding_lists(list(K)::in, list(V)::in,
+	bimap(K, V)::out) is semidet.
+
+	% As above but throws an exception instead of failing if the
+	% lists do not implicitly define a bijection or are of unequal
+	% length.
+	%
+:- func bimap__det_from_corresponding_lists(list(K), list(V)) = bimap(K, V).
+:- pred bimap__det_from_corresponding_lists(list(K)::in, list(V)::in,
 	bimap(K, V)::out) is det.
-:- func bimap__from_corresponding_lists(list(K), list(V)) = bimap(K, V).

+:- func bimap__apply_forward_map_to_list(bimap(K, V), list(K)) = list(V).
 :- pred bimap__apply_forward_map_to_list(bimap(K, V)::in, list(K)::in,
 	list(V)::out) is det.
-:- func bimap__apply_forward_map_to_list(bimap(K, V), list(K)) = list(V).

+:- func bimap__apply_reverse_map_to_list(bimap(K, V), list(V)) = list(K).
 :- pred bimap__apply_reverse_map_to_list(bimap(K, V)::in, list(V)::in,
 	list(K)::out) is det.
-:- func bimap__apply_reverse_map_to_list(bimap(K, V), list(V)) = list(K).

 	% Apply a transformation predicate to all the keys.
+	% Throws an exception if the resulting bimap is not bijective.
 	%
+:- func bimap__map_keys(func(V, K) = L, bimap(K, V)) = bimap(L, V).
 :- pred bimap__map_keys(pred(V, K, L)::in(pred(in, in, out) is det),
 	bimap(K, V)::in, bimap(L, V)::out) is det.
-:- func bimap__map_keys(func(V, K) = L, bimap(K, V)) = bimap(L, V).

 	% Apply a transformation predicate to all the values.
+	% Throws an exception if the resulting bimap is not bijective.
 	%
+:- func bimap__map_values(func(K, V) = W, bimap(K, V)) = bimap(K, W).
 :- pred bimap__map_values(pred(K, V, W)::in(pred(in, in, out) is det),
 	bimap(K, V)::in, bimap(K, W)::out) is det.
-:- func bimap__map_values(func(K, V) = W, bimap(K, V)) = bimap(K, W).

-	% Apply a transformation predicate to all the values.
+	% Perform a traversal of the bimap, applying an accumulator
+	% predicate for each key-value pair.
 	%
+:- func bimap__foldl(func(K, V, T) = T, bimap(K, V), T) = T.
 :- pred bimap__foldl(pred(K, V, T, T), bimap(K, V), T, T).
-:- mode bimap__foldl(pred(in, in, di, uo) is det, in, di, uo) is det.
 :- mode bimap__foldl(pred(in, in, in, out) is det, in, in, out) is det.
 :- mode bimap__foldl(pred(in, in, in, out) is semidet, in, in, out) is semidet.
-:- func bimap__foldl(func(K, V, T) = T, bimap(K, V), T) = T.
+:- mode bimap__foldl(pred(in, in, di, uo) is det, in, di, uo) is det.

+	% Perform a traversal of the bimap, applying an accumulator
+	% predicate with two accumulators for each key-value pair.
+	% (Although no more expressive than bimap.foldl, this is often
+	% a more convenient format, and a little more efficient).
+	%
+:- pred bimap__foldl2(pred(K, V, T, T, U, U), bimap(K, V), T, T, U, U).
+:- mode bimap__foldl2(pred(in, in, in, out, in, out) is det,
+	in, in, out, in, out) is det.
+:- mode bimap__foldl2(pred(in, in, in, out, in, out) is semidet,
+	in, in, out, in, out) is semidet.
+:- mode bimap__foldl2(pred(in, in, in, out, di, uo) is det,
+	in, in, out, di, uo) is det.
+:- mode bimap__foldl2(pred(in, in, di, uo, di, uo) is det,
+	in, di, uo, di, uo) is det.
+
+	% Perform a traversal of the bimap, applying an accumulator
+	% predicate with three accumulators for each key-value pair.
+	% (Although no more expressive than bimap.foldl, this is often
+	% a more convenient format, and a little more efficient).
+	%
+:- pred bimap__foldl3(pred(K, V, T, T, U, U, W, W), bimap(K, V),
+	T, T, U, U, W, W).
+:- mode bimap__foldl3(pred(in, in, in, out, in, out, in, out) is det,
+	in, in, out, in, out, in, out) is det.
+:- mode bimap__foldl3(pred(in, in, in, out, in, out, in, out) is semidet,
+	in, in, out, in, out, in, out) is semidet.
+:- mode bimap__foldl3(pred(in, in, in, out, in, out, di, uo) is det,
+	in, in, out, in, out, di, uo) is det.
+:- mode bimap__foldl3(pred(in, in, in, out, di, uo, di, uo) is det,
+	in, in, out, di, uo, di, uo) is det.
+:- mode bimap__foldl3(pred(in, in, di, uo, di, uo, di, uo) is det,
+	in, di, uo, di, uo, di, uo) is det.
+
+	% Extract a the forward map from the bimap, the map
+	% from key to value.
+	%
 :- func bimap__forward_map(bimap(K, V)) = map(K, V).

+	% Extract the reverse map from the bimap, the map
+	% from value to key.
+	%
 :- func bimap__reverse_map(bimap(K, V)) = map(V, K).

 %-----------------------------------------------------------------------------%
@@ -256,7 +373,15 @@
 		map__det_insert(Reverse1, V, K, Reverse),
 		Forward = Forward1
 	).
-
+
+bimap__insert_from_assoc_list(List, BM0) = BM :-
+	bimap__insert_from_assoc_list(List, BM0, BM).
+
+bimap__insert_from_assoc_list([], !BM).
+bimap__insert_from_assoc_list([ Key - Value | KeyValues], !BM) :-
+	bimap__insert(!.BM, Key, Value, !:BM),
+	bimap__insert_from_assoc_list(KeyValues, !BM).
+
 bimap__det_insert_from_assoc_list([], !BM).
 bimap__det_insert_from_assoc_list([Key - Value | KeysValues], !BM) :-
 	bimap__det_insert(!.BM, Key, Value, !:BM),
@@ -332,15 +457,26 @@
 bimap__to_assoc_list(bimap(Forward, _), L) :-
 	map__to_assoc_list(Forward, L).

-bimap__from_assoc_list(L, bimap(Forward, Reverse)) :-
-	map__from_assoc_list(L, Forward),
-	assoc_list__reverse_members(L, L1),
-	map__from_assoc_list(L1, Reverse).
+bimap__from_assoc_list(L, Bimap) :-
+	bimap__insert_from_assoc_list(L, bimap.init, Bimap).
+
+bimap__det_from_assoc_list(L) = Bimap :-
+	bimap__det_from_assoc_list(L, Bimap).
+
+bimap__det_from_assoc_list(L, Bimap) :-
+	bimap__det_insert_from_assoc_list(L, bimap.init, Bimap).

 bimap__from_corresponding_lists(Ks, Vs, BM) :-
 	assoc_list__from_corresponding_lists(Ks, Vs, L),
 	bimap__from_assoc_list(L, BM).

+bimap__det_from_corresponding_lists(Ks, Vs) = BM :-
+	bimap__det_from_corresponding_lists(Ks, Vs, BM).
+
+bimap__det_from_corresponding_lists(Ks, Vs, BM) :-
+	assoc_list__from_corresponding_lists(Ks, Vs, L),
+	bimap__det_from_assoc_list(L, BM).
+
 bimap__apply_forward_map_to_list(bimap(Forward, _), Ks, Vs) :-
 	map__apply_to_list(Ks, Forward, Vs).

@@ -350,22 +486,22 @@
 bimap__map_keys(KeyMap, BM0, BM) :-
 	bimap__to_assoc_list(BM0, L0),
 	bimap__map_keys_2(KeyMap, L0, [], L),
-	bimap__from_assoc_list(L, BM).
+	bimap__det_from_assoc_list(L, BM).

 bimap__map_keys(KeyMap, BM0) = BM :-
 	bimap__to_assoc_list(BM0, L0),
 	bimap__map_keys_func_2(KeyMap, L0, [], L),
-	bimap__from_assoc_list(L, BM).
+	bimap__det_from_assoc_list(L, BM).

 bimap__map_values(ValueMap, BM0, BM) :-
 	bimap__to_assoc_list(BM0, L0),
 	bimap__map_values_2(ValueMap, L0, [], L),
-	bimap__from_assoc_list(L, BM).
+	bimap__det_from_assoc_list(L, BM).

 bimap__map_values(ValueMap, BM0) = BM :-
 	bimap__to_assoc_list(BM0, L0),
 	bimap__map_values_func_2(ValueMap, L0, [], L),
-	bimap__from_assoc_list(L, BM).
+	bimap__det_from_assoc_list(L, BM).

 :- pred bimap__map_keys_2(pred(V, K, L)::in(pred(in, in, out) is det),
 	assoc_list(K, V)::in, assoc_list(L, V)::in, assoc_list(L, V)::out)
@@ -410,6 +546,12 @@
 bimap__foldl(Pred, bimap(Forward, _), List0, List) :-
 	map__foldl(Pred, Forward, List0, List).

+bimap__foldl2(Pred, bimap(Forward, _), !A, !B) :-
+	map__foldl2(Pred, Forward, !A, !B).
+
+bimap__foldl3(Pred, bimap(Forward, _), !A, !B, !C) :-
+	map__foldl3(Pred, Forward, !A, !B, !C).
+
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 % Ralph Becket <rwab1 at cl.cam.ac.uk> 29/04/99
@@ -493,3 +635,7 @@
 bimap__forward_map(bimap(Forward, _)) = Forward.

 bimap__reverse_map(bimap(_, Reverse)) = Reverse.
+
+%----------------------------------------------------------------------------%
+:- end_module bimap.
+%----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
Previous message: [m-rev.] for review: fix behaviour of bimap.from_assoc_list
Next message: [m-rev.] for review: fix behaviour of bimap.from_assoc_list
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the reviews mailing list