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

Re: collection-fold-right for unordered collections



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.

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 nevers terminates).

Is there any indication for unbounded collections? A quick look didn't show any. How are they to be handled?

Jim
--
"I love deadlines. I love the whooshing sound they make as they fly by." -- Douglas Adams