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

[Alexey Radul <axch@x>]

On Sun, May 26, 2013 at 8:28 AM, John Cowan <cowan@x> wrote:
> So far I haven't heard about any *actual* cases of people requiring
> specialized equivalence predicates, though it's easy to make up
> hypotheticals.

Really?

How about record types?  equal? is not specified to compare their
contents recursively, so if I want those semantics I have to force
them with a custom equivalence predicate, and therefore a custom hash
function.  I have written a hash function because of this, so this
meets your criterion of non-hypotheticalness.

How about sets?  Suppose I want to use sets as keys in a hash table,
with set=? as the equivalence predicate?

Sets are a good example of why custom equivalence predicates are
essential: Scheme has no primitive data structures that do not store
their elements in some observable order, so declaring the order
irrelevant has to be done at the set level.  This essentially [*]
necessitates a set equivalence predicate which is non-trivial in the
sense that it is coarser than any natural equivalence predicate that
might be applied to the sets' underlying representations.

~Alexey

[*] One could object that it is possible to implement sets that store
their elements in a normalized order internally, and compare that
internal store with equal?.  Yes, it is possible to implement sets
this way; it is not possible to do so with amortized O(1) insertion,
because the internal order amounts to a sort; and anyway, Scheme does
not define a universal < procedure.  (What if you wanted a set of
ports to which some logging output needs to be copied?)  Incidentally,
the `project' proposal applied to sets has the same weakness of
essentially mandating a universal sort order, and costing O(n log n)
to compute.

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