Re: Traits, dictionaries

[scgmille@xxxxxxxxxxxxxxxxxx]

> I think the SRFI is only missing two important feature traits:
> 
>     reversible-collection?      supports collection-reverse-fold
>     finite-collection?          collection-fold will halt on its own

finite-collection? is arguably the same as (not (collection-size 
collection)).  Infinite collections *must* return #f from that function.

Others are permitted to do so if they cannot determine their own size 
efficiently.

I've added the reversible collection attribute to the SRFI and updated 
at http://sgmiller.org/code/srfi-44.html.  

> This sort of thing is also handy for collections like circular lists,
> wrap-around vectors, and similar collections.
Maybe, maybe not.  The semantics of collection-fold are such that
an enumeration over a collection should enumerate once over all the 
values in the collection unless halted by the folding function.

Circular lists and simliar collections can be created using the 
negative index trick hinted at by the SRFI, but I'm unsure whether 
folds should proceed indefinitely over finite collections.  Other 
thoughts?

> The mutable-collection? trait is essentially a performance trait. It
> tells you to prefer the *-proc!! interfaces over the functional
> interfaces. (By the way, I agree with Matthias Radestock: The ! and !!
> procedures seem redundant. Do you know of any case where it's important
> to actually distinguish between the two? It seems to me that you could
> always trivially implement ! by returning the result of !!.) It's also a
> feature trait, because it tells you about the interface, even if you
> merge ! and !!: It tells you that you're allowed to ignore the returned
> value of the mutable methods, because it's always eq? to the input
> collection.

The !/!! distinction is to aid in the readability of code primarily.  
Its unclear looking at the following code what will be returned if 
! were the same as !! without a test for mutable-collection?:

(let ([c (make-foo-collection)])
  (foo-add! c 3)
  (foo-add! c 4)
  (foo-add! c 5))

Thats a weak example, here's a better one.  Imagine this following piece
of code occurs in a program:

(define (add-two collection a b)
  (bag-add! collection a)
  (bag-add! collection b))

If ! is the same as !!, this code may break in a bizarre way if the 
input collection is changed at some point from a mutable to non-mutable
collection.  If it were bag-add!! instead, a clear error about the 
operation being undefined should be raised instead.


> 
> 1. The reversible-collection? and finite-collection? feature traits are
>    NECESSARY to implement several desirable collections.
finite-collection? may not be necessary.  Reversible is in.

> 
> 2. The bidirectional-collection? and random-access-collection?
>    performance traits would be HELPFUL for generic programming.
I'd prefer that be left to another SRFI.

> 
> 3. I recommend merging the ! and !! procedures unless there's a strong
>    argument not to.
See above.

> >> 2. Equivalence of dictionaries
> 
> > This is a weakness in the wording I imagine.  Dictionaries compare
> > keys and values using the same equivalence function, which takes two
> > values at a time, not key/value pairs.  The equivalence function would
> > be applied to two keys, one from each dictionary, then two the two
> > values from each dictionary mapping.
> 
> That's a reasonable default, but it must not be a requirement, because
> it makes some dictionaries impossible to implement!
> 
> For example, consider a dictionary that maps case-insensitive user IDs
> to case-sensitive user names. There's no straightforward way to
> implement this. You could do it by encapsulating the keys or values in
> some other data structure, but why? That's just a hack to accommodate an
> inflexible interface.
> 
> It would be better to have separate equivalence predicates for the keys
> and the values (if necessary). Here's how I'd spec the constructor:
> 
>     (unordered-dictionary [key-eqv? [val-eqv?]] pair ...)
>     (ordered-dictionary [less?] [val-eqv?] pair ...)
> 
> For unordered dictionaries, key-eqv? and val-eqv? both default to eqv?.
> Ordered dictionaries are similar, except that they can derive key-eqv?
> from less?, as long as it's a strict weak order (which includes < but
> not partial orders like <=).

I almost agree.  I'd prefer the value equivalence function be the 
default, as it fits with the rest of the SRFI that values, not keys, are
the default visible element of a dictionary when used ignorantly.

> 
> This complicates *-equivalence-function, since there's now more than one
> of them. I can think of three ways to deal with that:
> 
> "default" equivalence function operates on keys. I can think of two ways
> to fix *that*:
> 
> 2a. As above, but *-equivalence-function => *-value-equivalence-function.
> 
> Bad idea, because the equivalence function is supposed to "return true
> if they should be considered equivalent for the purposes of contains?,
> value insertion, removal, and key lookup."

I prefer making *-equivalence-function return the value equivalence 
function as above, but change the wording of the above sentence to 
match.

> 
> 1. Dictionaries MUST have separate key-eqv? and val-eqv? predicates.
Sure.

> 
> 2. Ordered dictionaries SHOULD derive key-eqv? from the ordering
>    predicate whenever possible. Specifically, they should encourage
>    strict weak orders and discourage partial orders, which makes the
>    less->eqv? conversion possible.
Sure.

> 3. A dictionary's *-equivalence-function SHOULD return the key
>    comparator. Dictionaries should have at least one additional accessor
>    to obtain the value comparator.
I argue it should return the value comparator, 
*-key-equivalence-function returns the key comparator, and specifying 
only one equivalence function causes both key and value to use said 
function.

	Scott

Attachment: pgpTm9qgPyJ5C.pgp
Description: PGP signature