Taylor Campbell wrote:
> And we were just about to finalize it...damn...

Sorry about that! I would've commented earlier, but (1) I've been away
from Scheme for a few months, and (2) this is a subject very dear to me,
so of course I want the best possible implementation!

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

It was a bad example and an oversimplification.

Better example: The "fibonacci" sequence, which is ordered but infinite,
so there is no right end to work from.

Also, I too was conflating two different concepts. "Bidirectional" means
that it's (roughly) just as efficient to fold in either direction.
Vectors are bidirectional, but Scheme lists are not. It's a hint for
generic algorithms. I recommend implementing it, but you could leave it
for a later GP SRFI if it's too much hassle.

I was mixing that up with "reversible," which *is* necessary. It's how
you know that you can't use a reverse-fold on an unordered bag or a
fibonacci sequence.

Regarding my suggestion to change the "fold" names:

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

OK, you've got me there; LEFT and RIGHT are traditional. However, I
can't say that I like the tradition, especially in this case. Could you
at least change FOLD-LEFT to FOLD?

1. There's precedent for it in SRFI-1.
2. "LEFT" doesn't make sense for non-directional collections.
3. It's less to type.

I don't care for FOLD-RIGHT either, but I could live with it, and it
*is* traditional.

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

Likewise. Consider me convinced.

Regarding the note about "empty" alists:

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

Agreed! That's a much better way to explain and justify it.

Suggestion for the reference implementation: If possible, avoid using a
metadata cell if the equivalence function is eqv? (the default). That
way, (alist eqv?) will be a normal Scheme alist. Not really necessary,
but it should be more "intuitive" for a common case.
--
Bradd W. Szonye
http://www.szonye.com/bradd