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


Attachment: pgpikN1qbxuwB.pgp
Description: PGP signature