On Wed, Jul 30, 2003 at 05:24:28PM -0500, xxxxxx@freenetproject.org wrote:
> [forwarded on behalf of Oleg]
>
> advanced module system, I can import a particular dictionary
> implementation (e.g., associative lists) with renaming
> 	make-alist => make-mydict
> 	alist-get  => mydict-get
> etc. In my own code I would use the names make-mydict, mydict-get,
> etc. exclusively. If at a later time I decide to use a different
> dictionary implementation, I would only need to change the module
> declaration statement.

The problem with this approach is that it doesn't let you use two
collections of different types by the same Scheme function.  For
example:

(define (myfunc a)
  (set-contains? a 3))

(myfunc (foo-set 1 2 3))
(myfunc (bar-set 4 5 6))

> The latter gave a few suggestions.
>
> > procedure: % value ... => %
>
> >      Constructs a % collection with the zero or more values provided
> > as its initial contents.
>
> Should we add that if the collection is a set, it is unspecified which
> element is kept in case of duplicates? Or should duplicates be
> outlawed? [Edison takes the former approach].

I prefer the former.  There could be many cases where the user is
generating the input to that constructor, and it would be a shame to
penalize them for having duplicates.

>
> > procedure: *-add bag value => *
> > procedure: *-add![!] bag value => *
>
> >      Adds a single value to a bag.
>
> > procedure: *-add-all dest-bag source-bag => *
> > procedure: *-add-all![!] dest-bag source-bag => *
>
> >      Adds all the values in the source bag to the destination bag.
>
> Edison says: insert [our add] keeps the new element in case of
> duplicates, but insertSeq [our add-all] keeps an unspecified element.

In the case of bags, its perfectly valid to keep all the values.  Did
you mean sets?

> <snip> occurence counts ... </snip>

Yeah, this is a Good Thing.  Especially for bags where duplicates may be
common and contains? is insufficient.

> required to return either 0 or 1). Edison also defines a procedure
>
> >   instanceName   :: c -> String
> >     -- the name of the module implementing c
>
> which can be useful, for example, for generating error messages. The
> procedure is useful regardless of a particular module or OO system.

I agree.  In our scheme:

(collection-name %) => "%"
such that for example (collection-name (make-list 3)) => "list"

>
> For ordered collections, Edison defines procedures to view, insert or
> delete the maximum and the minimum elements. I don't know how useful
> this may be (many advanced collections do allow efficient
> implementations of such operations -- especially for collections that
> are used for priority queues or dequeues).

This has come up in IRC discussions, coincidentally in discussion of
implementing queues.  It would be best mapped as
*-get-left, *-insert-left![!], *-remove-left![!], and likewise for
right, and would be defined on Bags, Sequences, and ordered collections.
...-right's would *in general* not be well defined on bags, but specific
collections (like a queue) would illuminate it.

>
> It goes without saying that many operations in Edison -- like union or
> intersection of two collections -- are perhaps too high-order or too
> laborous or too infrequent to warrant their specification in
> SRFI-44. It's better to stick to the bare minimum and provide
> extensions only for very frequent operations.
For general collections, yes.  Note though that we basically have this
for sets, union = add-all, difference = remove-all, and intersection =
(remove-all in1 (remove-all in1 in2)).

> > procedure: *-ref sequence integer => boolean
>
> >      Returns the value stored in the sequence at the integer index
> > provided. It is an error to reference an index outside the range of
> > the sequence.
>
> The return type can't be boolean. Right?

Typo.  Thanks.

> BTW, often a function *-ref-with-default is surprisingly useful. The
> function takes an extra argument -- the default value -- and returns
> literally (in the sense of eq?) that argument in case the lookup
> failed.
Yes, we have this on dictionary get.  We probably shoud have it on ref
and get for the other collection types.

>
> Edison's sequences,
> http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/*checkout*/hfl/hfl/edison/Seq/Sequence.hs
>
> are also interesting, in particular procedures lview, rview, inBounds,
> adjust and zippers. However, one may also leave them out for SRFIs to
> come.

Yes.  Its mostly the intent to specify the absolutely necessary elements
of collections here.  Like Scheme, one can define much from little.

> > (eq? <input collection> (update-procedure <input collection>)) will
> > always return a non-false value.
>
> Perhaps this statement is too conservative? R5RS requires that eq? (as
> well as eqv? and equal?) return a boolean value. Therefore, the only
> non-false return value of eq? is #t. It might be a good idea to say
> that explicitly.

Force of habit, sorry.

> > The collection fold procedure then invokes the folding function on a
> > value of the collection and the seeds, and receives from the folding
> > function a proceed value followed by a like number of seed return
> > values. If the termination value is non-false,
>
> Perhaps you meant "the proceed value" rather than a termination
> value. Otherwise, "termination value" is not mentioned anywhere else in
> the document.

Indeed.

> > In order to ensure a consistent ordering in the collection, the
> > ordering function must return the same result for like inputs over
> > time.
> In other words, an ordering function must be a pure function, a
> mapping of its arguments. One might add that an implementation of a
> collection may assume
>     (and (equal? x x1) (equal? y y1)) ==>
> 	(equal? (ordering-function x y) (ordering-function x1 y1))
>
> Should the same requirement be applied to a equivalence function as
> well?

Of course.  Thanks as always for your meticulous insight.

	Scott