[pitch] Change filter to return an associated type


(Ben Cohen) #1

Hi swift evolution,

The following is a proposal that came off the back of the discussions accepting the recent Dictionary proposal.

It is small but has source-breaking implications so would be good to get in for the 4.0 release.

Online copy here: https://github.com/airspeedswift/swift-evolution/blob/804d24e8950de98dd6af146b6367043e2f5072a8/proposals/NNNN-filter-range-replaceable.md

Change filter to return an associated type

Proposal: SE-NNNN <file:///Users/ben/Documents/swift-evolution/proposals/NNNN-filter-range-replaceable.md>
Authors: Ben Cohen <https://github.com/airspeedswift>
Review Manager: TBD
Status: Awaiting review
Introduction

This proposal changes the filter operation on Sequence to return an associated type, and adds a default implementation to RangeReplaceableCollection to return the same type as the filtered collection.

Motivation

The recently accepted SE-165 <https://github.com/apple/swift-evolution/blob/master/proposals/0165-dic %20t.md> introduced a version of filter on Dictionary that returned a Dictionary. This had both performance and useability benefits: in most cases, a Dictionary is what the user wanted from the filter, and creating one directly from the filter operation is much more efficient than first creating an array then creating a Dictionary from it.

However, this does result in some inconsistencies. Users may be surprised that this one specific collection returns Self, while other collections that would benefit from the same change still return [Element]. And some collections, such as String, might also benefit from usability and performance win similar to Dictionary. Additionally, these wins will be lost in generic code – if you pass a Dictionary into an algorithm that takes a Sequence, then when you filter it, you will still get an Array.

Proposed solution

The existing protocol requirement on filter will be changed to return an associated type, Filtered. The extension providing a default implementation will remain as-is, resulting in an inferred value for Filtered of [Element]. Dictionary will automatically infer a filtered type of Dictionary as a result of this change.

A default implementation on RangeReplaceableCollection will be provided, using init() and append(_:), so all range-replaceable collections will have a Filtered of Self. Per SE-163 <https://github.com/apple/swift-evolution/blob/master/proposals/0163-string-revision-1.md>, this will include String.

Note, many sequences (for example, strides or ranges), cannot represent a filtered self as Self and will continue to return an array. If this is a performance problem, lazy remains a good solution.

Detailed design

Add a Filtered associated type to Sequence, and change the requirement to return it:

protocol Sequence {
  associatedtype Filtered
  /// Returns an filtered sequence containing, in order, the elements of the
  /// sequence that satisfy the given predicate.
  ///
  /// In this example, `filter` is used to include only names shorter than
  /// five characters.
  ///
  /// let cast = ["Vivien", "Marlon", "Kim", "Karl"]
  /// let shortNames = cast.filter { $0.characters.count < 5 }
  /// print(shortNames)
  /// // Prints "["Kim", "Karl"]"
  ///
  /// - Parameter isIncluded: A closure that takes an element of the
  /// sequence as its argument and returns a Boolean value indicating
  /// whether the element should be included in the returned sequence.
  /// - Returns: An array of the elements that `includeElement` allowed.
  func filter(
    _ isIncluded: (Iterator.Element) throws -> Bool
  ) rethrows -> Filtered
}
Add a default implementation of filter to RangeReplaceableCollection returning Self:

extension RangeReplaceableCollection {
    func filter(_ isIncluded: (Iterator.Element) throws -> Bool) rethrows -> Self {
        var result = Self()
        for element in self {
            if try isIncluded(element) {
                result.append(element)
            }
        }
        return result
    }
}
Specific concrete collections may choose to implement a faster version, but this is an implementation detail.

Source compatibility

This change is subtly source breaking. In most cases users will not notice. They may be be relying on an array being returned (albeit often in order to then transform it back into the original type), but this version will still be available (via the extension on Sequence) and will be called if forced through type context. The only code that will break is if this operation spans multple lines:

