[m-rev.] for review: Implement map.equal/2
Paul Bone
paul at bone.id.au
Fri Oct 18 15:12:22 AEDT 2013
For review.
Branches: release, master
I'm keen to get this into the next point release so that MCit can use it.
Implement map.equal/2
The equality test operation on 2-3-4 trees tests if they are structurally
equal. They might also be considered equal if their sets of key-value pairs
are equivalent. I've created an equal/2 predicate in the tree234 and
map modules in the standard library to test this.
library/tree234.m:
Implement a predicate to test for tree234 equivalence.
library/map.m:
Forward map.equal/2 to tree234.equal/2.
NEWS:
Announce this change in the news file.
tests/general/map_equal.m:
tests/general/map_equal.exp:
Add test case for map.equal/2
tests/general/Mmakefile:
Include the new test case.
---
NEWS | 4 ++
library/map.m | 21 +++++++
library/tree234.m | 131 +++++++++++++++++++++++++++++++++++++++++++-
tests/general/Mmakefile | 1 +
tests/general/map_equal.exp | 10 ++++
tests/general/map_equal.m | 65 ++++++++++++++++++++++
6 files changed, 231 insertions(+), 1 deletion(-)
create mode 100644 tests/general/map_equal.exp
create mode 100644 tests/general/map_equal.m
diff --git a/NEWS b/NEWS
index 2fed589..061e073 100644
--- a/NEWS
+++ b/NEWS
@@ -18,6 +18,10 @@ This is a bug-fix release.
call modulo constructor optimisation on the Java and (probably) C#
grades. (Bug #300)
+Changes to the Mercury standard library:
+
+* Equality predicates are now defined for 2-3-4 trees and maps.
+
NEWS for Mercury 13.05.1
------------------------
diff --git a/library/map.m b/library/map.m
index 3eb8d02..c1d6224 100644
--- a/library/map.m
+++ b/library/map.m
@@ -19,6 +19,15 @@
% tree234.m. Virtually all the predicates in this file just
% forward the work to the corresponding predicate in tree234.m.
%
+% Note: 2-3-4 trees do not have a canonical representation for any given
+% map. Therefore, two maps with the same key-value pairs may have different
+% internal representations. This means that two maps with the same
+% key-value pairs that were constructed differently may fail to unify or
+% compare as unequal, for example if items are inserted into one of the maps
+% in a different order. This behaviour may change in the future. See
+% map.equal/2 below which can be used to test if two maps have the same
+% key-value pairs.
+%
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
@@ -49,6 +58,15 @@
%
:- pred map.is_empty(map(_, _)::in) is semidet.
+ % True if both maps have the same key-value pairs, regardless of how the
+ % maps were constructed.
+ %
+ % Unifying maps does not work as one might expect because the internal
+ % structure of two equivalent maps (according to this predicate) may be
+ % different.
+ %
+:- pred map.equal(map(K, V)::in, map(K, V)::in) is semidet.
+
% Check whether map contains key
%
:- pred map.contains(map(K, _V)::in, K::in) is semidet.
@@ -796,6 +814,9 @@ map.singleton(K, V) =
map.is_empty(M) :-
tree234.is_empty(M).
+map.equal(MapA, MapB) :-
+ tree234.equal(MapA, MapB).
+
map.contains(Map, K) :-
map.search(Map, K, _).
diff --git a/library/tree234.m b/library/tree234.m
index 718f6ab..21a33d4 100644
--- a/library/tree234.m
+++ b/library/tree234.m
@@ -37,6 +37,8 @@
:- pred tree234.is_empty(tree234(K, V)::in) is semidet.
+:- pred tree234.equal(tree234(K, V)::in, tree234(K, V)::in) is semidet.
+
%----------------------%
:- pred tree234.member(tree234(K, V)::in, K::out, V::out) is nondet.
@@ -567,6 +569,7 @@
:- import_module int.
:- import_module io.
:- import_module pair.
+:- import_module private_builtin.
:- import_module require.
:- import_module set.
:- import_module string.
@@ -607,6 +610,132 @@ tree234.singleton(K, V) = two(K, V, empty, empty).
tree234.is_empty(Tree) :-
Tree = empty.
+tree234.equal(MapA, MapB) :-
+ ( pointer_equal(MapA, MapB) ->
+ true
+ ;
+ equal(MapA, [MapB], [])
+ ).
+
+ % Use a stack to store the unexplored parts of B while you recurse on A
+ % matcking KV pairs. use two nested loops, the out loop recurses on A,
+ % the inner loop matches from B and the explicit stack.
+ %
+ % Note that B is conceptually the top of B's stack. Allowing us to use
+ % it to make pointer comprisons.
+ %
+:- pred equal(tree234(K, V)::in,
+ list(tree234(K, V))::in, list(tree234(K, V))::out) is semidet.
+
+equal(MapA, !StackB) :-
+ (
+ !.StackB = [MapB | !:StackB],
+ pointer_equal(MapA, MapB)
+ ->
+ true
+ ;
+ require_complete_switch [MapA]
+ (
+ MapA = empty
+ ;
+ MapA = two(K, V, Left, Right),
+ equal(Left, !StackB),
+ match_kv(K, V, !StackB),
+ equal(Right, !StackB)
+ ;
+ MapA = three(K1, V1, K2, V2, Left, Middle, Right),
+ equal(Left, !StackB),
+ match_kv(K1, V1, !StackB),
+ equal(Middle, !StackB),
+ match_kv(K2, V2, !StackB),
+ equal(Right, !StackB)
+ ;
+ MapA = four(K1, V1, K2, V2, K3, V3,
+ Left, MidLeft, MidRight, Right),
+ equal(Left, !StackB),
+ match_kv(K1, V1, !StackB),
+ equal(MidLeft, !StackB),
+ match_kv(K2, V2, !StackB),
+ equal(MidRight, !StackB),
+ match_kv(K3, V3, !StackB),
+ equal(Right, !StackB)
+ )
+ ).
+
+:- pred match_kv(K::in, V::in,
+ list(tree234(K, V))::in, list(tree234(K, V))::out) is semidet.
+
+match_kv(K, V, !Stack) :-
+ !.Stack = [B | !:Stack],
+ match_kv(K, V, B, !Stack).
+
+ % match_kv(K, V, Top, !Stack)
+ %
+ % Match a key-value pair against one item from the stack of trees.
+ % If the match is successful then the matched item from the stack is
+ % updated. Top is the top of the input stack.
+ %
+:- pred match_kv(K::in, V::in, tree234(K, V)::in,
+ list(tree234(K, V))::in, list(tree234(K, V))::out) is semidet.
+
+match_kv(K, V, B, !Stack) :-
+ require_complete_switch [B]
+ (
+ B = empty,
+ % This case is rarely executed, because empty items are never put on
+ % the stack within match_kv/4 or match_kv/5.
+ match_kv(K, V, !Stack)
+ ;
+ B = two(K1, V1, Left, Right),
+ ( Left = empty ->
+ % Try to match the items.
+ K = K1,
+ V = V1,
+ % Update stack and return.
+ ( Right \= empty ->
+ !:Stack = [Right | !.Stack]
+ ;
+ true
+ )
+ ;
+ % Break up this node and recurse
+ !:Stack = [two(K1, V1, empty, Right) | !.Stack],
+ match_kv(K, V, Left, !Stack)
+ )
+ ;
+ B = three(K1, V1, K2, V2, Left, Middle, Right),
+
+ % This case has the same structure as the one above.
+ ( Left = empty ->
+ K = K1,
+ V = V1,
+
+ % We've eliminated Left and V1-V2, so we can build a two node
+ % from the rest of the three node.
+ !:Stack = [two(K2, V2, Middle, Right) | !.Stack]
+ ;
+ !:Stack = [three(K1, V1, K2, V2, empty, Middle, Right) |
+ !.Stack],
+ % Pull the leftmost node out and try to match on it.
+ match_kv(K, V, Left, !Stack)
+ )
+ ;
+ B = four(K1, V1, K2, V2, K3, V3, Left, MidLeft, MidRight, Right),
+
+ % This case has the same structure as the previous two cases.
+ ( Left = empty ->
+ K = K1,
+ V = V1,
+ !:Stack = [three(K2, V2, K3, V3, MidLeft, MidRight, Right) |
+ !.Stack]
+ ;
+ !:Stack = [four(K1, V1, K2, V2, K3, V3, empty, MidLeft,
+ MidRight, Right)
+ | !.Stack],
+ match_kv(K, V, Left, !Stack)
+ )
+ ).
+
%------------------------------------------------------------------------------%
%------------------------------------------------------------------------------%
@@ -3143,7 +3272,7 @@ tree234.keys_and_values_acc(three(K0, V0, K1, V1, T0, T1, T2),
!:Values = [V0 | !.Values],
tree234.keys_and_values_acc(T0, !Keys, !Values).
tree234.keys_and_values_acc(four(K0, V0, K1, V1, K2, V2, T0, T1, T2, T3),
- !Keys, !Values) :-
+ !Keys, !Values) :-
tree234.keys_and_values_acc(T3, !Keys, !Values),
!:Keys = [K2 | !.Keys],
!:Values = [V2 | !.Values],
diff --git a/tests/general/Mmakefile b/tests/general/Mmakefile
index c6a8c7b..b83817f 100644
--- a/tests/general/Mmakefile
+++ b/tests/general/Mmakefile
@@ -37,6 +37,7 @@ ORDINARY_PROGS= \
io_regression \
liveness \
liveness2 \
+ map_equal \
mode_inf \
mode_inf_bug \
mode_inference_reorder \
diff --git a/tests/general/map_equal.exp b/tests/general/map_equal.exp
new file mode 100644
index 0000000..b2f4290
--- /dev/null
+++ b/tests/general/map_equal.exp
@@ -0,0 +1,10 @@
+Map1 = Map1: unifiable, equal
+Map1 = Map1Copy: unifiable, equal
+Map1 = Map2: not unifiable, not equal
+Map2 = Map1: not unifiable, not equal
+Map1 = empty: not unifiable, not equal
+empty = Map1: not unifiable, not equal
+empty = empty: unifiable, equal
+empty = copy(empty): unifiable, equal
+Map3 = Map4: not unifiable, equal
+Map4 = Map3: not unifiable, equal
diff --git a/tests/general/map_equal.m b/tests/general/map_equal.m
new file mode 100644
index 0000000..a025085
--- /dev/null
+++ b/tests/general/map_equal.m
@@ -0,0 +1,65 @@
+%------------------------------------------------------------------------------%
+% map_equal.m
+% Paul Bone
+% vim: ft=mercury ff=unix ts=4 sw=4 et
+%------------------------------------------------------------------------------%
+
+:- module map_equal.
+
+:- interface.
+
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+%------------------------------------------------------------------------------%
+%------------------------------------------------------------------------------%
+
+:- implementation.
+
+:- import_module list.
+:- import_module map.
+:- import_module pair.
+:- import_module string.
+
+%------------------------------------------------------------------------------%
+
+main(!IO) :-
+ List1 = [1 - 1, 2 - 2, 3 - 3, 5 - 5, 6 - 6,
+ 7 - 7, 9 - 9, 10 - 10],
+ map.from_assoc_list(List1, Map1),
+ test("Map1 = Map1", Map1, Map1, !IO),
+ copy(Map1, Map1Copy),
+ test("Map1 = Map1Copy", Map1, Map1Copy, !IO),
+ set(7, 49, Map1, Map2),
+ test("Map1 = Map2", Map1, Map2, !IO),
+ test("Map2 = Map1", Map2, Map1, !IO),
+
+ EmptyMap = map.init,
+ test("Map1 = empty", Map1, EmptyMap, !IO),
+ test("empty = Map1", EmptyMap, Map1, !IO),
+ test("empty = empty", EmptyMap, EmptyMap, !IO),
+ copy(EmptyMap, EmptyMap2),
+ test("empty = copy(empty)", EmptyMap, EmptyMap2, !IO),
+
+ map.from_assoc_list(List1, Map3),
+ map.from_assoc_list(reverse(List1), Map4),
+ test("Map3 = Map4", Map3, Map4, !IO),
+ test("Map4 = Map3", Map3, Map4, !IO).
+
+:- pred test(string::in, map(K, V)::in, map(K, V)::in, io::di, io::uo) is det.
+
+test(Name, A, B, !IO) :-
+ ( map.equal(A, B) ->
+ EqualRes = "equal"
+ ;
+ EqualRes = "not equal"
+ ),
+ ( unify(A, B) ->
+ UnifyRes = "unifiable"
+ ;
+ UnifyRes = "not unifiable"
+ ),
+ io.format("%s: %s, %s\n", [s(Name), s(UnifyRes), s(EqualRes)], !IO).
+
+%------------------------------------------------------------------------------%
--
1.8.4.rc3
More information about the reviews
mailing list