Re: Bidirectionality and other comments Taylor Campbell 16 Oct 2003 19:10 UTC

On Thursday, Oct 16, 2003, at 13:07 US/Eastern, wrote:

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

And we were just about to finalize it...damn...

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

Perhaps I'm misunderstanding what 'bidirectional' means here, but
FOLD-RIGHT is definitely well-defined on lists; or this is just a bad

>> 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 the sake of consistency, I'm _vehemently_ against this:
_everywhere_ that I've seen some form of folding or reducing, there is
either a FOLD or a FOLD-LEFT and a FOLD-RIGHT; _never_ have I seen a
situation in which FOLD-RIGHT means 'go _to_ the right.'

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

I agree that COLLECTION-FOLD-RIGHT (-REVERSE-FOLD?) should be, rather
than equivalent to COLLECTION-FOLD-LEFT, undefined on bidirectional

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

Yes.  I don't like the wording of that.  I'd prefer that you just left
it that NULL? might not return #T for what (alist) returns and that
ALIST-EMPTY? shall be used instead, because I find the metadata useful
and the ability to modify the CDR of an empty alist only marginally
convenient in linear update procedures.