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

[Ray Dillinger <bear@x>]

On 05/25/2013 06:07 PM, John Cowan wrote:
> Ray Dillinger scripsit:
>
>> 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.
>
> Which, come to think of it, is a good argument for the
> hash-plus-equivalence magic.  The current set/bag API doesn't have any
> way to specify a hash function, because the fact that sets and bags use
> a hash table is or should be an implementation detail -- but if you pass
> an unknown equivalence function, the implementation won't work.

An ordering predicate could be used with a tree or skiplist 
implementation, yielding O(logN) rather than O(N) or O(1)
access time.  While O(1) hash tables are preferable, if an
implementation drops to O(logN) trees with a user-supplied
ordering/equivalance predicate, that would be acceptable, I
think.  I consider O(N) list comparisons to be unacceptable
for keyed searches.

I think user-supplied ordering functions are a relatively
easy requirement for most users to fulfil, but hash functions
that work as hash functions while mapping 'equal' things under
a custom predicate to equivalent buckets are surprisingly
subtle.  Requiring the user to supply one would make the
library unfriendly to use and perhaps impossible in some
cases.  IOW, providing a hash function, if there's a way
to do it at all, should be optional but hopefully rewarded
with (implementation-dependent?) better performance.  But
providing at least a compatible ordering function if using
a custom equivalence predicate is a reasonable requirement.

Ray




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