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