[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Fundamental design flaws

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.




    > 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?

instead of

	(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
error.

-t