Re: Bidirectionality and other comments Taylor Campbell 16 Oct 2003 19:10 UTC
On Thursday, Oct 16, 2003, at 13:07 US/Eastern, email@example.com 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.