[m-rev.] for post-commit review: improve bag.m

[Julien Fischer]

Hi Zoltan,

> Improve bag.m.
> 
> library/bag.m:
>     The old implementations of bag.subtract, bag.least_upper_bound,
>     bag.union, bag.intersect iterated over their second bag arguments,
>     and did a logarithmic amount of work in each iteration. This is good
>     if the second bag is small, but not if it is big. Keep those
>     implementations as the implementation of bag.subtract_small,
>     bag.least_upper_bound_small etc, and replace the implementation
>     of bag.subtract etc with code that iterates over the assoc_list version
>     of both bags. This does work that linear in total size of the two sets.

This aspect of the change needs to be mentioned in the NEWS file.

>     Replace the implementation of bag.subset_compare with one
>     that actually works.
>
>     Replace the implementation of bag.is_subbag with one that
>     does significantly less work.
>
>     Group related predicates together.
>
>     Improve the documentation of the exported predicates.
>
>     Use a more descriptive and more consistent set of variable names.

...

> diff --git a/library/bag.m b/library/bag.m
> index f309954..327ff35 100644
> --- a/library/bag.m
> +++ b/library/bag.m
> @@ -26,88 +26,74 @@

...

> +    % Given a bag, produce a set containing all the values in the bag.
> +    % NOTE_TO_IMPLEMENTORS The _without_duplicates suffix is redundant.
> +    %
> +:- func to_set(bag(T)) = set(T).
> +:- func to_set_without_duplicates(bag(T)) = set(T).
> +:- pred to_set_without_duplicates(bag(T)::in, set(T)::out) is det.

The suffix versions should be deprecated.

...

>      % Compares the two bags, and returns whether the first bag is a
>      % subset (<), is equal (=), or is a superset (>) of the second.
> +    % Fails if the two bags are incomparable.
> +    %
> +    % Examples:
>      % subset_compare(<, {apple, orange}, {apple, apple, orange}).
>      % subset_compare(=, {apple, orange}, {apple, orange}).
>      % subset_compare(>, {apple, apple, orange}, {apple, orange}).
> @@ -243,6 +297,8 @@
>  :- pred subset_compare(comparison_result::out, bag(T)::in, bag(T)::in)
>      is semidet.

There's another existing issue here: it's a little unusual to have
a semidet comparison predicate -- the ordering of the arguments suggests
that this predicate is intended as such -- so we should at least add
det_subset_compare (e.g. so that it is possible to call list.sort/3 on
lists of bags using the subset ordering).

...

>  %---------------------------------------------------------------------------%
>  %---------------------------------------------------------------------------%
> 
> @@ -303,364 +371,689 @@
>  :- type bag(T)
>      --->    bag(map(T, int)).
> 
> +:- inst empty_list
> +    --->    [].
> +:- inst nonempty_list
> +    --->    [ground | ground].

Why do we need a local definition of the second inst when the list module
already exports non_empty_list/0?  (I would delete both of them from here and
add the inst empty_list/0 to the list module.)

The rest of the diff looks ok.

Julien.