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

[Dave Abrahams]

on Fri May 13 2016, Nate Cook <nate-AT-natecook.com> 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 give me a random collection of Ts, I may want to find the index
of the first element that satisfies some predicate.  Then I may want to
process the prefix of elements that don't satisfy that predicate, and
repeat.

In general, many algorithms that operate on a collection place no
requirements on the semantic relationship and/or ordering of the
elements, and such algorithms can still be useful on Sets.  Use your
imagination and you'll see more of them, e.g. find the index of the
maximum element in the set (so that you can remove it).

>>> 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:). 

? What does “type-specific” mean and why do you say so?

If we don't have a remove(at:) method for Set, that's a bug.  Whether we
need a RangeRemovableCollection that is refined by
RangeReplaceableCollection is an interesting question.

> 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.

It's true that it's harder to find algorithms that are *very likely* to
be useful on collections whose ordering is not controlled, but that
doesn't mean those collections shouldn't satisfy the Collection
protocol.  Even parallelization of trivial operations such as “find the
minimum element” requires the the fundamental properties of Collection.

-- 
-Dave