[m-dev.] sorted_list_to_set

[Peter Moulder]

On Wed, Feb 08, 2006 at 03:07:35PM +1100, Mark Brown wrote:

 [set.sorted_list_to_set is documented to require the list not to contain
  duplicates, but currently doesn't make use of this condition: so it can
  only guarantee O(n) rather than O(1).

  set_ordlist.sorted_list_to_set does not require the list to be
  uniqued.
 
  It is beneficial for same-named procedures to have the same
  semantics.

  It is desirable to do this conversion "as efficiently as possible".]
 
Other relevant point:

  It is relatively common to have lists that are not only sorted but
  uniqued, e.g. because of various -to-sorted-list procedures in the
  standard library that guarantee uniquedness.

> Are there any strong objections to changing the meaning of the latter
> so that it makes that assuption?  The change would not be backwards
> compatible.

I'm concerned by the backwards-incompatible nature of the proposed
change: it seems quite reasonable to me for someone to call sort on a
list of integers and later pass that to set_ordlist.sorted_list_to_set.

If I understand correctly (e.g. from "as efficiently as possible"), the
proposed implementation is simply

  set.sorted_list_to_set(L) = L.

with no checking: allowing various other predicates (singleton_set,
equal, remove, ...) to silently give the wrong result if the user passed
a non-uniqued sorted list to some previous sorted_list_to_set call.
This could lead to problems that are rather hard to debug.

How about either introducing a new pred/func named
sorted_uniqued_list_to_set (which has the benefit that programmers are
more likely to make sure that the list really is uniqued); or having at
least one stable release that does an explicit check?

pjrm.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------