At Thu, 23 Oct 2003 09:38:55 -0700, Bradd W. Szonye wrote:
>
> > xxxxxx@freenetproject.org 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.

Another special property property of dictionaries that I don't see
mentioned in the SRFI is that people generally expect them to provide a
fast lookup (at least faster than O(n) or else alists would be all
around better).  This is of course an implementation detail, which can
be solved in several ways, so you would think this detail should be left
out of the SRFI.  However, all solutions for fast dictionaries require
more information than just the equality predicate.  Weight balanced
trees are nice because they keep the dictionary sorted, and give
O(log(n)) lookup.  But they require a key<? predicate (and actually that
suffices, since you can derive = from <).  Hash tables are the most
common dictionary implementation, but they require a hashing function.
If you assume a generic hash function then you cannot implement
dictionaries that, for example, use string-ci=? as an equality predicate
(imagine implementing a Scheme environment).

Without opening access to implementation details you would need to
restrict the equality predicate to a predefined set such as eq?, eqv?
and equal?

--
Alex