[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
I've actually just added some language in the document about that.
I'll check it out.
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.
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.
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
Is there any indication for unbounded collections? A quick look didn't
show any. How are they to be handled?
"I love deadlines. I love the whooshing sound they make as they fly by."
-- Douglas Adams