// filtered used to be [Character], now String
let filtered = "abcd".filter { $0 == "a" }
useArray(filtered) // won't compile
Because of this, the new implementation of RangeReplaceableCollection.filter will only be available in Swift 4.

Effect on ABI stability

This change will affect the ABI of Sequence and needs to be made before declaring ABI stability.

Effect on API resilience

N/A

Alternatives considered

Status-quo. There are benefits to the consistency of always returning [Element].

It could be worthwhile to make a similar change to map, but this is beyond the capabilities of the current generics system because map does not preserve the element type (more specifically, you cannot express a type that is Self except with a different Element in order to provide the default implementation on RangeReplaceableCollection).


(Xiaodi Wu) #2

Is it the intention that `associatedtype Filtered : Sequence` once
recursive protocol constraints are supported? Can it be `associatedtype
Filtered : Collection`?

···

On Sun, Apr 23, 2017 at 2:37 PM, Ben Cohen via swift-evolution < swift-evolution@swift.org> wrote:

Hi swift evolution,

The following is a proposal that came off the back of the discussions
accepting the recent Dictionary proposal.

It is small but has source-breaking implications so would be good to get
in for the 4.0 release.

Online copy here: https://github.com/airspeedswift/swift-evolution/blob/
804d24e8950de98dd6af146b6367043e2f5072a8/proposals/NNNN-
filter-range-replaceable.md

Change filter to return an associated type

   - Proposal: SE-NNNN
   - Authors: Ben Cohen <https://github.com/airspeedswift>
   - Review Manager: TBD
   - Status: *Awaiting review*

Introduction

This proposal changes the filter operation on Sequence to return an
associated type, and adds a default implementation to
RangeReplaceableCollection to return the same type as the filtered
collection.
Motivation

The recently accepted SE-165
<https://github.com/apple/swift-evolution/blob/master/proposals/0165-dic %20t.md> introduced
a version of filter on Dictionary that returned a Dictionary. This had
both performance and useability benefits: in most cases, a Dictionary is
what the user wanted from the filter, and creating one directly from the
filter operation is much more efficient than first creating an array then
creating a Dictionary from it.

However, this does result in some inconsistencies. Users may be surprised
that this one specific collection returns Self, while other collections
that would benefit from the same change still return [Element]. And some
collections, such as String, might also benefit from usability and
performance win similar to Dictionary. Additionally, these wins will be
lost in generic code – if you pass a Dictionary into an algorithm that
takes a Sequence, then when you filter it, you will still get an Array.
Proposed solution

The existing protocol requirement on filter will be changed to return an
associated type, Filtered. The extension providing a default
implementation will remain as-is, resulting in an inferred value for
Filtered of [Element]. Dictionary will automatically infer a filtered
type of Dictionary as a result of this change.

A default implementation on RangeReplaceableCollection will be provided,
using init() and append(_:), so all range-replaceable collections will
have a Filtered of Self. Per SE-163
<https://github.com/apple/swift-evolution/blob/master/proposals/0163-string-revision-1.md>,
this will include String.

Note, many sequences (for example, strides or ranges), cannot represent a
filtered self as Self and will continue to return an array. If this is a
performance problem, lazy remains a good solution.
Detailed design

Add a Filtered associated type to Sequence, and change the requirement to
return it:

protocol Sequence {
  associatedtype Filtered
  /// Returns an filtered sequence containing, in order, the elements of the
  /// sequence that satisfy the given predicate.
  ///
  /// In this example, `filter` is used to include only names shorter than
  /// five characters.
  ///
  /// let cast = ["Vivien", "Marlon", "Kim", "Karl"]
  /// let shortNames = cast.filter { $0.characters.count < 5 }
  /// print(shortNames)
  /// // Prints "["Kim", "Karl"]"
  ///
  /// - Parameter isIncluded: A closure that takes an element of the
  /// sequence as its argument and returns a Boolean value indicating
  /// whether the element should be included in the returned sequence.
  /// - Returns: An array of the elements that `includeElement` allowed.
  func filter(
    _ isIncluded: (Iterator.Element) throws -> Bool
  ) rethrows -> Filtered
}

