On Sat, Oct 25, 2003 at 09:55:44PM -0700, Bradd W. Szonye wrote:
> xxxxxx@freenetproject.org wrote:
> >> (*-nextkey dict) ;; same as function returned from get-iterator
> >> (*-nextkey dict key) ;; same as returned from the get-iterator func above
> >> (*-lastkey dict)     ;; same as returned from the get-reversed-iterator func
> >> (get-reversed-iterator dict)
>
> > See Olegs post on the hazards of iterators.
>
> Oleg makes a good point, but you should quit taking it as gospel. Can
> you clearly explain the advantages and disadvantages yourself? Do you
> understand the underlying theory? And, most importantly, can you show
> how to implement a multiple-collection fold without cursors?
>
>     (nfold f seed c1 c2 c3 ...)

Perhaps you should read treatise linked in the post which shows how a
cursor is trivially created from an enumeration?  I don't disagree that
some operations would be more convenient with cursors.  After all, the
initial draft of the SRFI specified iterators as the fundamental
operator.  I wouldn't have agreed with a change to enumeration unless it
preserved the functionality of iterators.

> > <snip>Efficiency procs
> > Best left to a separate SRFI.
>
> Yes, perhaps. But you should be more careful about your design to make
> sure that it isn't incompatible with them. You seem to have a mental
> filter that shuts out anything performance-related, even if it has
> design implications.

Can you point out how it currently is not?  That would be a concrete
criticism worth addressing.

>
> >> (*-fetchfirst dict number) ;; returns number entries
> > [B] Trivially implemented with collection-fold-left
>
> Trivially and VERY SLOWLY. However, you could implement it more
> efficiently with a "*-get-any" interface that returns all matches. Even
> more efficiently with a "*-get-any" enumerator that uses a filtering
> predicate that can stop the enumeration. You can do this for a tree ADT
> in O(log N + K) time, where N is the dictionary size and K is the number
> of elements returned.

I frankly don't see this at all.  Its obvious that a get-any with a
filter could be more efficient than enumeration, but fetchfirst would
only be more efficient and faster than enumeration over an ordered
dictionary (as originally stated!) only if enumeration was poorly
implemented for the dictionary.

>
> But SRFI-44 doesn't include those interfaces, so you're stuck with the
> O(N) enumeration algorithm. Sure, you could leave this for later, but
> what's the point in having an inefficient dictionary interface at all?
> There's no need for it.
>
The point is to describe the set of functionality need to use
dictionaries at all.  Again this SRFI does not attempt to be the last
word on APIs for any of the collection types.  Take sets for example,
where many operations are omitted.

For arbitrary dictionaries, one cannot guarantee that the many
operations you'd have added can be efficiently or even possibly
implemented.  Being too specific would in fact limit the range
dictionaries that could be used in an agnostic way, efficiently or
outright.  When one defines a tree based dictionary as a subsequent SRFI
or wherever, its obvious that operations will be added, as the tree
structure facilitates them.

>
> No, it's much richer than the current SRFI, with procedures designed
> around the way people actually use the collection. In some cases, it
> solves problems that are poorly-defined or inefficient using the SRFI-44
> interface.

I agree, and I do not claim that SRFI-44 will have a monopoly on those
interfaces.

>
> Which is ridiculous, because efficiency is the whole point of having
> collections, and usability (including naming) is the whole point of
> having a standard interface. I don't know what your design goals were,
> but I'd be curious to hear them.

The design goals are stated pretty clearly at the beginning of the SRFI.
To provide a structure for agnostic use of collections and a framework
in which to define them, providing for the necessary set of operations
on them, and for interaction between them. It is not a document to
specify all possible operations on all possible datastructures.

	Scott