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
Attachment:
pgpCdkTbF6r1n.pgp
Description: PGP signature