On Fri, Oct 24, 2003 at 10:24:09AM +0900, Alex Shinn wrote:
>
> 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).

The dictionaries you mention would be ordered, and thus are covered
quite nicely by the ordering function.  Hash tables will necessarily
require a hash function, which is likely to be specific to one or more
types.  Its fairly obvious that you'd need to specify a bit more when
defining a hashtable, but the extensions are very specific to the hash
table datastructure, so its outside the scope of this particular SRFI.

	Scott