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.
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.
Therefore, I strongly recommend that you split off the
bidirectional-collection? attribute from ordered-collection?. This would
address the issues brought up by Jim White earlier in the discussion. I
also strongly recommend a random-access-collection? attribute to
distinguish lists from vectors. They're both sequences, but they have
very different algorithmic properties. I consider this a major issue
because algorithmic efficiency is one of the main reasons for having a
sophisticated container system.
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
I prefer these names because (1) the more common case, forward
traversal, has a simpler name, and (2) it removes the ambiguity between
"from the left" and "to the left."
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.
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?
MINOR ISSUES
In "Collection Attributes":
... 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 ...."
In "Scheme Association Lists":
It is difficult to fully map the collections API onto alists, as
they are Scheme lists. Difficulty would be encountered in adding to
an empty alist, as mutation of the variable holding the Scheme
empty-list would be required. For this reason alists produced by
this SRFI have a placeholder value at the front of the list so that
its contents can always be side-effected and to store metadata about
the alist.
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.
--
Bradd W. Szonye
http://www.szonye.com/bradd