On Thu, Oct 16, 2003 at 03:59:59AM -0700, Bradd W. Szonye wrote:
> Overall, I'm very pleased with this SRFI, and I'm looking forward to its
> finalization. Unfortunately, I have a few issues with it. Some of it's
> just minor editorial stuff, but I have two major issues.
>
> MAJOR ISSUES
>
> 1. Bidirectionality and folding
>
> The SRFI conflates "order" and "bidirectionality." While it does
> recognize that some bidirectional collections are unordered --
> collection-fold-right works on sequences -- it incorrectly assumes that
> all ordered collections are bidirectional. For example, a sorted list is
> ordered but not bidirectional.
>
> This difference is important when writing generic algorithms for
> collections. If you know whether a collections behaves poorly when
> "backing up," you can specialize a generic algorithm to account for that
> fact. There are similar benefits for specializing on a random-access
> collections.

Perhaps the real solution is to make it optional that an ordered
collection support a reverse fold in addition to a
bidirectional-collection attribute.

> Related to this, I find the enumerator names confusing. I realize that
> you wanted them to parallel *-get-left, *-get-right, and similar
> procedures. However, collection-fold-left implies to me that the
> enumeration proceeds *toward* the left, not *from* the left. Also, it's
> a very cumbersome name for what should be a common operation. Based on
> this and the idea of bidirectional or "reversible" containers, I
> recommend changing the names to:
>
>     collection-fold             in-order (or unordered) traversal
>     collection-reverse-fold     reverse-order traversal

The argument for a more concise function name is more persuasive to me
than any confusion that might arise from left/right distinctions.  I'm
receptive to the idea, and will change it if there is a second from
anyone else on the list.

> 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.  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.

> 2. Equivalence of dictionaries
>
> The SRFI states:
>
>     For sequences, the ordering of the contained values must also be
>     equivalent. For dictionaries, each key in the first dictionary must
>     be equal to a key in the second dictionary, and the value(s) mapped
>     to by that key in each dictionary must also be equivalent.
>
> This doesn't specify how you determine whether a value is equivalent.
> More precisely, the SRFI doesn't specify whether the equivalence
> function compares keys only or key-value pairs. The latter approach
> makes the above text well-defined, but it makes dictionary-get more
> difficult to implement correctly. The former approach (comparing keys
> only) works better for the collection methods, but leaves "values ...
> must be equivalent" undefined. Should they be compared with eqv? Should
> it use key-value pairs? Should it have a second equivalence operator?
> Should the equivalence operator function correctly both for keys and for
> key-value pairs?

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.

>     ... collections also may possess one of two (in this SRFI)
>     attributes which specify whether certain global functions are well
>     defined for the collection.
>
> This implies that an ordered collection cannot also be mutable. Should
> read "collections may possess either of two ...." If you introduce
> bidirectional-collection? and random-access-collection?, it should read
> "any of four ...."

Absolutely.

>
> Why is this a problem for alists but not for plain lists? I don't see
> how it's a problem at all -- alists are not mutable collections. In
> functional programming style, the "empty list" problem is not a problem
> at all. Now, storing metadata in the list head is a good idea, but this
> "need set-cdr!" explanation doesn't hold water.

Taylor, can you comment on this?

	Scott