[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Fundamental design flaws
> From: scgmille@xxxxxxxxxxxxxxxxxx
> > > For something like a hash table, sure -- at creation time I really
> > > need to establish what notion of equality (and hence, hashing) is in
> > > play -- but for bags?
> > OK. This point I concede. I don't like the handling of equality
> > functions either. I'd probably prefer optional comparison arguments
> > to many of the procedures, but I'd have to talk with Scott and
> > Matthias about this before becoming certain that that would be better.
> I can see both sides here, but let me state the other side that
> you may not be considering. There may be bags whose internal
> representation is dependent on the equivalence function in the
> same way that its important for hash table based dictionaries.
> A bucket based bag, for example, may need the equivalence
> function to classify the values it stores, allowing it to have
> logarithmic performance for contains? because it has pre-sorted
> its values in a certain way. This is the rationale for
> pre-specification of the equivalence function. If all bags were
> completely unorganized collections of values and all had
> guaranteed O(N) lookup times, then it would be just fine to pass
> the equivalence function at call time.
Perhaps in all cases, the optional equivalence predicate to a
constructor is mostly just a hint.
If I make a hash table using EQV? but then modify it with:
(dictionary-set! d k v) ; set using equal?
(dictionary-setv! d k v) ; set using eqv?
then perhaps the results are simply undefined. The non-generic
interface to (normal) association lists works that way, for example.
I've certainly used hash-table libraries that work that way.
Haven't had too many problems with it and, since the result is
"undefined", a hash table would certainly be permitted to signal an