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

[Mark Brown]

On 05-Sep-2002, Fergus Henderson <fjh at cs.mu.OZ.AU> wrote:
> On 05-Sep-2002, Mark Brown <dougl at cs.mu.OZ.AU> wrote:
> > 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.

It isn't.  :-(

Apparently we've been assuming the following:

	compare((=), X, Y) implies X = Y

in which case stability is not an issue.  Is there any reason why this
assumption is necessary?  Sometimes more general orderings are useful,
as the ICFP2002 submission shows.

> Existing code which uses it might be depending on this.

Then it is in for a surprise!

> Also, stability is, as Ralph says, a desirable characteristic.

I agree.  The change to make it stable appears trivial, although I haven't
yet tried it.  I'll do that as part of the change.

Cheers,
Mark.

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