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