[m-rev.] for review: list__sort_and_remove_equivs/3

[Fergus Henderson]

The same issue arises with list__merge_and_remove_dups,
so you might want to define list__merge_and_remove_equivs too.

On 05-Sep-2002, Mark Brown <dougl at cs.mu.OZ.AU> wrote:
> Index: library/list.m
> +	% list__sort_and_remove_equivs(Compare, Unsorted, Sorted) is true iff
> +	% Sorted is a list containing the same elements as Unsorted, but with
> +	% any equivalent elements removed, where Sorted is a sorted list with
> +	% respect to the ordering defined by the predicate term Compare.  Note
> +	% that elements are considered to be equivalent if the result of
> +	% comparison using Compare is '='.
> +:- pred list__sort_and_remove_equivs(pred(X, X, comparison_result), list(X),
> +	list(X)).
> +:- mode list__sort_and_remove_equivs(pred(in, in, out) is det, in, out) is det.

The documentation here is not very precise/clear.
What does "with any equivalent elements removed" mean?
- equivalent to what?  each other? 
- if so, does that mean that all elements which are equivalent to any
  other element in the list are removed?
  i.e. sort_and_remove_equivs(compare, [1,1,1], L) returns L = []??
  Obviously that is not what was intended, but that's the most natural
  interpretation of the words.
- if two elements are equivalent, which one gets kept in the output list?

> +	% list__remove_adjacent_equivs(P, L0, L) is true iff L is the result
> +	% of replacing every sequence of equivalent elements in L0 with a
> +	% single such element.  Elements are considered equivalent if the
> +	% comparison predicate compare returns '='.
> +:- pred list__remove_adjacent_equivs(pred(X, X, comparison_result), list(X),
> +	list(X)).
> +:- mode list__remove_adjacent_equivs(pred(in, in, out) is det, in, out) is det.

Again the documentation should say which of the equivalent elements is
kept -- e.g. is it the first occurrence, or the last occurrence?
Probably it would be best to keep the first occurrence.

> +list__remove_adjacent_equivs(_, [], []).
> +list__remove_adjacent_equivs(P, [X | Xs], L) :-
> +	list__remove_adjacent_equivs_2(P, Xs, X, L).
> +
> +:- pred list__remove_adjacent_equivs_2(pred(T, T, comparison_result),
> +	list(T), T, list(T)).
> +:- mode list__remove_adjacent_equivs_2(pred(in, in, out) is det, in, in, out)
> +	is det.
> +
> +list__remove_adjacent_equivs_2(_, [], X, [X]).
> +list__remove_adjacent_equivs_2(P, [X1 | Xs], X0, L) :-
> +	(P(X0, X1, (=)) ->
> +		list__remove_adjacent_equivs_2(P, Xs, X1, L)

It would be better to pass X0 rather than X1 here, so as to
keep the first occurrence rather than the last occurrence.

> Index: tests/hard_coded/sort_and_remove_dups.m
> ===================================================================
> RCS file: tests/hard_coded/sort_and_remove_dups.m
> diff -N tests/hard_coded/sort_and_remove_dups.m
> --- /dev/null	1 Jan 1970 00:00:00 -0000
> +++ tests/hard_coded/sort_and_remove_dups.m	5 Sep 2002 06:33:58 -0000
> @@ -0,0 +1,42 @@
> +:- module sort_and_remove_dups.
> +:- interface.
> +:- import_module io.
> +
> +:- pred main(io__state::di, io__state::uo) is det.
> +
> +:- implementation.
> +:- import_module list, int.
> +
> +main -->
> +	{
> +		L = [{2, 12}, {1, 11}, {4, 14}, {3, 13},
> +			{2, 12}, {3, 999}, {2, 2222}]
> +	},
> +	{ list__sort_and_remove_dups(compare_first, L, LD) },
> +	{ list__sort_and_remove_equivs(compare_first, L, LE) },
> +	{ list__map(fst, LE, LE1) },
> +	io__write(L),
> +	io__nl,
> +	io__write_string("sort_and_remove_dups: "),
> +	io__write(LD),
> +	io__nl,
> +	io__write_string("sort_and_remove_equivs: "),
> +	io__write(LE1),
> +	io__nl.

The test case should print the value of LE, not
the value of LE1.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------