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

Re: Left- and right-ness of folds



> oleg@xxxxxxxxx wrote:
>> I would like to remark that 'left' and 'right' in the traditional
>> fold-left and fold-right do *not* refer to the order in which the
>> elements of a collection are fetched: from the left or from the
>> right. Rather, these labels refer to associativity. Let us consider
>> an ordered collection, e.g., a list of three elements (e1 e2 e3).

scgmille@xxxxxxxxxxxxxxxxxx wrote:
> Am I correct in saying then that a right fold would be defined even
> for a directional datastructure such as a list?

Yes.

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

For example, a Scheme list is reversible but not bidirectional. You can
reverse it, but it has a clear forward bias. The infinite sequence
a[n] = n is bidirectonal but not reversible. The fibonacci sequence is
neither bidirectional nor reversible.

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.
-- 
Bradd W. Szonye
http://www.szonye.com/bradd