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

Re: Bidirectionality and other comments

This page is part of the web mail archives of SRFI 44 from before July 7th, 2015. The new archives for SRFI 44 contain all messages, not just those from before July 7th, 2015.

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