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

Re: Left- and right-ness of folds

On Sat, Oct 25, 2003 at 10:10:29AM -0700, Bradd W. Szonye wrote:
> > This would argue against a reversible attribute, at least for the
> > purposes of folding.  It would still be valid for get-right, however.
> It sounds like you're still using "reversible" to mean "reversals are
> efficient." Generic programming usually uses the word "bidirectional"
> for that. I use "reversible" to indicate whether you can get the right
> end at all.

No, I understand what you mean, but a reversible attribute would 
only apply to the from the get-right, insert-right, and remove-right 
operators. Right folds would be required to operate on all collections.  
What wouldn't be required is that a right fold necessarily be the 
reverse of a left fold, since an arbitrary collection may not even have
a consistent ordering from one fold to the next.

> Even with the "right-associative" definition, a right fold is still not
> possible for an infinite sequence, because the fold will not halt. It
> will diverge before you can even use the initial value. You first need
> to select a finite subset so that you can apply the initial value in the
> fold.

It would still be defined for said collections however.  The fact that 
it may not halt is a pitfall for the programmer that attempts it.


Attachment: pgpYjZ443x2tu.pgp
Description: PGP signature