Re: collection-fold-right for unordered collections

[scgmille@xxxxxxxxxxxxxxxxxx]

On Mon, Jul 28, 2003 at 11:08:17AM -0700, Jim White wrote:
> scgmille@xxxxxxxxxxxxxxxxxx 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.

Attachment: pgpi6D1sew5H9.pgp
Description: PGP signature