Re: [Scheme-reports] Seeking review of sets and hash tables proposals

[Ray Dillinger <bear@x>]

On 05/25/2013 01:54 PM, Per Bothner wrote:
> On 05/25/2013 01:50 PM, Vassil Nikolov wrote:
>>
>> Per Bothner<per@x>  wrote:
>>
>>> ...
>>> a bag of T is just
>>> a minor optimization of a map (hash-table) from T to integers.
>>
>>     Except when equality only depends on
>>     parts of the elements.
>
> I don't understand this comment.

One may use a custom equality predicate in other sorts of
structures -- but if you use a custom equality predicate in a
map representation of something, you lose the nice property
that 'equal' entities hash to 'equal' buckets, unless you
also define a hash function such that your custom notion of
equality will map things to the same hash bucket when they
are 'equal' in its terms.

Perhaps you're asking about items whose names have equal length,
or some similarly odd request. (actually not that odd -- permutations 
having the same length are frequently 'equal' (because made of the same 
substrings) in DNA computing.)

I don't think that's the issue Vassil was talking about, but
implementation as a map requires the ability to use a custom
hash function if using a custom equality predicate.

				Bear




_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports