On Mon, Jul 28, 2003 at 11:08:17AM -0700, Jim White wrote:
> xxxxxx@freenetproject.org wrote:
> >On Mon, Jul 28, 2003 at 08:08:57AM -0700, Jim White wrote:
> >
> >>I'm thinking that unordered collections are not quite fully specified.
> >>
> >>A key question is whether collection-fold-left will return the elements
> >>of the collection in the same (unspecified) order or not when used
> >>multiple times.
> >
> >I've actually just added some language in the document about that.
>
> I'll check it out.
Its not up yet, just in my local copy where I'm aggregating changes.

>
> >>It seems to me that either unordered collections should either always
> >>enumerate in the same order as long as they are not modified, or there
> >>needs to be some way to distinguish unordered collections that make no
> >>representation about repeating the enumeration order.
> >
> >Devils advocate may argue that garbage collection should be allowed to
> >compact a collection in a way that may affect its order.
>
> I agree.  But that's what I'm saying.  If you've got some exotic
> implementation for unordered collections that does reordering, then
> great (although one may wonder what it might be doing during
> enumeration).  If however you're dealing with something ordinary, then
> you should be able to use it effeciently.
>
> I'm particularly thinking of functions that divide and recurse on the
> left and right ends looking to meet in the middle.

If you want to reliably go backwards on any datastructure, it should be
ordered, such as for a sequence.  The contract for unordered, unindexed
datastructures (namely Bags and Sets in this SRFI) does not provision
for ordering, so the programmer shouldn't rely on any particular walk.

> >
> >That I disagree with completely.  Just because the order is unchanging
> >should not necessarily mean that a right fold is possible.  Take for
> >example a collection of the natural numbers.  Its unchanging from left
> >fold to left fold, but a right fold is completely impossible.  In less
> >dramatic cases, such as for long Scheme lists, a right fold may be
> >possible, but very inefficient.
>
> Well, that is not a counter example.  That actually is an example of an
> ordered collection that (may) not have a right fold.  Of course it
> probably does have a right fold (which always returns infinity and
> nevers terminates).

The list example still holds.  One should expect that an enumeration
takes a constant space/time to step from one value to another.  This
would not be the case for the right fold of a list, as you'd need to
build up O(n) context information to get to the end and then walk
backwards.

>
> Is there any indication for unbounded collections?  A quick look didn't
> show any.  How are they to be handled?

The API does not preclude them.  They are handled straightforwardly from
the functions that exist.  collection-fold-[right|decreasing] would
be undefined on them, as you note.