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

[Zoltan Somogyi]

On 06-Sep-2002, Ralph Becket <rafe at cs.mu.OZ.AU> wrote:
> > As I mentioned earlier, we apparently assume that Compare(X, Y, (=))
> > implies X = Y, so the above inconsistency is not an issue.  I'm prepared
> > to make the changes required, but I need some feedback on the following:
> > do we wish to keep this assumption or throw it out (I vote for the latter)?
> 
> Chuck it (only its converse should be valid.)

And the reason for that is that sorting usually works by comparing *keys*,
not entire items themselves.

At the moment, the user supplied Compare pred will in general do two things:
extract the keys from the two items and compare them. Equality of the keys
does not imply equality of the items unless you make the assumption that
keys are not duplicated in the list to be sorted, whereas the converse
should always hold, as Ralph says. (The reason why this hasn't been a problem
before is, I suspect, the fact that the assumption is usually true.)

The documentation should be rewritten with this in mind. We may even wish to
change the implementation to take *two* predicates: extracting the keys and
comparing keys.

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