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

Re: collection-fold-right for unordered collections

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

> 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