[m-rev.] for review 2/3: Implement map.equivalent/2

[Julien Fischer]

Hi Paul,

On Fri, 28 Jun 2013, Paul Bone wrote:

> Implement map.equivalent/2

A better name would be: map.equal/2.
(That name is more consistent with that of similar predicates throughout
the rest of the standard library, for example set_tree234.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 equivalent/2 predicate in the tree234 and
> map modules in the standard library to test this.

I suggest:

    Add a new predicate, map.equal/2, that can be used to test whether
    two maps contain the same set of key-value pairs.  Unifying two maps
    will not do this as the standard defintion of equality for 234-trees
    is structural equality.

>
> library/tree234.m:
>    Implement a predicate to test for tree234 equivalence.

You should probably add a similar predicate to the rbtree and assoc_list
modules.  It's useful if all the modules in the standard library that
provide a map ADT provide similar functionality.

>
> NEWS:
>    Announce this change in the news file.

Or just:

      Announce the above changes.

("in the new file" seems a bit redundant, given that the file in
question *is* the NEWS file.)

...

> diff --git a/NEWS b/NEWS
> index d3c6eac..03ed031 100644
> --- a/NEWS
> +++ b/NEWS
> @@ -11,6 +11,10 @@ This is a bug-fix release.
>   for shared libraries and the LD_LIBFLAGS and EXTRA_LD_LIBFLAGS mmake
>   variables.  (Bug #288)
>
> +Changes to the Mercury standard library:
> +
> +* Equality predicates are now defined for 2-3-4 trees and maps.

Change this to:

    * We have added the predicate map.equal/2, which can be used to
      test whether two maps contain the same set of key-value pairs.
      Similarly, we have added the predicate tree234.equal/2.

...

> diff --git a/library/map.m b/library/map.m
> index 3eb8d02..c864a23 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.equivalent/2 below which can be used to test if two maps have the same
> +% key-value pairs.

For the last sentence I suggest:

     Use the predicate map.equal/2 if you want to test if two maps
     contain the same set of key-value pairs.

Can you generalise the above  so that the advice in that paragraph is not so
234-tree specific.  (In principle, we should be able to change the
underlying implementation for maps, although in practice I cannot see us
ever doing so.)

> %-----------------------------------------------------------------------------%
> %-----------------------------------------------------------------------------%
>
> @@ -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.
> +    %

I suggest the following:

     % map.equal(MapA, MapB):
     % True iff `MapA' and `MapB' contain the same set of key-value pairs.

> +:- pred map.equivalent(map(K, V)::in, map(K, V)::in) is semidet.
> +
>     % Check whether map contains key
>     %

While you're at it, there's a full stop missing after the word "key"
there.

> :- pred map.contains(map(K, _V)::in, K::in) is semidet.

...

> diff --git a/library/tree234.m b/library/tree234.m
> index 718f6ab..525dbe6 100644
> --- a/library/tree234.m
> +++ b/library/tree234.m

...


> +tree234.equivalent(MapA, MapB) :-
> +    ( pointer_equals(MapA, MapB) ->
> +        true
> +    ;
> +        equivalent(MapA, [MapB], [])
> +    ).
> +
> +    % Use a stack to store the unexplored parts of B while you recurse on A

    while doing an inorder traversal of A

> +    % matcking KV pairs.  use two nested loops, the out loop recurses on A,

s/matcking/matching/

s/use/Use/

s/out/outer/

> +    % 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.

Fix your grammar in that last sentence.

> +    %
> +:- pred equivalent(tree234(K, V)::in,
> +    list(tree234(K, V))::in, list(tree234(K, V))::out) is semidet.
> +
> +equivalent(MapA, !StackB) :-
> +    (
> +        !.StackB = [MapB | !:StackB],
> +        pointer_equals(MapA, MapB)
> +    ->
> +        true
> +    ;
> +        require_complete_switch [MapA]
> +        (
> +            MapA = empty

That doesn't look right -- shouldn't we fail unless MapB (and the rest
of the stack) is also empty?

> +        ;
> +            MapA = two(K, V, Left, Right),
> +            equivalent(Left, !StackB),
> +            match_kv(K, V, !StackB),
> +            equivalent(Right, !StackB)
> +        ;
> +            MapA = three(K1, V1, K2, V2, Left, Middle, Right),
> +            equivalent(Left, !StackB),
> +            match_kv(K1, V1, !StackB),
> +            equivalent(Middle, !StackB),
> +            match_kv(K2, V2, !StackB),
> +            equivalent(Right, !StackB)
> +        ;
> +            MapA = four(K1, V1, K2, V2, K3, V3,
> +                Left, MidLeft, MidRight, Right),
> +            equivalent(Left, !StackB),
> +            match_kv(K1, V1, !StackB),
> +            equivalent(MidLeft, !StackB),
> +            match_kv(K2, V2, !StackB),
> +            equivalent(MidRight, !StackB),
> +            match_kv(K3, V3, !StackB),
> +            equivalent(Right, !StackB)
> +        )
> +    ).

Please post a revised diff once you have addressed the above comments.

Cheers,
Julien.