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

[Fergus Henderson]

On 05-Sep-2002, Mark Brown <dougl at cs.mu.OZ.AU> wrote:
> Actually, I've just thought of a potential problem with this change.  The
> problem is that if list__sort is not stable, then the output of the new
> predicate is not well defined (that is, there would be more than one
> solution that fits the specification).  Is list__sort meant to be stable?

AFAIK we didn't consider this issue until now.

The current implementation uses merge sort, which should be stable.
Existing code which uses it might be depending on this.
Also, stability is, as Ralph says, a desirable characteristic.
The only reason to avoid it is that sometimes it comes at the
expense of performance, but given that we are doing a non-destructive
sort on lists, I think that merge sort will perform reasonably well.
For the standard library, the portability advantages of specifying
a stable sort are fairly persuasive, IMHO.  So, I think we should
go ahread and say that it is meant to be stable.

It would be good if you could
	(1) add a test case to verify that list__sort/3 is stable
	(1) document that list__sort/3 is stable

-- 
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
--------------------------------------------------------------------------