Bradd wrote:
>> Agreed. I keep waffling between two different concepts for the
>> dictionary: is it a collection of mappings, or is it a bag with an
>> index?

xxxxxx@freenetproject.org wrote:
> A dictionary is a datastructure which stores values that can be
> accessed using a key.  Anything more specific than that assumes a
> specific implementation type.

No, it's not about the implementation. I'm talking about concepts and
interfaces here. There are two common kinds of dictionary ADTs:

1. A collection of mappings. This is how you define a dictionary in set
   theory. In this kind of dictionary, the keys are conceptually a part
   of a collection element (but they need not be represented that way
   internally). Scheme alists and C++ maps use this concept.

2. A collection with an index. This is more like a sequence, or a bag
   with an index. The keys are conceptually external to the elements
   (but they need not be represented that way internally). PLT Scheme
   hash tables use this concept.

With the "collection of mappings" concept, users generally expect
enumerations and lookups to return a mapping (a pair or something like
it), because that's the element type. With the "external index" concept,
users generally expect enumerations and lookups to return a mapped
value.

The "collection of mappings" dictionaries usually *also* provide a
method to get a domain/mapped value, given a range/key value. That's
because they're modeling the set-theory concept of a mapping, which is
both a set (collection of mappings) *and* a relationship (mappings keys
to values).

> It may be implemented as a bag with an
> index, but its important to keep the types distinct, otherwise you
> risk shoehorning many dictionary types into an awkward interface in
> order to look like a bag with an index.  You can't necessarily assume
> a collection of mappings either (although to some extent you must to
> implement the folding enumerator).

>>     mutable vs immutable (seem like opposites, but they're not)

> This is really a problem with haphazardly calling purely mutable
> functions just mutable at times.  This has been fixed.

Good, thanks.

>>     *-all vs *-any (names similar and counterintuitive)

> The names are quite intuitive if you read them right:
>
> (*-remove-all collection bag) => remove all of bag from collection
> (*-remove-any collection bag) => remove any occurence of bag from
> collection

Sure, if you read them right. My point is that it's easy to read them
backwards: "remove all occurrences." However, I haven't been able to
think of anything less ambiguous, so I'll withdraw this complaint.

>> 2. Error-prone naming conventions.

> Maybe.  I'm not convinced that the same argument can't be made from the
> other side of the fence, i.e. that the names of procedures from other
> libraries are themselves ill conceived.

You may be right!
--
Bradd W. Szonye
http://www.szonye.com/bradd