[swift-evolution] Proposal: Add function SequenceType.find()

[Kevin Ballard]

On Wed, Dec 30, 2015, at 07:33 AM, Donnacha Oisín Kidney via swift-evolution wrote:
> +1 on this.
>
> I see a lot of code like this:
>
> sequence.filter(predicate).first
>
> Which is of course is inefficient. However, the go-to optimisation:
>
> sequence.lazy.filter(predicate).first
>
> Is not necessarily better, and has some strange behaviour:
>
> let array = [1, 2, 3, 4, 5, 6] func noisyPredicate(n: Int) -> Bool {
> print(n, terminator: " ") return n > 2 }
>
> array.lazy.filter(noisyPredicate).first // 1 2 3 1 2 3
>
> AnySequence(array).lazy.filter(noisyPredicate).first // 1 2 3 4 5 6
>
> If it’s called on a collection, the collection is only evaluated up
> until the element being looked for, but it’s done twice. If it’s
> called on a sequence, the *whole* sequence is evaluated, regardless of
> where the element is found.

Actually, you're calling it on a collection in both cases. SequenceType
doesn't have a `first` property (honestly, I think it should). Saying
`lazy.filter(noisyPredicate)` is actually resolving to the version of
filter() from SequenceType, the one that returns an Array, because the
one from LazySequenceType that returns a LazyFilterSequence doesn't have
a `first` property.

As for it calling it twice on a collection, this is because it's
implemented as `isEmpty ? nil : self[startIndex]`, which is honestly
pretty silly.

FWIW, there's other sequence methods that actually evaluate lazy
collections twice, because they detect that the receiver is a
collection and run a preprocessing pass first. For example, the
version of joinWithSeparator() that returns a String does this (to
size all of the elements so it can preallocate a buffer), which causes
duplicate evaluation of lazy filter/map collections. I filed this a
while ago as SR-68[1].

> I think that find is maybe not the best name, though. It’s not
> immediately clear that it doesn’t return an index.

indexOf() used to be called find(), but it was renamed because find()
didn't make it obvious that it returned an index. I know I personally
got confused all the time about what find() returned.

Also, this is a sequence method. Sequences don't have indexes.

-Kevin Ballard

> I’d prefer to call it first, as in:
>
> extensionSequenceType { /// Returns the first element where
> `predicate` returns `true`, or `nil` /// if such value is not found.
> public func first(@noescape thatSatisfies: (Self.Generator.Element)
> throws -> Bool) rethrows -> Self.Generator.Element? { for elt in self
> { if try thatSatisfies(elt) { return elt      }    } returnnil  } }
>
> [1, 2, 3, 4, 5].first(thatSatisfies: (Int) throws -> Bool)
>
> [1, 2, 3, 4, 5].first { $0 > 3 }
>
>> On 30 Dec 2015, at 10:13, James Campbell via swift-evolution <swift-
>> evolution at swift.org> wrote:
>>
>> We should add the full collection of ruby methods
>> http://matthewcarriere.com/06/23/using-select-reject-collect-inject-and-detect/
>>
>>
>>
>> Sent from my iPhone
>>
>> On 30 Dec 2015, at 02:40, Keith Smiley via swift-evolution <swift-
>> evolution at swift.org> wrote:
>>> +1. We've added an extension for this and find it very useful. On
>>> Tue, Dec 29, 2015 at 18:38 Kevin Ballard via swift-evolution <swift-
>>> evolution at swift.org> wrote:
>>>> __
>>>> I'm proposing a new extension method on SequenceType called find().
>>>> It's similar to CollectionType.indexOf() except it returns the
>>>> element:
>>>>
>>>> extensionSequenceType{ /// Returns the first element where
>>>> `predicate` returns `true`, or `nil` /// if such value is not
>>>> found. publicfuncfind(@noescapepredicate: (Self.Generator.Element)throws->Bool)rethrows-
>>>> >Self.Generator.Element? { foreltinself{ iftrypredicate(elt) {
>>>> returnelt            }        } returnnil    } }
>>>>
>>>> -Kevin Ballard
>>>>
>>>>
>>>> _______________________________________________
>>>> swift-evolution mailing list swift-evolution at swift.org
>>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>>
>>> _______________________________________________
>>> swift-evolution mailing list swift-evolution at swift.org
>>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>  _______________________________________________
>> swift-evolution mailing list swift-evolution at swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>
> _________________________________________________
> swift-evolution mailing list swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution



Links:

  1. https://bugs.swift.org/browse/SR-68
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20151230/39494b39/attachment.html>