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