This page is part of the web mail archives of SRFI 44 from before July 7th, 2015. The new archives for SRFI 44 contain all messages, not just those from before July 7th, 2015.
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