[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Orthogonality issues

This page is part of the web mail archives of SRFI 44 from before July 7th, 2015. The new archives for SRFI 44 contain all messages, not just those from before July 7th, 2015.

Bradd W. Szonye wrote:
> However, it just occurred to me that there's some ambiguity for
> ordered-collection -- dictionaries are usually in key order, but other
> collections are in value order. I think we actually need to separate
> them into "ordered-collection" and "key-ordered-collection."
> Otherwise, you'll have problems with polymorphism ....
> *-update is for sequences, *-update-key is for dictionaries. The
> reason for having two different functions is because key lookup is
> *not* the same thing as indexing ....

> *-remove takes a value out of a bag, and *-remove-key takes a key out
> of a dictionary. If you have a dictionary that is also a bag, those
> need to be two different methods.

And related to these: I forgot to mention it earlier, but I changed
collection-fold-keys to be defined *only* for dictionaries (not
sequences) in my revision. That's because:

1. If you overload them, you're screwed if you have a dictionary that is
   also a sequence (e.g., alists).

2. You can easily simulate collection-fold-indexes by passing the index
   as a seed and incrementing it with each enumeration.

In general, I tried to keep each interface distinct, so that "mixed
interface" collections still make sense. However, as the first quoted
paragraph states, "ordered-collection" is not very well defined.

I think you could resolve this by changing "order" from a property of
collections in general to a property of each collection type:

    ordered-bag, ordered-set: you can access/retrieve values in order
    ordered-sequence: ascending positions contain ascending values
    ordered-dictionary: you can access/retrieve keys in order

With this change, the semantics of *-ordering-function, *-fold-left, and
all other *-method-direction functions would depend on the ordering
semantics of *. For example, bag-ordering-function would give you an
ordering-function for values, and dictionary-ordering-function would
give you an ordering-function for keys. Here's the whole set:

    collection-fold: arbitrary order

    bag-fold: enumerate in arbitrary order
    ordered-bag-fold: enumerate in arbitrary order
    ordered-bag-fold-left: enumerate in bag order
    ordered-bag-fold-right: enumerate in reverse bag order

    set-fold: enumerate in arbitrary order
    ordered-set-fold: enumerate in arbitrary order
    ordered-set-fold-left: enumerate in bag order
    ordered-set-fold-right: enumerate in reverse bag order

    sequence-fold: enumerate sequence (forward)
    sequence-fold-left: enumerate sequence (forward)
    sequence-fold-right: enumerate reverse sequence
    ordered-sequence-fold[-left/right]: same thing

    dictionary-fold: enumerate key-value pairs
    ordered-dictionary-fold-left: enumerate pairs in key order
    ordered-dictionary-fold-right: enumerate pairs in reverse key order

I'm not sure about dictionaries. Which is best?

1. Dictionary-fold enumerates values, treating the dictionary like a
   bag, and dictionary-fold-keys works like the original fold-keys.
2. As #1, except dictionary-fold enumerates key-value pairs.
3. As #2, except that there is no fold-keys.

Again, there's the fundamental issue: "Is a dictionary a bag with keys,
or is it a collection of key-value pairs?" I truly cannot decide which
is better.
Bradd W. Szonye