[swift-evolution] [Review] SE-0074: Implementation of Binary Search functions

[Dave Abrahams]

on Fri May 13 2016, Nate Cook <swift-evolution at swift.org> wrote:

>>> On May 13, 2016, at 9:36 AM, Dave Abrahams via swift-evolution <swift-evolution at swift.org> wrote:
>>> 
>>> on Mon May 09 2016, Nate Cook <natecook-AT-gmail.com> wrote:
>>> 
>>> Yet another alternative would be to drop Set and Dictionary down a
>>> level to a FiniteSequence protocol in between Sequence and
>>> Collection. Basically none of the index-based collection APIs
>>> (i.e. everything except `count` and `isEmpty`) make sense on sets and
>>> dictionaries.
>> 
>> Strongly disagreed.  Any read-only operation that makes sense on a
>> bidirectional collection makes sense on these data structures.
>
> I don't see how the methods that impose meaning on the order of a set
> are useful. What does mySet.prefix(upTo: i) mean when I have no
> control or dependable way of knowing which elements lie between
> startIndex and i? mySet.first is useful, but it's meaning is more like
> NSSet's anyObject.

If you want to process the elements of your set in parallel, you want to
break it down into equally-sized regions and distribute the work across
cores.  That's indexing and slicing.

>>> index(where:) was marginally useful with dictionaries, but now that
>>> Sequence is getting first(where:), née find(...), even that isn't
>>> necessary.
>> 
>>   s.remove(at: s.index(where: { $0 < 1 }))
>
> Since Set's remove(at:) method is type-specific, it would need to be
> rewritten as remove(where:). 

That would mean “remove all elements satisfying this predicate,” to me.

> This example is kind of my point, though - it removes the first
> element less than 1, but only one such element, and there's no telling
> which. That's not an operation I've ever needed to perform on a set.
>
> To clarify, I don't think the current system is hurting Set and
> Dictionary in any way. It's simply providing them with methods that
> aren't very useful for that particular data structure.

I agree that because of Set's nature, some Collection algorithms are
less-applicable than they would otherwise be.  Does that mean Set isn't
fundamentally a Collection?  No it does not.  A Collection is a
multipass sequence with a representation of position.  Set definitely
has those properties.

-- 
-Dave