Email list hosting service & mailing list manager

New draft (#2) of SRFI 153: Ordered Sets and Bagsw Arthur A. Gleckler (16 Jul 2017 04:54 UTC)
Re: New draft (#2) of SRFI 153: Ordered Sets and Bags Sudarshan S Chawathe (05 Aug 2017 22:23 UTC)
Re: New draft (#2) of SRFI 153: Ordered Sets and Bags John Cowan (06 Aug 2017 04:14 UTC)

Re: New draft (#2) of SRFI 153: Ordered Sets and Bags Sudarshan S Chawathe 05 Aug 2017 22:23 UTC

These comments refer to "Draft #2 published: 2017/7/15".  I'm sorry for
the length of this message, especially because many of the comments
likely reflect confusion on my part.  Many can probably be ignored.

- Is the recommendation to use SRFI-14 char-sets for characters
  motivated by (expected) performance benefits, or something else
  (such as compatibility with SRFI-13)?  A brief clarification would
  be useful.

- Specification, 3rd paragraph: Is it correct that for lists (when
  they are elements of an oset or obag), the "object" is the list
  (recursively) and not just the initial pair?

- I don't understand the second itemized point under "benefits to this
  convention" (assuming the ! versions of procedures are being used).
  It seems to me that if one decides to use the ! procedures on an
  oset, then the old version, if needed, needs to be saved separately
  by copying, etc.

- oset constructor: Seems implied by the description of oset/ordered,
  but is it correct that it is not an error to invoke the oset
  constructor with duplicated elements?  (A similar comment applies to
  oset-unfold.)

- It is not clear which element is retained in case of attempted
  addition of multiple equal-by-comparator elements (first/last)?
  This applies to both constructors oset and oset-unfold.  [Based on
  later material, it seems this is meant to be undefined, but a
  clarification either way would be helpful.]

- Is it correct that oset-contains? uses the oset's equality predicate
  to check membership?  (Seems implied, since no other equality
  predicate is mentioned, but it may be helpful to make it explicit,as
  is done for oset-member later.)

- Related to above, is it true that (oset-member xs k d) is equivalent to
  (if (oset-contains? xs k) xs d)?

- oset-search: Is the "expected to tail call..." interpreted as a
  "MUST tail call..." (in RFC 2119 terms)?  That is, calling the
  procedures in a non-tail position, or not at all, an error (or just
  potentially inefficient)?

- In the context of obags, the naming convention for "oset-delete" and
  "oset-delete-all" may be easy to misinterpret as referring to
  deleting just one or all matching elements (cf. Java's "remove" and
  "removeAll").  Could be just me!

- oset-map: The example has the order of comparator and proc reversed
  from the order in the signature.

- oset-map, last sentence in description: Should it read "... elements
  are not the same in the sense of eqv?..."?

- oset-map: The handling of duplicate elements mentions "omitted as in
  the oset constructor" but the oset constructor does not have the
  details (such as, which of several equal-by-comparator elements is
  retained).  Also applies to list->oset.

- Related to the above, it may be useful to include an example such as
  the following (corrected as needed), where list-length-comparator is
  equivalent to using integer-comparator on the lengths of the given
  lists.

  (oset-map (lambda (lst) (map number->string lst))
            list-length-comparator
            (oset equal? '(1) '(2) '(1 2) '(3 4)))
  => (oset list-length-comparator '("1") '("1" "2"))

- In general, I am a bit unsure of the handling of elements that are
  equal-by-comparator but otherwise distinguishable (by eqv?, eq?,
  equal?).

- Comparators: It may be nice if oset-comparator an obag-comparator
  did provide ordering predicates (so as to make it convenient to
  build osets of osets and so on).  Given the ordering of elements, a
  lexicographic ordering may make sense.

- oset=?, etc.: Probably obvious, but perhaps worth noting that "same"
  here refers to equal-by-comparator.

- oset-min-value and oset-max-value: These don't make sense to me.
  Are they left over from mappings?

- oset-element-predecessor and oset-element-successor: Is it an error
  if oset does not contain the given obj?  It would be nice if such
  use is permissible, and it should be easy to support in a
  search-tree-based implementation.  But the description seems to
  suggest otherwise.  In any case, a clarification would be helpful.

- Dividing osets: It seems useful to also allow both ends of a range
  to be specified, to get objects in the ranges [a,b], (a,b], etc.

- oset-catenate: Should "the oset element" read "a singleton oset
  containing element" or some such?

- Obag procedures section, first para: I am a bit confused here (and
  earlier, for osets) by the special consideration given to eqv? (v.,
  in particular, equal?).  Does the comment about eqv? also hold true
  if eqv? is replaced with equal? there?  (I think so, based on the
  following paragraph, but then I am confused as to why only eqv? is
  mentioned.)

- Would it make sense (perhaps in another SRFI if out of scope here)
  to define (o)bags that do separately store items that are
  equal-by-comparator?  I am thinking here of applications that may
  wish to use an obag for grouping objects that do need to be treated
  separately later.

- obag-product: Probably obvious, but may be useful to explicitly note
  that n should be an exact nonnegative integer.

- obag-for-each-unique and obag-fold-unique: It may be useful to add a
  note/reminder here that it is undefined which of a group of
  equal-by-comparator elements is given to proc.

- obag->alist: May be just me, but "car" and "cdr" may be clearer than
  "elements" and "values" for describing the alist, although the
  correspondence is fairly obvious.

- alist->obag and alist/ordered->obag: The comparator mentioned in the
  description is missing from the signature.

- alist->obag: What happens in case of an alist with multiple pairs with
  equal-by-comparator 'car's?  Are the number of occurrences summed as
  in oset-sum (or maxed as in oset-union)?

- Very minor points:

  - Abstract: The parenthetical remark seems a bit odd to me since
    osets and obags are not very common terms.  Perhaps the terms
    should be expanded here?

  - Rationale: Second sentence has an extra "and".

  - Specification, para 5: I believe "for" should read "from".

  - Linear update section, para 2: "so clients" -> "So clients" (or
    perhaps the preceding period should be a comma?)

Regards,

-chaw