xxxxxx@freenetproject.org wrote:
> Lets examine your proposed API for dictionaries, and contrast it with
> SRFI-44.

Bear wrote:
>> (*-insert! dict datum key),

> *-put dictionary key value

Not necessarily. PUT adds a key if it does not exist or changes it if it
does exist. That's not well-defined unless the dictionary has unique
keys. INSERT may be equivalent to ADD, which can add a duplicate key or
raises an exception if the dictionary doesn't permit them.

By the way, did I mention that PUT isn't well-defined for arbitrary
mappings? It only works for "function" (N to 1) mappings.

> > (*-fetch-deleting! dict key)

> [A]
> (define (*-fetch-deleting! dict key)
>   (let ([rv (*-get dict key)])
>     (*-remove! dict key)
>     rv))
>
> Additionally, fetch-deleting! does not map to many dictionaries, for
> example disk file database, *without* doing the above.

The point is that it's an important for practical reasons. Also, your
implementation may not be the best way to do it for some dictionaries.
Without the interface, there's no way for a generic algorithm to deal
with that.

Now, there is a trade-off between perfect polymorphism and keeping the
"concept space" of the interface reasonable. But without a real
implementation of SRFI-44, there's no way to show that its trade-offs
are appropriate. Indeed, I've seen you repeatedly reject these sorts of
practical concerns.

>> (*-get-n dict num)
>> (*-get-n-deleting! dict num)

> Trivially defined with enumeration.

But is it practical? Another disadvantage of the "no practical
implementation" approach.

>> (get-iterator dict)   ;; returns an iterator function that
>>                       ;; takes a key arg and returns some "next" key,
>>                       ;; or takes '() and returns some (arbitrarily
>>                       ;; chosen for unordered dictionaries) "first" key.
>>
>> (*-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 ...)

Q: Can you implement it at all with the SRFI-44 interface?

A: Yes, you can, but it's tricky, and the implementation includes
something just like a cursor. Essentially, collection-fold-left and
nfold must be coroutines, and the Scheme implementation of coroutines
effectively creates a one-use cursor.

Enumerators may also create problems for algorithms which require
backtracking (bidirectionality). It may be possible, with something like
the "limited use cursors" you get from coroutines, but I haven't figured
it out yet.

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

>> (*-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.

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.

> So, you see, your API is almost *exactly* like the current SRFI apart
> from minor naming variations.

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.

That's more than just "minor naming variations." Sorry if this sounds
rude, but you're far too quick to dismiss ideas as being "minor" just
because they're about naming, efficiency, or practical concerns.

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.

> Where it differs, there has been strong refutation for that approach.

Please don't overstate Oleg's claims unless you can explain them. He
makes some good points, enough to justify the enumerators, but I'm not
entirely convinced -- enumerators themselves seem to require at least a
limited kind of iterator, if you go beyond the basic one-collection
fold.

> I must ask, did you *read* the SRFI carefully?

I have, several times, and it's missing some important details, like
design goals, conflicts with prior art, a full implementation, several
of the performance- and usability-oriented interfaces that Bear's
dictionary provides. Most importantly, it doesn't explain this bizarre
attitude that performance and usability are "minor" issues in a proposal
for a standard interface for collections. I strongly suggest that you
step back and reconsider your design goals, both to (1) make sure that
you've met them, and to (2) make sure that they actually make sense
given the nature of the SRFI.
--
Bradd W. Szonye
http://www.szonye.com/bradd