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: >> 1. Bidirectionality and folding scgmille@xxxxxxxxxxxxxxxxxx wrote: > Perhaps the real solution is to make it optional that an ordered > collection support a reverse fold in addition to a > bidirectional-collection attribute. Yes, that would be the simplest way to do it. I've been thinking about how to deal with this without too much impact -- I don't want to hold up finalization too much. Your SRFI is very close to having excellent support for generic programming, but the collection "traits" fall just a little bit short. (Also, I have some concerns about dictionaries; see the end of the message.) In generic programming, it's important for data structures to support two kinds of traits: feature tests and performance traits. The feature tests are also important from the OO point of view, because they're effectively a kind of classification (inheritance)! The SRFI already reflects this partially, by treating ordered collections as a "class" in some contexts. In other words, bag? and ordered-collection? are both classes (from the OO point of view), and they're both feature traits (from the GP point of view). Methods like ordered-collection? and bag? are feature traits; they tells you which operations are valid on a collection. Methods like bidirectional-collection? describe performance traits; they tell you whether a given operation is "reasonable" for regular use. While I recommend the inclusion of some performance traits, they're not absolutely necessary. If you think it's too much trouble to include them, they could always be postponed to a "generic programming" SRFI based on SRFI-44. >> For most unidirectional collections, collection-reverse-fold could be >> an alias for collection-fold. For some of them, like unidirectional >> sequences (i.e., lists), it can provide an inefficient reverse fold. > I don't like that as much. Reverse fold should be undefined if its > semantics are the same as ordinary fold. On second thought, you're correct. I also made the mistake of conflating two different traits. There's a difference between asking whether you *can* reverse a collection and asking whether you *should*. > For sequences it should probably be defined even if inefficiently. > The programmer can use the bidirectional attribute to figure out if > this is going to be cost prohibitive. Right! What we actually need is a feature trait (reversible-collection?) and a performance trait (bidirectional-collection?). The former tells you whether you can reverse the collection; the latter tells you whether it's inexpensive. Vectors and proper lists are both reversible collections, but only the vector is bidirectional. 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 Justification: Consider the sequence "fibonacci," which generates its values instead of storing them. The Nth index of the sequence is the (N+1)th fibonacci number. This collection is ordered but not finite or reversible. You could use (sequence-ref fibonacci 3) to get the 4th fibonacci number. To get a subsequence, you can fold the collection: (define (fibonacci-subsequence start end) (define (f n v s e acc) (cond? ((< n s) (values #t s e acc)) ((<= n e) (values #t s e (cons v acc))) (else (values #f s e acc))) (let-values ((s e acc) (collection-fold-keys fibonacci f start end '())) (reverse acc)))) This gives us generated sequences like Clean and ML! (A later SRFI could extend your collection classes to standardize the interface for this kind of sequence.) Of course, you can't reverse fibonacci, even though it's ordered, so reversible-collection? must be false. Likewise, folder-procs must explicitly halt enumeration, so finite-collection? must be false. This sort of thing is also handy for collections like circular lists, wrap-around vectors, and similar collections. I also think it would be a good idea to include a few performance traits, like bidirectional-collection? and random-access-collection?, but you could leave that to a future GP SRFI if you think it's unecessary. However, it would be a good idea to at least explain the concept of performance traits, especially since you already have one: 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. Summary of my opinions on collection traits: 1. The reversible-collection? and finite-collection? feature traits are NECESSARY to implement several desirable collections. 2. The bidirectional-collection? and random-access-collection? performance traits would be HELPFUL for generic programming. 3. I recommend merging the ! and !! procedures unless there's a strong argument not to. >> 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 <=). This complicates *-equivalence-function, since there's now more than one of them. I can think of three ways to deal with that: 1. *-equivalence-function d => key-eqv? val-eqv? -or- *-equivalence-function d => (cons key-eqv? val-eqv?) Bad idea, because it breaks the Liskov substitution rule for polymorphism. (A subtype's methods should be more generous about inputs and stricter about outputs, which is false for this method. By the way, this is a good reason *not* to make sequence a subtype of dictionary -- while all sequences are a kind of dictionary, the interface would break the Liskov substitution rule.) 2. Introduce *-key-equivalence-function and *-value-equivalence-function, with *-equivalence-function => *-key-equivalence-function. Question: (collection-fold dict) enumerates the values, right? That seems like the right thing to do, because it makes for an interface similar to sequences. However, there are also good reasons to enumerate the keys or to enumerate key-value pairs (i.e., (cons key value)). I keep arguing with myself over what's the best "default" enumeration for dictionaries, and I can't make up my mind. Anyway, assuming that it does enumerate values, there's some potential here for confusion: The "default" enumerator operates on values, but the "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." 2b. As above, (collection-fold dict) enumerates key-value pairs, and *-equivalence-function tests two pairs for equivalence. That is, the "equivalence function" is a composition: (lambda (a b) (and (key-eqv? (car a) (car b)) (val-eqv? (cdr a) (cdr b)))) This is better than 2a, but it still isn't really testing for key equivalence. The basic problem here is that there are at least two major uses of the equivalence function: dealing with keys within a single collection, and comparing two entire collections. I think the best solution is #2: Introduce explicit key-eqv? and val-eqv? accessors, and have the "default" be the key comparator. Generic algorithms will therefore need to be careful about combining collection-fold with *-equivalence-function, but I think that's the least of all evils in this case. 3. Get rid of *-equivalence-function for dictionaries. If you don't like any of the alternatives, you could remove the accessor entirely. I don't think it's necessary, but it is a viable option. Summary of my opinions on dictionaries: 1. Dictionaries MUST have separate key-eqv? and val-eqv? predicates. 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. 3. A dictionary's *-equivalence-function SHOULD return the key comparator. Dictionaries should have at least one additional accessor to obtain the value comparator. -- Bradd W. Szonye http://www.szonye.com/bradd