<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=""><br class=""><div><blockquote type="cite" class=""><div class="">Am 19.02.2016 um 15:47 schrieb Andrew Bennett <<a href="mailto:cacoyi@gmail.com" class="">cacoyi@gmail.com</a>>:</div><br class="Apple-interchange-newline"><div class="">Hi Maximillian,<div class=""><br class="">On Friday, 19 February 2016, Maximilian Hünenberger <<a class="">m.huenenberger@me.com</a>> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" class=""><div class=""></div><div class="">Discussions on different index handling should belong to another thread if there isn't one already.</div></div></blockquote><div class=""><font size="2" class=""><span style="background-color:rgba(255,255,255,0)" class="">I mentioned indices only to provide context :) the linked document (Swift master) discusses an approach that fixes many of the issues with a custom wrapper approaches mentioned here.</span></font></div><div class=""><font size="2" class=""><span style="background-color:rgba(255,255,255,0)" class=""><br class=""></span></font></div></div></div></blockquote><div><br class=""></div><div>Is there already a thread on swift-evolution which discusses these index changes?</div><br class=""><blockquote type="cite" class=""><div class=""><div class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" class=""><div class=""><br class=""></div><div class="">Your proposed Set change covers at least the custom Hashable behavior.</div><div class="">What about Equatable? I think it could be expressed as behaviors.</div></div></blockquote><div class=""> </div>Custom Equatable could also be implemented as a similar closure (Element,Element)->Bool. I left it off, but I probably shouldn't have. My main goal was to minimise changes to the existing interfaces and provide similar performance.</div><div class=""><br class=""></div><div class="">I wonder if there's any cases someone would want anything other than Equatable or pointer comparison.</div><div class=""><br class=""></div><div class="">As for your behaviour suggestion: I may be misinterpreting how it works. I like the idea, but it seems like a much larger change than is necessary. It may change all the type signatures in normal usage, and obsfucate the Element type.</div><div class=""><br class=""></div><div class=""><font size="2" class=""><span style="background-color:rgba(255,255,255,0)" class="">Ideally the sets type would only show the element type, not implementation details like a custom hash algorithm.</span></font><br class=""></div><div class=""><br class=""></div></div></blockquote><div><br class=""></div><div>I thought about "Property behaviors" (separate thread) where such an addition <b class="">could</b> be difficult to implement.</div><div><br class=""></div><div>But if they are implemented we can then generalize them to a transparent wrapper type.</div><div><br class=""></div><div>Pseudo implementation:</div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>var behavior pointerHashable<Value: AnyObject>: Value {}</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>extension pointerHashable: Hashable {</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>var hashValue: Int { return ObjectIdentifier(self).hashValue }</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>}</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>func ==<T>(lhs: <font size="2" class=""><span class="" style="background-color: rgba(255, 255, 255, 0);"><span style="font-size: 12px;" class="">pointerHashable</span><T></span></font>, rhs: <font size="2" class=""><span class="" style="background-color: rgba(255, 255, 255, 0);"><span style="font-size: 12px;" class="">pointerHashable</span><T></span></font>) -> Bool {</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>return <font size="2" class=""><span class="" style="background-color: rgba(255, 255, 255, 0);">ObjectIdentifier(lhs) == ObjectIdentifier(rhs)</span></font></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>}</div><div><br class=""></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>//usage</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>var set: Set<pointerHashable<MyClass>> = [MyClass(), MyClass()]</div><div><span class="Apple-tab-span" style="white-space:pre"> </span>let firstElement = set.first! // returns MyClass</div><br class=""><blockquote type="cite" class=""><div class=""><div class="">If you're happy to change the Set's type signature for each hash/equality algorithm then a wrapper like Nicola suggests is probably good enough.</div><div class=""><br class=""></div><div class="">Even easier if you're happy to manually wrap and unwrap:</div><div class=""><br class=""></div></div></blockquote><div><br class=""></div><div>a behavior would implicitly wrap/unwrap</div><br class=""><blockquote type="cite" class=""><div class=""><div class="">class HashableReference<T: AnyObject>: Hashable {</div><div class=""> let object: T</div><div class=""> var hashValue: Int {</div><div class=""> return ObjectIdentifier(object).hashValue</div><div class=""> }</div><div class="">}</div><div class="">func ==<T: AnyObject>(lhs: <font size="2" class=""><span style="background-color:rgba(255,255,255,0)" class="">HashableReference<T></span></font>, rhs: <font size="2" class=""><span style="background-color:rgba(255,255,255,0)" class="">HashableReference<T></span></font>) -> Bool {</div><div class=""> return <font size="2" class=""><span style="background-color:rgba(255,255,255,0)" class="">ObjectIdentifier(lhs) == ObjectIdentifier(rhs)</span></font></div><div class="">}</div><div class=""><br class=""></div><div class="">Apologies for any errors, this was done from my iPhone from memory.</div></div></blockquote><div><br class=""></div><div>However if the behavior cannot be implemented easily this approach would be the best.</div><div><br class=""></div><div>- Maximilian</div><br class=""><blockquote type="cite" class=""><div class=""><div class=""><br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" class=""><div class=""><br class=""></div><div class="">- Maximilian</div><div class=""><br class="">Am 19.02.2016 um 11:58 schrieb Andrew Bennett via swift-evolution <<a class="">swift-evolution@swift.org</a>>:<br class=""><br class=""></div><blockquote type="cite" class=""><div class=""><div dir="ltr" class=""><div class="">Good points Dimitri,</div><div class=""><br class=""></div><div class="">I only wrote this quickly, so please look for other issues too, I don't expect it to be complete by any means.</div><div class=""><br class=""></div><div class="">I think a way to get an element's hashValue should probably be exposed, similar to `<font face="monospace, monospace" class="">collection.next(index)</font>` that I mentioned earlier. I think this is useful, but I don't think it's actually necessary. Equatable is sufficient to provide Set functionality, Hashable is just for performance</div><div class=""><br class=""></div><div class="">I'm not aware of any algorithms that can't be built on top of the existing set methods that would require the same hash value the element used for binning.<br class=""></div><div class=""><br class=""></div><div class="">I was initially thinking that you could compare the Hashable to determine equality, but I agree that there is a potential for the closure to convert to a narrower type.</div><div class=""><br class=""></div><div class="">A much stronger solution would change the interface slightly to require Element to be `<font face="monospace, monospace" class="">Equatable`</font>, and provide `<font face="monospace, monospace" class="">Element -> Int</font>` as the closure. It's slightly less flexibly, but I do agree that a narrowing makes Equatability of s1 == s2 ambiguous.<br class=""></div><div class=""><br class=""></div><div class=""><b class="">In summary</b>:</div><div class=""><br class=""></div><div class=""><div style="font-size:13px" class=""><div class=""><span style="font-family:monospace,monospace;background-color:rgb(244,204,204)" class="">- struct Set<Element: Hashable> {</span><br class=""></div><div class=""><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class="">- struct Set<Element: Equatable> {</span></div><div class=""><span style="font-family:monospace,monospace" class=""> ...</span><br class=""></div><font face="monospace, monospace" style="background-color:rgb(244,204,204)" class=""><div class=""><div style="font-family:arial,sans-serif;background-color:rgb(255,255,255)" class=""><div class=""><font face="monospace, monospace" style="background-color:rgb(244,204,204)" class="">- public init() { ... }</font></div><div class=""><span style="background-color:rgb(217,234,211)" class=""><font face="monospace, monospace" class="">+ public init(</font></span><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class="">hashValue</span><span style="background-color:rgb(217,234,211)" class=""><font face="monospace, monospace" class="">ForElement: Element -> Int) {</font></span></div><div class=""><span style="background-color:rgb(217,234,211)" class=""><font face="monospace, monospace" class=""> ... </font></span></div><div class=""><span style="background-color:rgb(217,234,211)" class=""><font face="monospace, monospace" class=""> }</font></span></div></div><font face="monospace, monospace" style="background-color:rgb(255,255,255)" class=""></font></div>- public init(minimumCapacity: Int) { ... }</font></div><div style="font-size:13px" class=""><span style="background-color:rgb(217,234,211)" class=""><font face="monospace, monospace" class="">+ public init<H: Hashable>(minimumCapacity: Int, </font></span><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class="">hashValue</span><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class="">ForElement: Element -> Int</span><span style="background-color:rgb(217,234,211)" class=""><font face="monospace, monospace" class="">) {</font></span></div><div style="font-size:13px" class=""><span style="background-color:rgb(217,234,211)" class=""><font face="monospace, monospace" class=""> ... </font></span></div><div style="font-size:13px" class=""><span style="background-color:rgb(217,234,211)" class=""><font face="monospace, monospace" class=""> }</font></span><font face="monospace, monospace" style="background-color:rgb(244,204,204)" class=""><br class=""></font></div><div style="font-size:13px" class=""><div class=""><span style="font-family:monospace,monospace" class=""> ... (same for other public initialisers)</span></div></div><div style="font-size:13px" class=""><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class="">+ public func hashValueForElement(element: Element) -> Int { ... </span><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class="">}</span></div><div style="font-size:13px" class=""><span style="font-family:monospace,monospace" class=""> }</span><br class=""></div><div style="font-size:13px" class=""><div class=""><br class=""></div><div class=""><div class=""><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class="">+ extension Set where Element: Hashable {</span><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class=""><br class=""></span></div><div class=""><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class="">+ public init() { ... }</span><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class=""><br class=""></span></div><div class=""><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class="">+ public init(minimumCapacity: Int) { ... }</span><br class=""></div><div class=""><span style="font-family:monospace,monospace;background-color:rgb(217,234,211)" class="">+ }</span></div></div></div></div><div class=""><br class=""></div><div class="">-</div><div class="">Andrew Bennett</div><div class=""><br class=""></div></div><div class="gmail_extra"><br class=""><div class="gmail_quote">On Fri, Feb 19, 2016 at 7:14 PM, Dmitri Gribenko <span dir="ltr" class=""><<a class="">gribozavr@gmail.com</a>></span> wrote:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Fri, Feb 19, 2016 at 2:06 AM, Andrew Bennett via swift-evolution<br class="">
<<a class="">swift-evolution@swift.org</a>> wrote:<br class="">
> Wrapper Solution?<br class="">
><br class="">
> I've had a go at a wrapper solution before and it seems to either need a<br class="">
> unique type per sort, or a block stored per element (unstable).<br class="">
><br class="">
> Similar overheads were discussed when an index needs to store a reference to<br class="">
> the parent. There's some work to fix it that makes indices moveable, so<br class="">
> instead of going index.successor() you use collection.next(index).<br class="">
><br class="">
> <a href="https://github.com/apple/swift/blob/master/test/Prototypes/CollectionsMoveIndices.swift" rel="noreferrer" target="_blank" class="">https://github.com/apple/swift/blob/master/test/Prototypes/CollectionsMoveIndices.swift</a><br class="">
><br class="">
> Potential solution:<br class="">
><br class="">
> The collection interfaces could change like this:<br class="">
><br class="">
> - struct Set<Element: Hashable> {<br class="">
> - struct Set<Element> {<br class="">
> ...<br class="">
> - public init() { ... }<br class="">
> + public init<H: Hashable>(elementHasher: Element -> H) {<br class="">
> ...<br class="">
> }<br class="">
<br class="">
</span>How do you compare such sets? That is, what does s1 == s2 mean, if<br class="">
the two sets are constructed with a hashing closure? We can't even<br class="">
compare closures to find that they are the same.<br class="">
<br class="">
Also, how would this affect algorithms on sets? When handling a set,<br class="">
you essentially wouldn't know the rules according to which it<br class="">
operates, unless we expose this mapping function.<br class="">
<div class=""><div class=""><br class="">
Dmitri<br class="">
<br class="">
--<br class="">
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if<br class="">
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <<a class="">gribozavr@gmail.com</a>>*/<br class="">
</div></div></blockquote></div><br class=""></div>
</div></blockquote><blockquote type="cite" class=""><div class=""><span class="">_______________________________________________</span><br class=""><span class="">swift-evolution mailing list</span><br class=""><span class=""><a class="">swift-evolution@swift.org</a></span><br class=""><span class=""><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" target="_blank" class="">https://lists.swift.org/mailman/listinfo/swift-evolution</a></span><br class=""></div></blockquote></div></blockquote></div>
</div></blockquote></div><br class=""></body></html>