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

Orthogonality issues

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