<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class="">Would it make sense to abstract the hash functions into a protocol?</div><div class=""><br class=""></div><div class="">The limit of the Hashable protocol is that it forces a type to commit to a specific ‘canonical’ hash implementation, while there might be more efficient implementations depending on the application.</div><div class=""><br class=""></div><div class="">To truly support composition patterns, it would seem appropriate for the standard library to support decoupling the hashing functionality from the type of the container element.</div><div class=""><br class=""></div><div class="">E.g.</div><div class=""><br class=""></div><div class=""><span style="color: rgb(187, 44, 162); font-family: Menlo; font-size: 11px;" class="">protocol</span><span style="font-family: Menlo; font-size: 11px;" class=""> Hash {</span></div><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">typealias</span> Element</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">static</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> equal(lhs: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Element</span>, <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">_</span> rhs: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Element</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">static</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> hashValue(x: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Element</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">// now we can define a generic box</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">struct</span> HashableBox<T, H: Hash <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">where</span> H.Element == T> : <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Hashable</span> {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span> value: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">T</span></div><p style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></p><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">var</span> hashValue: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span> {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">return</span> <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">H</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">hashValue</span>(<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">value</span>)</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> ==<T, H>(lhs: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">HashableBox</span><<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">T</span>, <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">H</span>>, rhs: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">HashableBox</span><<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">T</span>, <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">H</span>>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span> {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">return</span> <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">H</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">equal</span>(lhs.<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">value</span>, rhs.<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">value</span>)</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">// now we can define a wrapper around Set, using an explicit Hash</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">struct</span> CustomHashSet<Element, H: Hash <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">where</span> H.Element == Element> {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> // this is an implementation detail; if CustomHashSet was part of the standard library,</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> // the .gyb could produce a more efficient implementation</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(79, 129, 135);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">private</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">var</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> set: </span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Set</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><</span>HashableBox<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><</span>Element<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span>H<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">>></span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(79, 129, 135);" class=""> </div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">init</span>() {}</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">init</span><S: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">SequenceType</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">where</span> <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">S</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Generator</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span> == <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Element</span>>(<span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">_</span> sequence: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">S</span>) {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">set</span> = <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Set</span>(sequence.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">lazy</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">map</span> { <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">HashableBox</span><<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Element</span>, <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">H</span>>(value: $0) })</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span>// etc.</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">// Example usage</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><div style="margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">struct</span> NaiveCollectionHash<C: CollectionType <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">where</span> C.Generator.Element: Hashable>: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Hash</span> {</div><div style="margin: 0px; line-height: normal;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">typealias</span> Element = <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">C</span></div><p style="margin: 0px; line-height: normal; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></p><div style="margin: 0px; line-height: normal;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">static</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> equal(lhs: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Element</span>, <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">_</span> rhs: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Element</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span> {</div><div style="margin: 0px; line-height: normal;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">guard</span> lhs.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">count</span> <span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">==</span> rhs.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">count</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">else</span> { <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">return</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">false</span> }</div><div style="margin: 0px; line-height: normal;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">return</span> <span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">zip</span>(lhs, rhs).<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">lazy</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">reduce</span>(<span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">true</span>) { $0 && ($1.<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">0</span> <span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">==</span> $1.<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">1</span>) }</div><div style="margin: 0px; line-height: normal;" class=""> }</div><div style="margin: 0px; line-height: normal;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">static</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> hashValue(x: <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">Element</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span> {</div><div style="margin: 0px; line-height: normal; color: rgb(0, 132, 0);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">return</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> x.</span><span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">reduce</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">(</span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">0</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">) { $0 ^ $1.</span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">hashValue</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> } </span>// a bad hash just as an example</div><div style="margin: 0px; line-height: normal;" class=""> }</div><div style="margin: 0px; line-height: normal;" class="">}</div><div style="margin: 0px; line-height: normal; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span> arrays = [[<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">1</span>],[<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">2</span>]]</div><div style="margin: 0px; line-height: normal; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; color: rgb(0, 132, 0);" class="">// This doesn't work because Array is not Hashable (yet)</div><div style="margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">var</span> s1 = <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Set</span>(<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">arrays</span>) <span style="font-variant-ligatures: no-common-ligatures; color: #008400" class="">// Error</span></div><div style="margin: 0px; line-height: normal; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; color: rgb(0, 132, 0);" class="">// This works but we need to explicitly specify all the types</div><div style="margin: 0px; line-height: normal; color: rgb(79, 129, 135);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">var</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> s2 = </span>CustomHashSet<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><</span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><</span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">>, </span>NaiveCollectionHash<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><</span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><</span><span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">>>>(</span>arrays<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">) </span><span style="font-variant-ligatures: no-common-ligatures; color: #008400" class="">// ok</span></div><div style="margin: 0px; line-height: normal; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; line-height: normal; color: rgb(0, 132, 0);" class="">// Generic typealiases would help reducing the boilerplate, e.g.</div><div style="margin: 0px; line-height: normal; color: rgb(0, 132, 0);" class="">// it would be useful if we could do</div><div style="margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">typealias</span> NaiveHashSet<T> = CustomHashSet<T, NaiveCollectionHash<T>> <span style="font-variant-ligatures: no-common-ligatures; color: #008400" class="">// Error</span></div><div style="margin: 0px; line-height: normal; color: rgb(0, 132, 0);" class="">// then Swift's type inference should be able to automatically handle this:</div><div style="margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">var</span> s3 = NaiveHashSet(<span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">arrays</span>) <span style="font-variant-ligatures: no-common-ligatures; color: #008400" class="">// Error</span></div><div class=""><span style="font-variant-ligatures: no-common-ligatures; color: #008400" class=""><br class=""></span></div></div></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class="">Nicola</div><div class=""><br class=""></div>
> Cc:swift-evolution<<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>><br class="">> Subject:[swift-evolution] Custom equality/hash for Sets<br class="">> Date:19 February 2016 at 05:04:51 GMT+1<br class="">> <br class="">> <br class="">> <br class="">> > On Feb 18, 2016, at 16:09 , Dave Abrahams via swift-evolution<<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>(<a href="mailto:swift-evolution@swift.org" class="">mailto:swift-evolution@swift.org</a>)>wrote:<br class="">> > <br class="">> > on Thu Feb 18 2016, Jacob Bandes-Storch<<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>(<a href="mailto:swift-evolution@swift.org" class="">mailto:swift-evolution@swift.org</a>)>wrote:<br class="">> > <br class="">> > > Would it make sense for the standard library Set to provide variants (or<br class="">> > > parallel versions of the same data structure) that take custom hashValue/==<br class="">> > > implementations at init time (functions taking in Elements), rather than<br class="">> > > relying on Hashable/Comparable protocols?<br class="">> > > <br class="">> > > Use case: I want a set of objects that are compared for equality using ===<br class="">> > > rather than ==. This doesn't seem possible today, using Set, without<br class="">> > > creating some sort of wrapper object.<br class="">> > > <br class="">> > > This particular case would be analogous to using NSHashTable with<br class="">> > > NSPointerFunctionsObjectPointerPersonality. (Maybe all I'm asking for is a<br class="">> > > Swiftier API for NSHashTable — including ArrayLiteralConvertible, using<br class="">> > > generics instead of UnsafePointer<Void>, etc.)<br class="">> > > <br class="">> > > Similarly, C++'s unordered_map<br class="">> > > <<a href="http://en.cppreference.com/w/cpp/container/unordered_map" class="">http://en.cppreference.com/w/cpp/container/unordered_map</a>>and friends have<br class="">> > > template parameters specifying the hash function and equality comparator,<br class="">> > > which use std::hash and == by default.<br class="">> > <br class="">> > It might make sense.How bad is the wrapper solution for user code?<br class="">> > struct CustomHashableFoo: Hashable {<br class="">> > var value: Foo<br class="">> > func hash() ->Int {<br class="">> > // custom hash function here<br class="">> > }<br class="">> > }<br class="">> > func ==(a: CustomHashableWrapped, b: CustomHashableWrapped) {<br class="">> > // custom == here<br class="">> > }<br class="">> Really not that bad, although you do have to get 'value' in and out of the box. It's also not reusable code—you have to rewrite the box for every type.<br class="">> <br class="">> I'd say you usuallydon'twant to allow custom hash/== closures because (a) then you have to store them somewhere, and (b) the compiler won't usually be able to inline them away. You also end up with a Set<Foo>that doesn't behave like a normal Set<Foo>—maybe you can insert equal-but-not-identical elements—which is bad if anyone's relying on normal Set-like guarantees.<br class="">> <br class="">> -1 from me until we can put functions in generics, if ever.<br class="">> <br class="">> Jordan_______________________________________________<br class="">> swift-evolution mailing list<br class="">> <a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">> <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" class="">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br class="">> <br class="">> <br class="">><span class="Apple-converted-space"> </span>
</body></html>