What to do with the rest of SE-0174?


(David Rönnqvist) #1

Hi.

I was looking to implement SE-0174 <https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md> (Change filter to return an associated type) but noticed that a different RangeReplaceableCollection.filter implementation had already been added in fd2ac31 to make String.filter return a String.

The RangeReplaceableCollection.filter implementation in SE-0174 eagerly enumerates self to filter its elements:

var result = Self()
for element in self {
    if try isIncluded(element) {
        result.append(element)
    }
}
return result

whereas the current implementation creates Self from a lazy filter:

return try Self(self.lazy.filter(isIncluded))

Which of these implementations is preferred for SE-0174?

The intended behavior of SE-0174 is already there with Data, Set, String, etc. returning Self when filtered. As far as I can tell the only remaining work is to add the associated type and specify the type alias in a few places to disambiguate which implementation is used to satisfy the Sequence protocol, essentially making this a non functional change. Or am I missing something?

Regards,
David


(Dave Abrahams) #2

Hi.

I was looking to implement SE-0174
<https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md>
(Change filter to return an associated type) but noticed that a different
RangeReplaceableCollection.filter implementation had already been added in fd2ac31 to make
String.filter return a String.

The RangeReplaceableCollection.filter implementation in SE-0174 eagerly enumerates self to filter
its elements:

var result = Self()
for element in self {
    if try isIncluded(element) {
        result.append(element)
    }
}
return result

whereas the current implementation creates Self from a lazy filter:

return try Self(self.lazy.filter(isIncluded))

Which of these implementations is preferred for SE-0174?

The advantage of the second implementation is that when the source is a
Collection, the filtered result will be counted before the first
allocation so the new array can be allocated once before elements are
copied into it. The first implementation does more allocations and more
element copies, but it only traverses the source collection once, and
passes each element through the filter once. I can easily come up with
an example that performs *much* better under each of the two
implementations. Picking a winner depends on making judgement calls
about the cost of traversing a representative source collection and
calling a representative filter function, and balancing that against the
cost of array reallocations. This is not an analysis we've ever taken
the time to do, so there's no simple answer, unfortunately.

···

on Thu Jul 20 2017, Gmail <swift-dev-AT-swift.org> wrote:

The intended behavior of SE-0174 is already there with Data, Set,
String, etc. returning Self when filtered. As far as I can tell the
only remaining work is to add the associated type and specify the type
alias in a few places to disambiguate which implementation is used to
satisfy the Sequence protocol, essentially making this a non
functional change. Or am I missing something?

Regards,
David
_______________________________________________
swift-dev mailing list
swift-dev@swift.org
https://lists.swift.org/mailman/listinfo/swift-dev

--
-Dave