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

Re: Left- and right-ness of folds

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.



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.

	Scott

Attachment: pgpYjZ443x2tu.pgp
Description: PGP signature