[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Bidirectionality and other comments




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.