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 Tue, Apr 29, 2003 at 10:27:25AM +0200, sebastian.egner@xxxxxxxxxxx wrote: > Scott, > > There are a number of remarks > > 1. Two frequent operations > > I am missing the two frequent methods *-clear! and *-copy. Yes of course. > > 2. Passing options to the constructors > > A major design challenge is passing options to the constructors (make-%). > > Your design only specifies an optional argument equivalence-function > for datatypes that require a notion of equality on their keys > (Dictionaries). > However, for efficient data structures it is very important to know as > much as possible about the keys (e.g. a total order, a hash function, > a range of possible keys or even their statistical distribution). This > holds in particular for Sets (= trivial applications of dictionaries). > > In the current SRFI there is no mechanism to pass these options to the > constructors, the problem is left to subclasses. Is it your intention to > add > a mechanism for this? Perhaps it needs to be made more clear in the document itself, but the intention is that specific collection SRFIs are allowed to make more specific, or even moderately conflicting definitions collection specific functions. Nevertheless, it may be desirable to add an [additional-options ...] to the specification of make-%. > > 3. Polymorphic interface > > Another major design challenge is a mechanism to choose the > representation of the collections without modifying the interface. > > The SRFI specifies a monomorphic interface, only. In other words, > each operation of each data type has a different name, so for > example alist-remove! and avl-tree-remove! both delete an > element from a dictionary but you have to know whether it is > implemented as an alist or an avl-tree. As the number of possible > data structures grows a problem might evolve here. Actually, there are polymorphic calls as well. *-remove!, for example, mandates the existence of dict-remove! and alist-remove!. I hope that specific Scheme systems solve this problem more cleanly than the current portable implementation does. The rationale for distinct functions for a specific datastructure as well as the categories it lives in is to allow code to be written which is datastructure agnostic, code to be written which is datastructure sensitive (using a more specific function would cause an error with the wrong specific type), and for implementors to both improve the efficiency of the specific calls, and to be able to dispatch to the specific calls from the generic ones. > > Iterators on the other hand are specified polymorphic; in other > words, *-iterator creates an object that can handle the messages > iterator-at-start? etc. independent of the underlying representation. > (Sorry for the OO-speak, but this language is widely known.) > If efficiency was the main design goal, wouldn't it be much more > efficient to specify alist-iterator-at-start? etc.? If iterators were monomorphic, it would prevent one from writing collection agnostic code, which I perceive as a real benefit to the collections APIs of most languages that have them. A fine example in this SRFI is the *-add-all! function, which is specified to take any bag as input to any other bag (including sequences). This is trivially implemented using an iterator and the *-add! function, but only if iterators are polymorphic. > Finally, you may want to check out two libraries for data structures > (if you haven't already) that I find myself very interesting. In any > case, they are worth a reference: > * LEDA: http://www.algorithmic-solutions.com/enledadoku.htm > * STL: http://www.cs.utexas.edu/users/lavender/courses/stl/stl.pdf I have some familiarity with the STL, but I'll give LEDA a look. Scott
Attachment:
pgpBuZN9gx6oB.pgp
Description: PGP signature