Dictionaries

["Bradd W. Szonye" <bradd+srfi@xxxxxxxxxx>]

> scgmille@xxxxxxxxxxxxxxxxxx wrote:
>> Dictionaries have conceptual issues precisely because they are a
>> mapping where all other collection styles in the SRFI are just
>> collections.

I have an idea that may help you resolve the dictionary problem.

Dictionaries need not be a special case. Their "unusual" properties
actually exist for other collections, just in a less obvious way. All
collections have a way to find elements:

    bags and sets search on the entire element
    sequences use an external, numeric index
    dictionaries use the mapping's range (keys) as an index

Therefore, the SRFI can generalize the index concept. The "mapped value"
concept likewise exists for all collections:

    bags, sets, and sequences map indices to the entire element
    dictionaries map the range values to the domain values

The result: There are three ways of viewing every collection element.

1. The entire ELEMENT.
2. An INDEX used to locate the element, which may be external (like a
   sequence's numeric indices) or internal (like a dictionary's keys).
3. An indexed VALUE, which may be the entire element or only part of it.

By collection type:

                Element type     Index         Value
    bag, set    anything         the element   the element
    sequence    anything         an integer    the element
    dictionary  key-value pair   the key       the mapped value

With this concept, much of the need for separate interfaces goes away.
For example, the need for fold-keys disappears; fold can enumerate all
ELEMENTS instead of all VALUES. Likewise, ref and get are both ways of
finding INDEXES, and contains? is a VALUE search.

This idea also simplifies the definition of equality: Two collections c1
and c2 are equal if and only if for every index I and element E in both
collections:

    (= (count-with elt= c1 E) (count-with elt= c2 E))
    (elt= (get-element c1 I) (get-element c2 I))

In other words, both collections have the same partition of elements
over elt=, the same set of indices, and the same mapping of indices to
elements.

The next step is to examine the current interfaces and decide which
values are really elements, which are indices, etc. You may find that
you don't need as many procedures.
-- 
Bradd W. Szonye
http://www.szonye.com/bradd