Add a default implementation of filter to RangeReplaceableCollection
returning Self:

extension RangeReplaceableCollection {
    func filter(_ isIncluded: (Iterator.Element) throws -> Bool) rethrows -> Self {
        var result = Self()
        for element in self {
            if try isIncluded(element) {
                result.append(element)
            }
        }
        return result
    }
}

Specific concrete collections may choose to implement a faster version,
but this is an implementation detail.
Source compatibility

This change is subtly source breaking. In most cases users will not
notice. They may be be relying on an array being returned (albeit often in
order to then transform it back into the original type), but this version
will still be available (via the extension on Sequence) and will be
called if forced through type context. The only code that will break is if
this operation spans multple lines:

// filtered used to be [Character], now Stringlet filtered = "abcd".filter { $0 == "a" }
useArray(filtered) // won't compile

Because of this, the new implementation of RangeReplaceableCollection.
filter will only be available in Swift 4.
Effect on ABI stability

This change will affect the ABI of Sequence and needs to be made before
declaring ABI stability.
Effect on API resilience

N/A
Alternatives considered

Status-quo. There are benefits to the consistency of always returning
[Element].
It could be worthwhile to make a similar change to map, but this is
beyond the capabilities of the current generics system because map does
not preserve the element type (more specifically, you cannot express a type
that is Self except with a different Element in order to provide the
default implementation on RangeReplaceableCollection).

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Ben Cohen) #3

Is it the intention that `associatedtype Filtered : Sequence` once recursive protocol constraints are supported?

Yup. Will add clarification.

Can it be `associatedtype Filtered : Collection`?

Sequence.lazy.filter returns a Sequence.

···

On Apr 23, 2017, at 1:05 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sun, Apr 23, 2017 at 2:37 PM, Ben Cohen via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi swift evolution,

The following is a proposal that came off the back of the discussions accepting the recent Dictionary proposal.

It is small but has source-breaking implications so would be good to get in for the 4.0 release.

Online copy here: https://github.com/airspeedswift/swift-evolution/blob/804d24e8950de98dd6af146b6367043e2f5072a8/proposals/NNNN-filter-range-replaceable.md

Change filter to return an associated type

Proposal: SE-NNNN <>
Authors: Ben Cohen <https://github.com/airspeedswift>
Review Manager: TBD
Status: Awaiting review
Introduction

This proposal changes the filter operation on Sequence to return an associated type, and adds a default implementation to RangeReplaceableCollection to return the same type as the filtered collection.

Motivation

The recently accepted SE-165 <https://github.com/apple/swift-evolution/blob/master/proposals/0165-dic %20t.md> introduced a version of filter on Dictionary that returned a Dictionary. This had both performance and useability benefits: in most cases, a Dictionary is what the user wanted from the filter, and creating one directly from the filter operation is much more efficient than first creating an array then creating a Dictionary from it.

However, this does result in some inconsistencies. Users may be surprised that this one specific collection returns Self, while other collections that would benefit from the same change still return [Element]. And some collections, such as String, might also benefit from usability and performance win similar to Dictionary. Additionally, these wins will be lost in generic code – if you pass a Dictionary into an algorithm that takes a Sequence, then when you filter it, you will still get an Array.

Proposed solution

The existing protocol requirement on filter will be changed to return an associated type, Filtered. The extension providing a default implementation will remain as-is, resulting in an inferred value for Filtered of [Element]. Dictionary will automatically infer a filtered type of Dictionary as a result of this change.

A default implementation on RangeReplaceableCollection will be provided, using init() and append(_:), so all range-replaceable collections will have a Filtered of Self. Per SE-163 <https://github.com/apple/swift-evolution/blob/master/proposals/0163-string-revision-1.md>, this will include String.

