Re: Bidirectionality and other comments

[Taylor Campbell <campbell@xxxxxxxxxxxx>]

On Thursday, Oct 16, 2003, at 13:07 US/Eastern, 
scgmille@xxxxxxxxxxxxxxxxxx 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...

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

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

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

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