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

Re: collection-fold-right for unordered collections



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.

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

> 
> And if an unordered collection *will* preserve the enumeration order 
> (which would be typical for many straightforward implementations) then 
> collection-fold-right should be defined to enumerate in the reverse of 
> that same unspecified (but invariant-while-not-modified) order.
> 
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.

	Scott

Attachment: pgpikN1qbxuwB.pgp
Description: PGP signature