Note, many sequences (for example, strides or ranges), cannot represent a filtered self as Self and will continue to return an array. If this is a performance problem, lazy remains a good solution.

Detailed design

Add a Filtered associated type to Sequence, and change the requirement to return it:

protocol Sequence {
  associatedtype Filtered
  /// Returns an filtered sequence containing, in order, the elements of the
  /// sequence that satisfy the given predicate.
  ///
  /// In this example, `filter` is used to include only names shorter than
  /// five characters.
  ///
  /// let cast = ["Vivien", "Marlon", "Kim", "Karl"]
  /// let shortNames = cast.filter { $0.characters.count < 5 }
  /// print(shortNames)
  /// // Prints "["Kim", "Karl"]"
  ///
  /// - Parameter isIncluded: A closure that takes an element of the
  /// sequence as its argument and returns a Boolean value indicating
  /// whether the element should be included in the returned sequence.
  /// - Returns: An array of the elements that `includeElement` allowed.
  func filter(
    _ isIncluded: (Iterator.Element) throws -> Bool
  ) rethrows -> Filtered
}
Add a default implementation of filter to RangeReplaceableCollection returning Self:

extension RangeReplaceableCollection {
    func filter(_ isIncluded: (Iterator.Element) throws -> Bool) rethrows -> Self {
        var result = Self()
        for element in self {
            if try isIncluded(element) {
                result.append(element)
            }
        }
        return result
    }
}
Specific concrete collections may choose to implement a faster version, but this is an implementation detail.

Source compatibility

This change is subtly source breaking. In most cases users will not notice. They may be be relying on an array being returned (albeit often in order to then transform it back into the original type), but this version will still be available (via the extension on Sequence) and will be called if forced through type context. The only code that will break is if this operation spans multple lines:

// filtered used to be [Character], now String
let filtered = "abcd".filter { $0 == "a" }
useArray(filtered) // won't compile
Because of this, the new implementation of RangeReplaceableCollection.filter will only be available in Swift 4.

Effect on ABI stability

This change will affect the ABI of Sequence and needs to be made before declaring ABI stability.

Effect on API resilience

N/A

Alternatives considered

Status-quo. There are benefits to the consistency of always returning [Element].

It could be worthwhile to make a similar change to map, but this is beyond the capabilities of the current generics system because map does not preserve the element type (more specifically, you cannot express a type that is Self except with a different Element in order to provide the default implementation on RangeReplaceableCollection).

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Xiaodi Wu) #4

Ah, right. Collection can refine the associatedtype and constrain to
Collection, yes?

···

On Sun, Apr 23, 2017 at 3:12 PM, Ben Cohen <ben_cohen@apple.com> wrote:

On Apr 23, 2017, at 1:05 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

Is it the intention that `associatedtype Filtered : Sequence` once
recursive protocol constraints are supported?

Yup. Will add clarification.

Can it be `associatedtype Filtered : Collection`?

Sequence.lazy.filter returns a Sequence.


(Ben Cohen) #5

…yes, I think so. But that’s as far as we’d want to go e.g. a lazily filtered random-access collection is only bi-directional.

···

On Apr 23, 2017, at 1:30 PM, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

On Sun, Apr 23, 2017 at 3:12 PM, Ben Cohen <ben_cohen@apple.com <mailto:ben_cohen@apple.com>> wrote:

On Apr 23, 2017, at 1:05 PM, Xiaodi Wu <xiaodi.wu@gmail.com <mailto:xiaodi.wu@gmail.com>> wrote:

Is it the intention that `associatedtype Filtered : Sequence` once recursive protocol constraints are supported?

Yup. Will add clarification.

Can it be `associatedtype Filtered : Collection`?

Sequence.lazy.filter returns a Sequence.

Ah, right. Collection can refine the associatedtype and constrain to Collection, yes?