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

[Mark Brown]

Hi,

This is for review by Fergus.  I was motivated to make this change
because of a bug I introduced (and then fixed) in the ICFP submission;
I expected list__sort_and_remove_dups/3 to behave the way that
list__sort_and_remove_equivs/3 now does.

Cheers,
Mark.

Estimated hours taken: 0.5
Branches: main

library/list.m:
	Add list__sort_and_remove_equivs/3, which is the same as
	list__sort_and_remove_dups/3 except that we use the equivalence
	relation implied by the comparison predicate, instead of the usual
	equality.

	Clarify the existing comment on list__sort_and_remove_dups/3, to
	make it clear what its behaviour is.

tests/hard_coded/Mmakefile:
tests/hard_coded/sort_and_remove_dups.exp:
tests/hard_coded/sort_and_remove_dups.m:
	A test case for list__sort_and_remove_{dups,equivs}/3.

Index: library/list.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/list.m,v
retrieving revision 1.107
diff -u -r1.107 list.m
--- library/list.m	18 Aug 2002 09:41:37 -0000	1.107
+++ library/list.m	5 Sep 2002 05:59:21 -0000
@@ -645,12 +645,33 @@
 
 	% list__sort_and_remove_dups(Compare, Unsorted, Sorted) is true iff
 	% Sorted is a list containing the same elements as Unsorted, but with
-	% any duplicates removed. Where Sorted is a sorted list, with respect
-	% to the ordering defined by the predicate term Compare.
+	% any duplicates 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 duplicates if they are equal
+	% according to the usual equality, as opposed to the equivalence
+	% implied by Compare.
 :- pred list__sort_and_remove_dups(pred(X, X, comparison_result), list(X),
 	list(X)).
 :- mode list__sort_and_remove_dups(pred(in, in, out) is det, in, out) is det.
 
+	% 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.
+
+	% 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.
+
 	% list__merge(Compare, As, Bs, Sorted) is true iff Sorted is a
 	% list containing the elements of As and Bs in the order implied
 	% by their sorted merge. The ordering of elements is defined by
@@ -1064,6 +1085,24 @@
 		list__remove_adjacent_dups_2(Xs, X1, L0)
 	).
 
+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)
+	;
+		L = [X0 | L0],
+		list__remove_adjacent_equivs_2(P, Xs, X1, L0)
+	).
+
 %-----------------------------------------------------------------------------%
 
 list__zip([], Bs, Bs).
@@ -1392,6 +1431,10 @@
 list__sort_and_remove_dups(P, L0, L) :-
 	list__sort(P, L0, L1),
 	list__remove_adjacent_dups(L1, L).
+
+list__sort_and_remove_equivs(P, L0, L) :-
+	list__sort(P, L0, L1),
+	list__remove_adjacent_equivs(P, L1, L).
 
 list__sort(P, L0, L) :-
 	list__length(L0, N),
Index: tests/hard_coded/Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.165
diff -u -r1.165 Mmakefile
--- tests/hard_coded/Mmakefile	4 Sep 2002 08:31:52 -0000	1.165
+++ tests/hard_coded/Mmakefile	5 Sep 2002 06:10:07 -0000
@@ -127,6 +127,7 @@
 	setjmp_test \
 	shift_test \
 	solve_quadratic \
+	sort_and_remove_dups \
 	space \
 	special_char \
 	split_c_files \
Index: tests/hard_coded/sort_and_remove_dups.exp
===================================================================
RCS file: tests/hard_coded/sort_and_remove_dups.exp
diff -N tests/hard_coded/sort_and_remove_dups.exp
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ tests/hard_coded/sort_and_remove_dups.exp	5 Sep 2002 06:34:30 -0000
@@ -0,0 +1,3 @@
+[{2, 12}, {1, 11}, {4, 14}, {3, 13}, {2, 12}, {3, 999}, {2, 2222}]
+sort_and_remove_dups: [{1, 11}, {2, 12}, {2, 2222}, {3, 13}, {3, 999}, {4, 14}]
+sort_and_remove_equivs: [1, 2, 3, 4]
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.
+
+:- pred compare_first({int, int}, {int, int}, comparison_result).
+:- mode compare_first(in, in, out) is det.
+
+compare_first({A, _}, {B, _}, Result) :-
+	compare(Result, A, B).
+
+:- pred fst({int, int}, int).
+:- mode fst(in, out) is det.
+
+fst({A, _}, A).
+
+% Output:
+% [{2, 12}, {1, 11}, {4, 14}, {3, 13}, {2, 12}, {3, 999}, {2, 2222}]
+% sort_and_remove_dups: [{1,11}, {2,12}, {2,2222}, {3,13}, {3,999}, {4,14}]
+% sort_and_remove_equivs: [1, 2, 3, 4]
+
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------