Left- and right-ness of folds

[s***@public.gmane.org]

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). Then
fold-left opl seed lst === (((seed `opl` e1) `opl` e2) `opl` e3)
fold-right opr seed lst === (e1 `opr` (e2 `opr` (e3 `opr` seed)))

<snip>

Ah. That is most enlightening as always. Bradd, I believe this means
you'll have to add

(define collection-fold collection-fold-left)

to your code. :)

Scott

[s***@public.gmane.org]

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

Am I correct in saying then that a right fold would be defined even for
a directional datastructure such as a list? This seems to be the case,
though it does imply that the right fold would naturally consume a
linear amount of storage in the worst case relative to the number of
values in a collection.

This would argue against a reversible attribute, at least for the
purposes of folding. It would still be valid for get-right, however.

Scott

[Bradd W. Szonye]

Post by s***@public.gmane.org

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

Am I correct in saying then that a right fold would be defined even
for a directional datastructure such as a list?

Yes.

Post by s***@public.gmane.org
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.

[s***@public.gmane.org]

Post by Bradd W. Szonye

Post by s***@public.gmane.org
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.

Post by Bradd W. Szonye
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

[Bradd W. Szonye]

Post by s***@public.gmane.org

Post by Bradd W. Szonye
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.

That's a big pitfall! A right-fold on an infinite sequence will diverge
before the folding function ever gets called. I think it's a bad idea to
provide an interface that is "broken by design" like that -- it cannot
possibly function correctly.

It's one thing to include dangerous procedures, stuff that will blow up
if you don't use it correctly. But it's another thing to include
procedures that cannot possibly work. I realize that Scheme has a very
"academic" following that worries more about concepts than practical
matters. However, this SRFI seems to take that to an extreme! The design
principles seem to include, "No matter how error-prone an interface is,
it's still the programmer's fault for misusing it," and "Incompatibility
with prior art is unimportant." While that might fly in some academic
contexts, it's *horrible* from an engineering point of view.

[s***@public.gmane.org]

Post by Bradd W. Szonye

Post by s***@public.gmane.org

Post by Bradd W. Szonye
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.

That's a big pitfall! A right-fold on an infinite sequence will diverge
before the folding function ever gets called. I think it's a bad idea to
provide an interface that is "broken by design" like that -- it cannot
possibly function correctly.

Its not really. collection-fold-right will raise an error if applied to
an infinite collection. Would it placate you if it was required to
raise an error with truely infinite collections? Real infinite
collections's fold-rights would then error immediately rather than after
running out of memory.

Scott

[Bradd W. Szonye]

Post by s***@public.gmane.org

Post by Bradd W. Szonye
That's a big pitfall! A right-fold on an infinite sequence will
diverge before the folding function ever gets called. I think it's a
bad idea to provide an interface that is "broken by design" like that
-- it cannot possibly function correctly.

Its not really. collection-fold-right will raise an error if applied
to an infinite collection. Would it placate you if it was required to
raise an error with truely infinite collections?

That's better, but I still have a problem with the fact that you're
requiring something that is not well-defined. And by "not well-defined,"
I don't mean that it's ambiguous or unclear -- I mean that there's no
way to define it meaningfully.

[s***@public.gmane.org]

Post by Bradd W. Szonye

Post by s***@public.gmane.org

Post by Bradd W. Szonye
That's a big pitfall! A right-fold on an infinite sequence will
diverge before the folding function ever gets called. I think it's a
bad idea to provide an interface that is "broken by design" like that
-- it cannot possibly function correctly.

Its not really. collection-fold-right will raise an error if applied
to an infinite collection. Would it placate you if it was required to
raise an error with truely infinite collections?

That's better, but I still have a problem with the fact that you're
requiring something that is not well-defined. And by "not well-defined,"
I don't mean that it's ambiguous or unclear -- I mean that there's no
way to define it meaningfully.

But its far less elegant to make specific exceptions.
After all, you're arguing over *what kind* of error occurs if someone
uses collection-fold-right is applied to an infinite collection.

Scott