[Review] SE-0174: Change `filter` to return an associated type


(Douglas Gregor) #1

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type" begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager. When replying, please try to keep the proposal link at the top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reply text
Other replies
<https://github.com/apple/swift-evolution#what-goes-into-a-review-1>What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

What is your evaluation of the proposal?
Is the problem being addressed significant enough to warrant a change to Swift?
Does this proposal fit well with the feel and direction of Swift?
If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md
Thank you,

-Doug Gregor

Review Manager


(Jaden Geller) #2

I think that the alternatives considered section isn’t entirely correct. Even if we had a more expressive type system, it would not be possible to make the return value of `map` preserve the element type *while* still allowing types like `String`, which aren’t parameterized by an element, to conform.

I think this would require two separate mapping protocols (ignore the straw man names and syntax):

protocol Mappable: Sequence {
    func map(_ transform: (Iterator.Element) -> Iterator.Element) -> Self
    // could also add `mapInPlace`
}

protocol MappableFunctor: Mappable {
    kind Self<Iterator.Element>
    func map<T>(_ transform: (Iterator.Element) -> T) -> Self<T>
}

I think we’d also require either a way for the generic function to conform to the non-generic signature if there exists a conforming instantiation if both functions were to have the same name.

Also, we’d probably want a way to say that the `T` in the generic signature has the same type constraints as the generic parameter would need to…

···

Anyway, the point is that we *could* consider adding the first protocol right now (or more likely, add the requirement to `Sequence`) even though the second protocol is not possible yet. Even if/when Swift’s type system can handle that, the first protocol will still be necessary for types like `String` that cannot conform to the second.

Cheers,
Jaden Geller

On Apr 28, 2017, at 5:06 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type" begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager. When replying, please try to keep the proposal link at the top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reply text
Other replies
<https://github.com/apple/swift-evolution#what-goes-into-a-review-1>What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

What is your evaluation of the proposal?
Is the problem being addressed significant enough to warrant a change to Swift?
Does this proposal fit well with the feel and direction of Swift?
If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md
Thank you,

-Doug Gregor

Review Manager

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


(Howard Lovatt) #3

review of SE-0174 "Change `filter` to return an associated type"

What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always returning an array from collection operations is limiting. However I think this proposal feels like 'papering' over problems rather than fixing the root cause. I think it would be better to reject this and do two more adventurous proposals instead:

  1. Allow protocols to be generic, instead of associated types, so that you can write Sequence<T>
  2. Allow Self to accept a generic argument, so that you can write Self<T>

With these to, admittedly much more major changes, you can then write:

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Sequence<T>
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
    }
    extension RangeReplaceableCollection {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T> {
            var result = Self<T>()
            for element in self {
                if try isIncluded(element) {
                     result.append(element)
                }
            }
           return result
        }
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
            var result = Self<M>()
            for element in self {
                try result.append(mapper(element))
            }
           return result
        }
    }

Which I think both reads better and is more powerful since it allows map to be written also.

Is the problem being addressed significant enough to warrant a change to Swift?

Yes, return an array is a real pain

Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift into a corner were other problems can't be fixed because the underlying, real, problems still remain.

If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the solution I presented above.

How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy to overcome this limitation, and others, of the current library.

-- Howard.

···

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type" begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager. When replying, please try to keep the proposal link at the top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reply text
Other replies
What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

What is your evaluation of the proposal?
Is the problem being addressed significant enough to warrant a change to Swift?
Does this proposal fit well with the feel and direction of Swift?
If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md
Thank you,

-Doug Gregor

Review Manager

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


(Brent Royal-Gordon) #4

I'm in favor of this proposal, and I don't agree with the previous reviewers who think this should be coupled with more advanced type system features. However, I have a few questions:

* How will associated type inference interact with this? If you write a type-specific `filter`, will it be automatically favored over the `Array` version, or will you have to manually specify a `Filtered` typealias?

* Do we want to constrain `Filtered` to `Sequence` or `Collection`? Do we want to require `where Filtered.Iterator.Element == Self.Iterator.Element`?

* Will `AnySequence`/`AnyCollection` have a `Filtered` of type `AnySequence`/`AnyCollection`, or one of type `Array`?

No time for a full review, but I thought it'd be helpful to note these things before the review period was up.

···

On Apr 28, 2017, at 5:06 PM, Douglas Gregor via swift-evolution <swift-evolution@swift.org> wrote:

What is your evaluation of the proposal?

--
Brent Royal-Gordon
Architechies


#5

Another possibility is to make “map” generic on the return type, something
like:

extension Collection {
    func map<T: RangeReplaceableCollection> (transform: (Iterator.Element)
throws -> T.Iterator.Element) rethrows -> T {
        var result = T()
        for e in self { try result.append(transform(e)) }
        return result
    }
}

That way the user can choose what type they want. And since there is also a
more-specific implementation returning an Array, that is what you’ll get if
context does not constrain the type, so existing code will still work the
same.

We could do the same for “filter”, in which case the current proposal would
just change what the default type is. So…what I’m talking about here would
be purely additive and can happen later.

In any case, I do like the idea being proposed in SE–0174. If I have a
collection and I filter it down, it makes sense to still be the same kind
of collection. So, +1 from me.

Nevin


(Xiaodi Wu) #6

Howard, take a look at the generics manifesto section on generic protocols:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

It explains very nicely how what you're really asking for is not generic
protocols but generalized existentials. This would be nice to have, but
it's clearly not happening within the next month and it wouldn't change the
solution for filter, for which this proposal is the obvious fix.

···

On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution < swift-evolution@swift.org> wrote:

review of SE-0174 "Change `filter` to return an associated type"

   - What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always
returning an array from collection operations is limiting. However I think
this proposal feels like 'papering' over problems rather than fixing the
root cause. I think it would be better to reject this and do two more
adventurous proposals instead:

  1. Allow protocols to be generic, instead of associated types, so that
you can write Sequence<T>
  2. Allow Self to accept a generic argument, so that you can write Self<T>

With these to, admittedly much more major changes, you can then write:

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows ->
Sequence<T>
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
    }
    extension RangeReplaceableCollection {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T>
{
            var result = Self<T>()
            for element in self {
                if try isIncluded(element) {
                     result.append(element)
                }
            }
           return result
        }
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
            var result = Self<M>()
            for element in self {
                try result.append(mapper(element))
            }
           return result
        }
    }

Which I think both reads better and is more powerful since it allows map
to be written also.

   - Is the problem being addressed significant enough to warrant a
   change to Swift?

Yes, return an array is a real pain

   - Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift
into a corner were other problems can't be fixed because the underlying,
real, problems still remain.

   - If you have used other languages or libraries with a similar
   feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the
solution I presented above.

   - How much effort did you put into your review? A glance, a quick
   reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy to
overcome this limitation, and others, of the current library.

-- Howard.

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type"
begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md

Reviews are an important part of the Swift evolution process. All reviews
should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the
review manager. When replying, please try to keep the proposal link at the
top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md

Reply text

Other replies

<https://github.com/apple/swift-evolution#what-goes-into-a-review-1>What
goes into a review?

The goal of the review process is to improve the proposal under review
through constructive criticism and, eventually, determine the direction of
Swift. When writing your review, here are some questions you might want to
answer in your review:

   - What is your evaluation of the proposal?
   - Is the problem being addressed significant enough to warrant a
   change to Swift?
   - Does this proposal fit well with the feel and direction of Swift?
   - If you have used other languages or libraries with a similar
   feature, how do you feel that this proposal compares to those?
   - How much effort did you put into your review? A glance, a quick
   reading, or an in-depth study?

More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Doug Gregor

Review Manager

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

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


(Howard Lovatt) #7

Yes, I know the change I suggested involves making generalised existentials.
I am suggesting not making *any* changes until such effort is available. I
understand that this would be after Swift 4. I think the wait would be
worthwhile.

As an aside: Currently one of the big issues with generalised existentials
in Swift is with Self (which you can think of as a form of generic
argument). Currently:

    protocol Equatable {
        static func ==(lhs: Self, rhs: Self) -> Bool
        ...
    }
    struct Int: Equatable { ... }
    let e1: Equatable = 1
    let e2: Equatable = 2
    if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the same
dynamic type

I would replace this with:

    protocol Equatable<T> { // Use T instead of Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable<Int> { ... }
    let e1: Equatable<Int> = 1
    let e2: Equatable<Int> = 2
    if e1 == e2 { ... } // No longer an error since they are both
Equatable<Int>

As an aside on the aside, even better:

    protocol Equatable<T = Self> { // T defaults to Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable { ... } // T is Int, the default is Self
    let e1: Equatable = 1 // T is Int, the default is Self
    let e2: Equatable = 2 // T is Int, the default is Self
    if e1 == e2 { ... } // No longer an error since they are both
Equatable<Int>

Everything I am suggesting is done in other languages and from my personal
experience works out better.

  -- Howard.

···

On 2 May 2017 at 09:53, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

Howard, take a look at the generics manifesto section on generic protocols:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

It explains very nicely how what you're really asking for is not generic
protocols but generalized existentials. This would be nice to have, but
it's clearly not happening within the next month and it wouldn't change the
solution for filter, for which this proposal is the obvious fix.

On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution < > swift-evolution@swift.org> wrote:

review of SE-0174 "Change `filter` to return an associated type"

   - What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always
returning an array from collection operations is limiting. However I think
this proposal feels like 'papering' over problems rather than fixing the
root cause. I think it would be better to reject this and do two more
adventurous proposals instead:

  1. Allow protocols to be generic, instead of associated types, so that
you can write Sequence<T>
  2. Allow Self to accept a generic argument, so that you can write
Self<T>

With these to, admittedly much more major changes, you can then write:

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows ->
Sequence<T>
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
    }
    extension RangeReplaceableCollection {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T>
{
            var result = Self<T>()
            for element in self {
                if try isIncluded(element) {
                     result.append(element)
                }
            }
           return result
        }
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
            var result = Self<M>()
            for element in self {
                try result.append(mapper(element))
            }
           return result
        }
    }

Which I think both reads better and is more powerful since it allows map
to be written also.

   - Is the problem being addressed significant enough to warrant a
   change to Swift?

Yes, return an array is a real pain

   - Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift
into a corner were other problems can't be fixed because the underlying,
real, problems still remain.

   - If you have used other languages or libraries with a similar
   feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the
solution I presented above.

   - How much effort did you put into your review? A glance, a quick
   reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy to
overcome this limitation, and others, of the current library.

-- Howard.

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type"
begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/
proposals/0174-filter-range-replaceable.md

Reviews are an important part of the Swift evolution process. All reviews
should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the
review manager. When replying, please try to keep the proposal link at the
top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/
proposals/0174-filter-range-replaceable.md

Reply text

Other replies

<https://github.com/apple/swift-evolution#what-goes-into-a-review-1>What
goes into a review?

The goal of the review process is to improve the proposal under review
through constructive criticism and, eventually, determine the direction of
Swift. When writing your review, here are some questions you might want to
answer in your review:

   - What is your evaluation of the proposal?
   - Is the problem being addressed significant enough to warrant a
   change to Swift?
   - Does this proposal fit well with the feel and direction of Swift?
   - If you have used other languages or libraries with a similar
   feature, how do you feel that this proposal compares to those?
   - How much effort did you put into your review? A glance, a quick
   reading, or an in-depth study?

More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Doug Gregor

Review Manager

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

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


(Xiaodi Wu) #8

Not an author, but I asked Ben a similar question during the pitch to one
of yours.

He clarified that the intention was to constrain Filtered to Sequence once
recursive constraints are implemented. Collection will refine to constrain
Filtered to Collection, and Ben said that this was about as far as he was
willing to go in terms of successive refinements.

···

On Wed, May 3, 2017 at 00:33 Brent Royal-Gordon via swift-evolution < swift-evolution@swift.org> wrote:

On Apr 28, 2017, at 5:06 PM, Douglas Gregor via swift-evolution < > swift-evolution@swift.org> wrote:

   - What is your evaluation of the proposal?

I'm in favor of this proposal, and I don't agree with the previous
reviewers who think this should be coupled with more advanced type system
features. However, I have a few questions:

* How will associated type inference interact with this? If you write a
type-specific `filter`, will it be automatically favored over the `Array`
version, or will you have to manually specify a `Filtered` typealias?

* Do we want to constrain `Filtered` to `Sequence` or `Collection`? Do we
want to require `where Filtered.Iterator.Element == Self.Iterator.Element`?

* Will `AnySequence`/`AnyCollection` have a `Filtered` of type
`AnySequence`/`AnyCollection`, or one of type `Array`?

No time for a full review, but I thought it'd be helpful to note these
things before the review period was up.

--
Brent Royal-Gordon
Architechies

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


(TJ Usiyan) #9

+1

There are many things that I would like more but this is a reasonable
compromise.

···

On Mon, May 1, 2017 at 8:02 PM, Nevin Brackett-Rozinsky via swift-evolution <swift-evolution@swift.org> wrote:

Another possibility is to make “map” generic on the return type, something
like:

extension Collection {
    func map<T: RangeReplaceableCollection> (transform: (Iterator.Element)
throws -> T.Iterator.Element) rethrows -> T {
        var result = T()
        for e in self { try result.append(transform(e)) }
        return result
    }
}

That way the user can choose what type they want. And since there is also
a more-specific implementation returning an Array, that is what you’ll get
if context does not constrain the type, so existing code will still work
the same.

We could do the same for “filter”, in which case the current proposal
would just change what the default type is. So…what I’m talking about here
would be purely additive and can happen later.

In any case, I do like the idea being proposed in SE–0174. If I have a
collection and I filter it down, it makes sense to still be the same kind
of collection. So, +1 from me.

Nevin

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


(Xiaodi Wu) #10

Howard, this is also mentioned in the generics manifesto under "Opening
existentials," and it's received plentiful discussion and will surely
receive more as these issues become addressed in future proposals. Let's
not divert the conversation here about map and filter.

···

On Mon, May 1, 2017 at 19:36 Howard Lovatt <howard.lovatt@gmail.com> wrote:

Yes, I know the change I suggested involves making generalised
existentials. I am suggesting not making *any* changes until such effort
is available. I understand that this would be after Swift 4. I think the
wait would be worthwhile.

As an aside: Currently one of the big issues with generalised existentials
in Swift is with Self (which you can think of as a form of generic
argument). Currently:

    protocol Equatable {
        static func ==(lhs: Self, rhs: Self) -> Bool
        ...
    }
    struct Int: Equatable { ... }
    let e1: Equatable = 1
    let e2: Equatable = 2
    if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the
same dynamic type

I would replace this with:

    protocol Equatable<T> { // Use T instead of Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable<Int> { ... }
    let e1: Equatable<Int> = 1
    let e2: Equatable<Int> = 2
    if e1 == e2 { ... } // No longer an error since they are both
Equatable<Int>

As an aside on the aside, even better:

    protocol Equatable<T = Self> { // T defaults to Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable { ... } // T is Int, the default is Self
    let e1: Equatable = 1 // T is Int, the default is Self
    let e2: Equatable = 2 // T is Int, the default is Self
    if e1 == e2 { ... } // No longer an error since they are both
Equatable<Int>

Everything I am suggesting is done in other languages and from my personal
experience works out better.

  -- Howard.

On 2 May 2017 at 09:53, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

Howard, take a look at the generics manifesto section on generic
protocols:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

It explains very nicely how what you're really asking for is not generic
protocols but generalized existentials. This would be nice to have, but
it's clearly not happening within the next month and it wouldn't change the
solution for filter, for which this proposal is the obvious fix.

On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution < >> swift-evolution@swift.org> wrote:

review of SE-0174 "Change `filter` to return an associated type"

   - What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always
returning an array from collection operations is limiting. However I think
this proposal feels like 'papering' over problems rather than fixing the
root cause. I think it would be better to reject this and do two more
adventurous proposals instead:

  1. Allow protocols to be generic, instead of associated types, so that
you can write Sequence<T>
  2. Allow Self to accept a generic argument, so that you can write
Self<T>

With these to, admittedly much more major changes, you can then write:

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows ->
Sequence<T>
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
    }
    extension RangeReplaceableCollection {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows ->
Self<T> {
            var result = Self<T>()
            for element in self {
                if try isIncluded(element) {
                     result.append(element)
                }
            }
           return result
        }
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
            var result = Self<M>()
            for element in self {
                try result.append(mapper(element))
            }
           return result
        }
    }

Which I think both reads better and is more powerful since it allows map
to be written also.

   - Is the problem being addressed significant enough to warrant a
   change to Swift?

Yes, return an array is a real pain

   - Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift
into a corner were other problems can't be fixed because the underlying,
real, problems still remain.

   - If you have used other languages or libraries with a similar
   feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the
solution I presented above.

   - How much effort did you put into your review? A glance, a quick
   reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy to
overcome this limitation, and others, of the current library.

-- Howard.

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type"
begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md

Reviews are an important part of the Swift evolution process. All
reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the
review manager. When replying, please try to keep the proposal link at the
top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md

Reply text

Other replies

<https://github.com/apple/swift-evolution#what-goes-into-a-review-1>What
goes into a review?

The goal of the review process is to improve the proposal under review
through constructive criticism and, eventually, determine the direction of
Swift. When writing your review, here are some questions you might want to
answer in your review:

   - What is your evaluation of the proposal?
   - Is the problem being addressed significant enough to warrant a
   change to Swift?
   - Does this proposal fit well with the feel and direction of Swift?
   - If you have used other languages or libraries with a similar
   feature, how do you feel that this proposal compares to those?
   - How much effort did you put into your review? A glance, a quick
   reading, or an in-depth study?

More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Doug Gregor

Review Manager

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

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


(Anders) #11

I would like to add that generalized existential is not really a better solution than letting the collection optionally and statically supply one. It consequentially forces all calls to the filtered collections virtual/dynamic.

Higher kinded type would ideally help, but we all know it is not coming anytime soon, or perhaps ever.

Regards
Anders

···

On 2 May 2017, at 08:41, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Howard, this is also mentioned in the generics manifesto under "Opening existentials," and it's received plentiful discussion and will surely receive more as these issues become addressed in future proposals. Let's not divert the conversation here about map and filter.

On Mon, May 1, 2017 at 19:36 Howard Lovatt <howard.lovatt@gmail.com> wrote:
Yes, I know the change I suggested involves making generalised existentials. I am suggesting not making *any* changes until such effort is available. I understand that this would be after Swift 4. I think the wait would be worthwhile.

As an aside: Currently one of the big issues with generalised existentials in Swift is with Self (which you can think of as a form of generic argument). Currently:

    protocol Equatable {
        static func ==(lhs: Self, rhs: Self) -> Bool
        ...
    }
    struct Int: Equatable { ... }
    let e1: Equatable = 1
    let e2: Equatable = 2
    if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the same dynamic type

I would replace this with:

    protocol Equatable<T> { // Use T instead of Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable<Int> { ... }
    let e1: Equatable<Int> = 1
    let e2: Equatable<Int> = 2
    if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

As an aside on the aside, even better:

    protocol Equatable<T = Self> { // T defaults to Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable { ... } // T is Int, the default is Self
    let e1: Equatable = 1 // T is Int, the default is Self
    let e2: Equatable = 2 // T is Int, the default is Self
    if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

Everything I am suggesting is done in other languages and from my personal experience works out better.

  -- Howard.

On 2 May 2017 at 09:53, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
Howard, take a look at the generics manifesto section on generic protocols:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

It explains very nicely how what you're really asking for is not generic protocols but generalized existentials. This would be nice to have, but it's clearly not happening within the next month and it wouldn't change the solution for filter, for which this proposal is the obvious fix.

On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution <swift-evolution@swift.org> wrote:

review of SE-0174 "Change `filter` to return an associated type"

What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always returning an array from collection operations is limiting. However I think this proposal feels like 'papering' over problems rather than fixing the root cause. I think it would be better to reject this and do two more adventurous proposals instead:

  1. Allow protocols to be generic, instead of associated types, so that you can write Sequence<T>
  2. Allow Self to accept a generic argument, so that you can write Self<T>

With these to, admittedly much more major changes, you can then write:

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Sequence<T>
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
    }
    extension RangeReplaceableCollection {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T> {
            var result = Self<T>()
            for element in self {
                if try isIncluded(element) {
                     result.append(element)
                }
            }
           return result
        }
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
            var result = Self<M>()
            for element in self {
                try result.append(mapper(element))
            }
           return result
        }
    }

Which I think both reads better and is more powerful since it allows map to be written also.

Is the problem being addressed significant enough to warrant a change to Swift?

Yes, return an array is a real pain

Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift into a corner were other problems can't be fixed because the underlying, real, problems still remain.

If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the solution I presented above.

How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy to overcome this limitation, and others, of the current library.

-- Howard.

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type" begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager. When replying, please try to keep the proposal link at the top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reply text
Other replies
What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

What is your evaluation of the proposal?
Is the problem being addressed significant enough to warrant a change to Swift?
Does this proposal fit well with the feel and direction of Swift?
If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md
Thank you,

-Doug Gregor

Review Manager

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

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

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


(Howard Lovatt) #12

My experience with languages that have generalised existential is that they are superior in many circumstances; not just for collections, e.g. I gave the example of the comparison protocol.

I don't think methods called on a returned generalised existential have to be called via a Vtable. If the return type is Self<T> then the compiler can eliminate the Vtable for selfs that are value types. For selfs that are classes it would still have to use a Vtable though, because classes always use Vtables! In most cases the return type will be Self<T> and in most cases the Self will be a value type, so I would argue that in most cases a Vtable won't be used.

-- Howard.

···

On 2 May 2017, at 8:57 pm, Anders Ha <hello@andersio.co> wrote:

I would like to add that generalized existential is not really a better solution than letting the collection optionally and statically supply one. It consequentially forces all calls to the filtered collections virtual/dynamic.

Higher kinded type would ideally help, but we all know it is not coming anytime soon, or perhaps ever.

Regards
Anders

On 2 May 2017, at 08:41, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Howard, this is also mentioned in the generics manifesto under "Opening existentials," and it's received plentiful discussion and will surely receive more as these issues become addressed in future proposals. Let's not divert the conversation here about map and filter.

On Mon, May 1, 2017 at 19:36 Howard Lovatt <howard.lovatt@gmail.com> wrote:
Yes, I know the change I suggested involves making generalised existentials. I am suggesting not making *any* changes until such effort is available. I understand that this would be after Swift 4. I think the wait would be worthwhile.

As an aside: Currently one of the big issues with generalised existentials in Swift is with Self (which you can think of as a form of generic argument). Currently:

    protocol Equatable {
        static func ==(lhs: Self, rhs: Self) -> Bool
        ...
    }
    struct Int: Equatable { ... }
    let e1: Equatable = 1
    let e2: Equatable = 2
    if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the same dynamic type

I would replace this with:

    protocol Equatable<T> { // Use T instead of Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable<Int> { ... }
    let e1: Equatable<Int> = 1
    let e2: Equatable<Int> = 2
    if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

As an aside on the aside, even better:

    protocol Equatable<T = Self> { // T defaults to Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable { ... } // T is Int, the default is Self
    let e1: Equatable = 1 // T is Int, the default is Self
    let e2: Equatable = 2 // T is Int, the default is Self
    if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

Everything I am suggesting is done in other languages and from my personal experience works out better.

  -- Howard.

On 2 May 2017 at 09:53, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
Howard, take a look at the generics manifesto section on generic protocols:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

It explains very nicely how what you're really asking for is not generic protocols but generalized existentials. This would be nice to have, but it's clearly not happening within the next month and it wouldn't change the solution for filter, for which this proposal is the obvious fix.

On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution <swift-evolution@swift.org> wrote:

review of SE-0174 "Change `filter` to return an associated type"

What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always returning an array from collection operations is limiting. However I think this proposal feels like 'papering' over problems rather than fixing the root cause. I think it would be better to reject this and do two more adventurous proposals instead:

  1. Allow protocols to be generic, instead of associated types, so that you can write Sequence<T>
  2. Allow Self to accept a generic argument, so that you can write Self<T>

With these to, admittedly much more major changes, you can then write:

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Sequence<T>
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
    }
    extension RangeReplaceableCollection {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T> {
            var result = Self<T>()
            for element in self {
                if try isIncluded(element) {
                     result.append(element)
                }
            }
           return result
        }
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
            var result = Self<M>()
            for element in self {
                try result.append(mapper(element))
            }
           return result
        }
    }

Which I think both reads better and is more powerful since it allows map to be written also.

Is the problem being addressed significant enough to warrant a change to Swift?

Yes, return an array is a real pain

Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift into a corner were other problems can't be fixed because the underlying, real, problems still remain.

If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the solution I presented above.

How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy to overcome this limitation, and others, of the current library.

-- Howard.

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type" begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager. When replying, please try to keep the proposal link at the top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reply text
Other replies
What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

What is your evaluation of the proposal?
Is the problem being addressed significant enough to warrant a change to Swift?
Does this proposal fit well with the feel and direction of Swift?
If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md
Thank you,

-Doug Gregor

Review Manager

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

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

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


(Goffredo Marocchi) #13

My experience with languages that have generalised existential is that they are superior in many circumstances; not just for collections, e.g. I gave the example of the comparison protocol.

I think generalised existential is where we want to get to, is it not?

···

Sent from my iPhone

On 3 May 2017, at 02:05, Howard Lovatt via swift-evolution <swift-evolution@swift.org> wrote:

I don't think methods called on a returned generalised existential have to be called via a Vtable. If the return type is Self<T> then the compiler can eliminate the Vtable for selfs that are value types. For selfs that are classes it would still have to use a Vtable though, because classes always use Vtables! In most cases the return type will be Self<T> and in most cases the Self will be a value type, so I would argue that in most cases a Vtable won't be used.

-- Howard.

On 2 May 2017, at 8:57 pm, Anders Ha <hello@andersio.co> wrote:

I would like to add that generalized existential is not really a better solution than letting the collection optionally and statically supply one. It consequentially forces all calls to the filtered collections virtual/dynamic.

Higher kinded type would ideally help, but we all know it is not coming anytime soon, or perhaps ever.

Regards
Anders

On 2 May 2017, at 08:41, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Howard, this is also mentioned in the generics manifesto under "Opening existentials," and it's received plentiful discussion and will surely receive more as these issues become addressed in future proposals. Let's not divert the conversation here about map and filter.

On Mon, May 1, 2017 at 19:36 Howard Lovatt <howard.lovatt@gmail.com> wrote:
Yes, I know the change I suggested involves making generalised existentials. I am suggesting not making *any* changes until such effort is available. I understand that this would be after Swift 4. I think the wait would be worthwhile.

As an aside: Currently one of the big issues with generalised existentials in Swift is with Self (which you can think of as a form of generic argument). Currently:

    protocol Equatable {
        static func ==(lhs: Self, rhs: Self) -> Bool
        ...
    }
    struct Int: Equatable { ... }
    let e1: Equatable = 1
    let e2: Equatable = 2
    if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the same dynamic type

I would replace this with:

    protocol Equatable<T> { // Use T instead of Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable<Int> { ... }
    let e1: Equatable<Int> = 1
    let e2: Equatable<Int> = 2
    if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

As an aside on the aside, even better:

    protocol Equatable<T = Self> { // T defaults to Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable { ... } // T is Int, the default is Self
    let e1: Equatable = 1 // T is Int, the default is Self
    let e2: Equatable = 2 // T is Int, the default is Self
    if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

Everything I am suggesting is done in other languages and from my personal experience works out better.

  -- Howard.

On 2 May 2017 at 09:53, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
Howard, take a look at the generics manifesto section on generic protocols:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

It explains very nicely how what you're really asking for is not generic protocols but generalized existentials. This would be nice to have, but it's clearly not happening within the next month and it wouldn't change the solution for filter, for which this proposal is the obvious fix.

On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution <swift-evolution@swift.org> wrote:

review of SE-0174 "Change `filter` to return an associated type"

What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always returning an array from collection operations is limiting. However I think this proposal feels like 'papering' over problems rather than fixing the root cause. I think it would be better to reject this and do two more adventurous proposals instead:

  1. Allow protocols to be generic, instead of associated types, so that you can write Sequence<T>
  2. Allow Self to accept a generic argument, so that you can write Self<T>

With these to, admittedly much more major changes, you can then write:

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Sequence<T>
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
    }
    extension RangeReplaceableCollection {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T> {
            var result = Self<T>()
            for element in self {
                if try isIncluded(element) {
                     result.append(element)
                }
            }
           return result
        }
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
            var result = Self<M>()
            for element in self {
                try result.append(mapper(element))
            }
           return result
        }
    }

Which I think both reads better and is more powerful since it allows map to be written also.

Is the problem being addressed significant enough to warrant a change to Swift?

Yes, return an array is a real pain

Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift into a corner were other problems can't be fixed because the underlying, real, problems still remain.

If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the solution I presented above.

How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy to overcome this limitation, and others, of the current library.

-- Howard.

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type" begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager. When replying, please try to keep the proposal link at the top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reply text
Other replies
What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

What is your evaluation of the proposal?
Is the problem being addressed significant enough to warrant a change to Swift?
Does this proposal fit well with the feel and direction of Swift?
If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md
Thank you,

-Doug Gregor

Review Manager

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

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

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

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


(Anders) #14

Returning `Self<T>` requires higher kinded type. Note that parameterized protocols are not the same as higher kinded types, since for the former generic protocol parameters are already bound at conformance of the static `Self` like associated types, while the later is about having a generic static `Self`.

IOW you cannot do `Self<T>` statically without higher kinded type. The best you can get is generalized existential, e.g. `filter` returning a `Collection where .Element == T` or `Collection<T>` if protocols can be parameterized.

The compiler cannot eliminate virtual dispatching for existentials, because this is what existential is by definition — knowing how to manipulate it at static time, but not the type which varies at runtime. All non-class existentials are dispatched through their associated protocol witness tables.

Regards
Anders

···

On 3 May 2017, at 09:05, Howard Lovatt <howard.lovatt@gmail.com> wrote:

My experience with languages that have generalised existential is that they are superior in many circumstances; not just for collections, e.g. I gave the example of the comparison protocol.

I don't think methods called on a returned generalised existential have to be called via a Vtable. If the return type is Self<T> then the compiler can eliminate the Vtable for selfs that are value types. For selfs that are classes it would still have to use a Vtable though, because classes always use Vtables! In most cases the return type will be Self<T> and in most cases the Self will be a value type, so I would argue that in most cases a Vtable won't be used.

-- Howard.

On 2 May 2017, at 8:57 pm, Anders Ha <hello@andersio.co> wrote:

I would like to add that generalized existential is not really a better solution than letting the collection optionally and statically supply one. It consequentially forces all calls to the filtered collections virtual/dynamic.

Higher kinded type would ideally help, but we all know it is not coming anytime soon, or perhaps ever.

Regards
Anders

On 2 May 2017, at 08:41, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Howard, this is also mentioned in the generics manifesto under "Opening existentials," and it's received plentiful discussion and will surely receive more as these issues become addressed in future proposals. Let's not divert the conversation here about map and filter.

On Mon, May 1, 2017 at 19:36 Howard Lovatt <howard.lovatt@gmail.com> wrote:
Yes, I know the change I suggested involves making generalised existentials. I am suggesting not making *any* changes until such effort is available. I understand that this would be after Swift 4. I think the wait would be worthwhile.

As an aside: Currently one of the big issues with generalised existentials in Swift is with Self (which you can think of as a form of generic argument). Currently:

    protocol Equatable {
        static func ==(lhs: Self, rhs: Self) -> Bool
        ...
    }
    struct Int: Equatable { ... }
    let e1: Equatable = 1
    let e2: Equatable = 2
    if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the same dynamic type

I would replace this with:

    protocol Equatable<T> { // Use T instead of Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable<Int> { ... }
    let e1: Equatable<Int> = 1
    let e2: Equatable<Int> = 2
    if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

As an aside on the aside, even better:

    protocol Equatable<T = Self> { // T defaults to Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable { ... } // T is Int, the default is Self
    let e1: Equatable = 1 // T is Int, the default is Self
    let e2: Equatable = 2 // T is Int, the default is Self
    if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

Everything I am suggesting is done in other languages and from my personal experience works out better.

  -- Howard.

On 2 May 2017 at 09:53, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
Howard, take a look at the generics manifesto section on generic protocols:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

It explains very nicely how what you're really asking for is not generic protocols but generalized existentials. This would be nice to have, but it's clearly not happening within the next month and it wouldn't change the solution for filter, for which this proposal is the obvious fix.

On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution <swift-evolution@swift.org> wrote:

review of SE-0174 "Change `filter` to return an associated type"

What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always returning an array from collection operations is limiting. However I think this proposal feels like 'papering' over problems rather than fixing the root cause. I think it would be better to reject this and do two more adventurous proposals instead:

  1. Allow protocols to be generic, instead of associated types, so that you can write Sequence<T>
  2. Allow Self to accept a generic argument, so that you can write Self<T>

With these to, admittedly much more major changes, you can then write:

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Sequence<T>
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
    }
    extension RangeReplaceableCollection {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T> {
            var result = Self<T>()
            for element in self {
                if try isIncluded(element) {
                     result.append(element)
                }
            }
           return result
        }
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
            var result = Self<M>()
            for element in self {
                try result.append(mapper(element))
            }
           return result
        }
    }

Which I think both reads better and is more powerful since it allows map to be written also.

Is the problem being addressed significant enough to warrant a change to Swift?

Yes, return an array is a real pain

Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift into a corner were other problems can't be fixed because the underlying, real, problems still remain.

If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the solution I presented above.

How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy to overcome this limitation, and others, of the current library.

-- Howard.

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type" begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager. When replying, please try to keep the proposal link at the top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reply text
Other replies
What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

What is your evaluation of the proposal?
Is the problem being addressed significant enough to warrant a change to Swift?
Does this proposal fit well with the feel and direction of Swift?
If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md
Thank you,

-Doug Gregor

Review Manager

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

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

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


(Howard Lovatt) #15

@Anders,

I think you can eliminate the dynamic dispatch for a struct. Using the
generic parameterised syntax rather than the where clause syntax (because
it is more compact and clearer):

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) -> Bool) -> Self<T> // Note: returns
Self<T>
        ...
    }
    extension Sequence {
        func filter(_ isIncluded: (T) -> Bool) -> Self<T> { // Note:
returns Self<T>
            var result = Self<T>
            for element in self {
                if isIncluded(element) { result.append(element) }
            }
            return result
        }
        ...
    }
    struct Set<T>: Sequence<T> { ... } // Inherits filter from extension

For struct `Set<T>` `Self<T>` is `Set<T>` (obviously, that is what Self
means), therefore the compiler can for both code and type checking purposes
generate:

    struct Set<T>: Sequence<T> {
        func filter(_ isIncluded: (T) -> Bool) -> Set<T> { // Note: returns
Set<T>
            var result = Set<T>
            for element in self {
                if isIncluded(element) { result.append(element) }
            }
            return result
        }
        ...
    }

This is an intermediate step for the compiler since `Set` is still generic,
in `T`. When a specific `Set` is instantiated, e.g. `let s = Set<Int>`, the
compiler can generate both for code and type checking purposes:

    struct Set<Int>: Sequence<Int> {
        func filter(_ isIncluded: (Int) -> Bool) -> Set<Int> { // Note:
returns Set<Int>
            var result = Set<Int>
            for element in self {
                if isIncluded(element) { result.append(element) }
            }
            return result
        }
        ...
    }

When you call `s.filter` there is no dynamic dispatch because `filter` is
final within a struct and the compiler also knows that this version of
`filter` returns a `Set<Int>` and therefore no dynamic dispatch on the
returned value if in a chain of calls either.

Have I made a mistake in the above?

  -- Howard.

···

On 3 May 2017 at 17:27, Anders Ha <hello@andersio.co> wrote:

Returning `Self<T>` requires higher kinded type. Note that parameterized
protocols are not the same as higher kinded types, since for the former
generic protocol parameters are already bound at conformance of the static
`Self` like associated types, while the later is about having a generic
static `Self`.

IOW you cannot do `Self<T>` statically without higher kinded type. The
best you can get is generalized existential, e.g. `filter` returning a `Collection
where .Element == T` or `Collection<T>` if protocols can be parameterized.

The compiler cannot eliminate virtual dispatching for existentials,
because this is what existential is by definition — knowing how to
manipulate it at static time, but not the type which varies at runtime. All
non-class existentials are dispatched through their associated protocol
witness tables.

Regards
Anders

On 3 May 2017, at 09:05, Howard Lovatt <howard.lovatt@gmail.com> wrote:

My experience with languages that have generalised existential is that
they are superior in many circumstances; not just for collections, e.g. I
gave the example of the comparison protocol.

I don't think methods called on a returned generalised existential have
to be called via a Vtable. If the return type is Self<T> then the compiler
can eliminate the Vtable for selfs that are value types. For selfs that are
classes it would still have to use a Vtable though, because classes always
use Vtables! In most cases the return type will be Self<T> and in most
cases the Self will be a value type, so I would argue that in most cases a
Vtable won't be used.

-- Howard.

On 2 May 2017, at 8:57 pm, Anders Ha <hello@andersio.co> wrote:

I would like to add that generalized existential is not really a better
solution than letting the collection optionally and statically supply one.
It consequentially forces all calls to the filtered collections
virtual/dynamic.

Higher kinded type would ideally help, but we all know it is not coming
anytime soon, or perhaps ever.

Regards
Anders

On 2 May 2017, at 08:41, Xiaodi Wu via swift-evolution < > swift-evolution@swift.org> wrote:

Howard, this is also mentioned in the generics manifesto under "Opening
existentials," and it's received plentiful discussion and will surely
receive more as these issues become addressed in future proposals. Let's
not divert the conversation here about map and filter.
On Mon, May 1, 2017 at 19:36 Howard Lovatt <howard.lovatt@gmail.com> > wrote:

Yes, I know the change I suggested involves making generalised
existentials. I am suggesting not making *any* changes until such effort
is available. I understand that this would be after Swift 4. I think the
wait would be worthwhile.

As an aside: Currently one of the big issues with generalised
existentials in Swift is with Self (which you can think of as a form of
generic argument). Currently:

    protocol Equatable {
        static func ==(lhs: Self, rhs: Self) -> Bool
        ...
    }
    struct Int: Equatable { ... }
    let e1: Equatable = 1
    let e2: Equatable = 2
    if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the
same dynamic type

I would replace this with:

    protocol Equatable<T> { // Use T instead of Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable<Int> { ... }
    let e1: Equatable<Int> = 1
    let e2: Equatable<Int> = 2
    if e1 == e2 { ... } // No longer an error since they are both
Equatable<Int>

As an aside on the aside, even better:

    protocol Equatable<T = Self> { // T defaults to Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable { ... } // T is Int, the default is Self
    let e1: Equatable = 1 // T is Int, the default is Self
    let e2: Equatable = 2 // T is Int, the default is Self
    if e1 == e2 { ... } // No longer an error since they are both
Equatable<Int>

Everything I am suggesting is done in other languages and from my
personal experience works out better.

  -- Howard.

On 2 May 2017 at 09:53, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:

Howard, take a look at the generics manifesto section on generic
protocols:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

It explains very nicely how what you're really asking for is not generic
protocols but generalized existentials. This would be nice to have, but
it's clearly not happening within the next month and it wouldn't change the
solution for filter, for which this proposal is the obvious fix.

On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution < >>> swift-evolution@swift.org> wrote:

review of SE-0174 "Change `filter` to return an associated type"

   - What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always
returning an array from collection operations is limiting. However I think
this proposal feels like 'papering' over problems rather than fixing the
root cause. I think it would be better to reject this and do two more
adventurous proposals instead:

  1. Allow protocols to be generic, instead of associated types, so
that you can write Sequence<T>
  2. Allow Self to accept a generic argument, so that you can write
Self<T>

With these to, admittedly much more major changes, you can then write:

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows ->
Sequence<T>
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
    }
    extension RangeReplaceableCollection {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows ->
Self<T> {
            var result = Self<T>()
            for element in self {
                if try isIncluded(element) {
                     result.append(element)
                }
            }
           return result
        }
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
            var result = Self<M>()
            for element in self {
                try result.append(mapper(element))
            }
           return result
        }
    }

Which I think both reads better and is more powerful since it allows
map to be written also.

   - Is the problem being addressed significant enough to warrant a
   change to Swift?

Yes, return an array is a real pain

   - Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift
into a corner were other problems can't be fixed because the underlying,
real, problems still remain.

   - If you have used other languages or libraries with a similar
   feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the
solution I presented above.

   - How much effort did you put into your review? A glance, a quick
   reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy
to overcome this limitation, and others, of the current library.

-- Howard.

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type"
begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/
proposals/0174-filter-range-replaceable.md

Reviews are an important part of the Swift evolution process. All
reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution

or, if you would like to keep your feedback private, directly to the
review manager. When replying, please try to keep the proposal link at the
top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/
proposals/0174-filter-range-replaceable.md

Reply text

Other replies

<https://github.com/apple/swift-evolution#what-goes-into-a-review-1>What
goes into a review?

The goal of the review process is to improve the proposal under review
through constructive criticism and, eventually, determine the direction of
Swift. When writing your review, here are some questions you might want to
answer in your review:

   - What is your evaluation of the proposal?
   - Is the problem being addressed significant enough to warrant a
   change to Swift?
   - Does this proposal fit well with the feel and direction of Swift?
   - If you have used other languages or libraries with a similar
   feature, how do you feel that this proposal compares to those?
   - How much effort did you put into your review? A glance, a quick
   reading, or an in-depth study?

More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md

Thank you,

-Doug Gregor

Review Manager

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

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

_______________________________________________

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


(Anders) #16

So a bit of correction: generic protocol had been dismissed in the Generic Manifesto specifically for sequences and collections, because it would permit multiple conformances of a certain type to the same protocol with different types of elements, and it is considered wrong.

`Self` in a protocol refers not to the unbound generic type, but to the specialized one, e.g. `Array<T>` where T is bound, instead of `Array`. For your code snippets to work, the compiler would need to explicitly “unspecialize” the specialised `Self` and parameterise it with a different type. This notion is called higher-kinded types.

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#higher-kinded-types

For example, using the potential syntax in the manifesto:

    extension RangeReplaceableCollection {
        func filter<Filtered>(_ isIncluded: (Element) -> Bool) -> Filtered where Filtered ~= Self, Filtered.Element == Element
        func map<Mapped>(_ transform: (Element) -> Mapped.Element) -> Mapped where Mapped ~= Self
    }

Let’s say `Self` is `Set<Int>`, the compiler would need to be instructed to “unspecialize” it and parameterise it again, so that it still knows the resulting collection statically. Then at this point, yes, it can be statically dispatched.

But for now, higher-kinded types do not seem to be on the radar at all. So to achieve the same result, there are only two options:

1. Type-erased wrappers, e.g. `AnyCollection<T>`, or generalised existential, e.g. `Collection where .Element == T`. This means dynamic dispatch.
2. Associated type, i.e. the proposal.

Another important constraint you’ve missed is that only `RangeReplaceableCollection` implies the collection can be explicitly constructed. So a default of `[Element]` is necessary.

Regards
Anders

···

On 3 May 2017, at 4:57 PM, Howard Lovatt <howard.lovatt@gmail.com> wrote:

@Anders,

I think you can eliminate the dynamic dispatch for a struct. Using the generic parameterised syntax rather than the where clause syntax (because it is more compact and clearer):

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) -> Bool) -> Self<T> // Note: returns Self<T>
        ...
    }
    extension Sequence {
        func filter(_ isIncluded: (T) -> Bool) -> Self<T> { // Note: returns Self<T>
            var result = Self<T>
            for element in self {
                if isIncluded(element) { result.append(element) }
            }
            return result
        }
        ...
    }
    struct Set<T>: Sequence<T> { ... } // Inherits filter from extension

For struct `Set<T>` `Self<T>` is `Set<T>` (obviously, that is what Self means), therefore the compiler can for both code and type checking purposes generate:

    struct Set<T>: Sequence<T> {
        func filter(_ isIncluded: (T) -> Bool) -> Set<T> { // Note: returns Set<T>
            var result = Set<T>
            for element in self {
                if isIncluded(element) { result.append(element) }
            }
            return result
        }
        ...
    }

This is an intermediate step for the compiler since `Set` is still generic, in `T`. When a specific `Set` is instantiated, e.g. `let s = Set<Int>`, the compiler can generate both for code and type checking purposes:

    struct Set<Int>: Sequence<Int> {
        func filter(_ isIncluded: (Int) -> Bool) -> Set<Int> { // Note: returns Set<Int>
            var result = Set<Int>
            for element in self {
                if isIncluded(element) { result.append(element) }
            }
            return result
        }
        ...
    }

When you call `s.filter` there is no dynamic dispatch because `filter` is final within a struct and the compiler also knows that this version of `filter` returns a `Set<Int>` and therefore no dynamic dispatch on the returned value if in a chain of calls either.

Have I made a mistake in the above?

  -- Howard.

On 3 May 2017 at 17:27, Anders Ha <hello@andersio.co> wrote:
Returning `Self<T>` requires higher kinded type. Note that parameterized protocols are not the same as higher kinded types, since for the former generic protocol parameters are already bound at conformance of the static `Self` like associated types, while the later is about having a generic static `Self`.

IOW you cannot do `Self<T>` statically without higher kinded type. The best you can get is generalized existential, e.g. `filter` returning a `Collection where .Element == T` or `Collection<T>` if protocols can be parameterized.

The compiler cannot eliminate virtual dispatching for existentials, because this is what existential is by definition — knowing how to manipulate it at static time, but not the type which varies at runtime. All non-class existentials are dispatched through their associated protocol witness tables.

Regards
Anders

On 3 May 2017, at 09:05, Howard Lovatt <howard.lovatt@gmail.com> wrote:

My experience with languages that have generalised existential is that they are superior in many circumstances; not just for collections, e.g. I gave the example of the comparison protocol.

I don't think methods called on a returned generalised existential have to be called via a Vtable. If the return type is Self<T> then the compiler can eliminate the Vtable for selfs that are value types. For selfs that are classes it would still have to use a Vtable though, because classes always use Vtables! In most cases the return type will be Self<T> and in most cases the Self will be a value type, so I would argue that in most cases a Vtable won't be used.

-- Howard.

On 2 May 2017, at 8:57 pm, Anders Ha <hello@andersio.co> wrote:

I would like to add that generalized existential is not really a better solution than letting the collection optionally and statically supply one. It consequentially forces all calls to the filtered collections virtual/dynamic.

Higher kinded type would ideally help, but we all know it is not coming anytime soon, or perhaps ever.

Regards
Anders

On 2 May 2017, at 08:41, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Howard, this is also mentioned in the generics manifesto under "Opening existentials," and it's received plentiful discussion and will surely receive more as these issues become addressed in future proposals. Let's not divert the conversation here about map and filter.
On Mon, May 1, 2017 at 19:36 Howard Lovatt <howard.lovatt@gmail.com> wrote:
Yes, I know the change I suggested involves making generalised existentials. I am suggesting not making *any* changes until such effort is available. I understand that this would be after Swift 4. I think the wait would be worthwhile.

As an aside: Currently one of the big issues with generalised existentials in Swift is with Self (which you can think of as a form of generic argument). Currently:

    protocol Equatable {
        static func ==(lhs: Self, rhs: Self) -> Bool
        ...
    }
    struct Int: Equatable { ... }
    let e1: Equatable = 1
    let e2: Equatable = 2
    if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the same dynamic type

I would replace this with:

    protocol Equatable<T> { // Use T instead of Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable<Int> { ... }
    let e1: Equatable<Int> = 1
    let e2: Equatable<Int> = 2
    if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

As an aside on the aside, even better:

    protocol Equatable<T = Self> { // T defaults to Self
        static func ==(lhs: T, rhs: T) -> Bool
        ...
    }
    struct Int: Equatable { ... } // T is Int, the default is Self
    let e1: Equatable = 1 // T is Int, the default is Self
    let e2: Equatable = 2 // T is Int, the default is Self
    if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

Everything I am suggesting is done in other languages and from my personal experience works out better.

  -- Howard.

On 2 May 2017 at 09:53, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
Howard, take a look at the generics manifesto section on generic protocols:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

It explains very nicely how what you're really asking for is not generic protocols but generalized existentials. This would be nice to have, but it's clearly not happening within the next month and it wouldn't change the solution for filter, for which this proposal is the obvious fix.

On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution <swift-evolution@swift.org> wrote:

review of SE-0174 "Change `filter` to return an associated type"

  • What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always returning an array from collection operations is limiting. However I think this proposal feels like 'papering' over problems rather than fixing the root cause. I think it would be better to reject this and do two more adventurous proposals instead:

  1. Allow protocols to be generic, instead of associated types, so that you can write Sequence<T>
  2. Allow Self to accept a generic argument, so that you can write Self<T>

With these to, admittedly much more major changes, you can then write:

    protocol Sequence<T> {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Sequence<T>
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
    }
    extension RangeReplaceableCollection {
        func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T> {
            var result = Self<T>()
            for element in self {
                if try isIncluded(element) {
                     result.append(element)
                }
            }
           return result
        }
        func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
            var result = Self<M>()
            for element in self {
                try result.append(mapper(element))
            }
           return result
        }
    }

Which I think both reads better and is more powerful since it allows map to be written also.

  • Is the problem being addressed significant enough to warrant a change to Swift?

Yes, return an array is a real pain

  • Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift into a corner were other problems can't be fixed because the underlying, real, problems still remain.

  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the solution I presented above.

  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy to overcome this limitation, and others, of the current library.

-- Howard.

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type" begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager. When replying, please try to keep the proposal link at the top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reply text
Other replies
What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  • What is your evaluation of the proposal?
  • Is the problem being addressed significant enough to warrant a change to Swift?
  • Does this proposal fit well with the feel and direction of Swift?
  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md
Thank you,

-Doug Gregor

Review Manager

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

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

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


(Anders) #17

So a bit of correction: generic protocol had been dismissed in the Generic Manifesto specifically for sequences and collections, because it would permit multiple conformances of a certain type to the same protocol with different types of elements, and it is considered wrong.

`Self` in a protocol refers not to the unbound generic type, but to the specialized one, e.g. `Array<T>` where T is bound, instead of `Array`. For your code snippets to work, the compiler would need to explicitly “unspecialize” the specialised `Self` and parameterise it with a different type. This notion is called higher-kinded types.

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md#higher-kinded-types

For example, using the potential syntax in the manifesto:

   extension RangeReplaceableCollection {
       func filter<Filtered>(_ isIncluded: (Element) -> Bool) -> Filtered where Filtered ~= Self, Filtered.Element == Element
       func map<Mapped>(_ transform: (Element) -> Mapped.Element) -> Mapped where Mapped ~= Self
   }

Let’s say `Self` is `Set<Int>`, the compiler would need to be instructed to “unspecialize” it and parameterise it again, so that it still knows the resulting collection statically. Then at this point, yes, it can be statically dispatched.

But for now, higher-kinded types do not seem to be on the radar at all. So to achieve the same result, there are only two options:

1. Type-erased wrappers, e.g. `AnyCollection<T>`, or generalised existential, e.g. `Collection where .Element == T`. This means dynamic dispatch.
2. Associated type, i.e. the proposal.

Another important constraint you’ve missed is that only `RangeReplaceableCollection` implies the collection can be explicitly constructed. So a default of `[Element]` is necessary.

Perhaps I should rephrase this for clarity:

Another important constraint missed is that `Sequence` and derived protocols do not imply constructibility and manipulability. These capabilities belong to standalone protocols like `RangeReplaceableCollection` and `SetAlgebra`.

So a default of `[Element]` for `Sequence.filter` is inevitable, even with we have higher-kinded types.

···

On 3 May 2017, at 5:32 PM, Anders Ha via swift-evolution <swift-evolution@swift.org> wrote:

Regards
Anders

On 3 May 2017, at 4:57 PM, Howard Lovatt <howard.lovatt@gmail.com> wrote:

@Anders,

I think you can eliminate the dynamic dispatch for a struct. Using the generic parameterised syntax rather than the where clause syntax (because it is more compact and clearer):

   protocol Sequence<T> {
       func filter(_ isIncluded: (T) -> Bool) -> Self<T> // Note: returns Self<T>
       ...
   }
   extension Sequence {
       func filter(_ isIncluded: (T) -> Bool) -> Self<T> { // Note: returns Self<T>
           var result = Self<T>
           for element in self {
               if isIncluded(element) { result.append(element) }
           }
           return result
       }
       ...
   }
   struct Set<T>: Sequence<T> { ... } // Inherits filter from extension

For struct `Set<T>` `Self<T>` is `Set<T>` (obviously, that is what Self means), therefore the compiler can for both code and type checking purposes generate:

   struct Set<T>: Sequence<T> {
       func filter(_ isIncluded: (T) -> Bool) -> Set<T> { // Note: returns Set<T>
           var result = Set<T>
           for element in self {
               if isIncluded(element) { result.append(element) }
           }
           return result
       }
       ...
   }

This is an intermediate step for the compiler since `Set` is still generic, in `T`. When a specific `Set` is instantiated, e.g. `let s = Set<Int>`, the compiler can generate both for code and type checking purposes:

   struct Set<Int>: Sequence<Int> {
       func filter(_ isIncluded: (Int) -> Bool) -> Set<Int> { // Note: returns Set<Int>
           var result = Set<Int>
           for element in self {
               if isIncluded(element) { result.append(element) }
           }
           return result
       }
       ...
   }

When you call `s.filter` there is no dynamic dispatch because `filter` is final within a struct and the compiler also knows that this version of `filter` returns a `Set<Int>` and therefore no dynamic dispatch on the returned value if in a chain of calls either.

Have I made a mistake in the above?

-- Howard.

On 3 May 2017 at 17:27, Anders Ha <hello@andersio.co> wrote:
Returning `Self<T>` requires higher kinded type. Note that parameterized protocols are not the same as higher kinded types, since for the former generic protocol parameters are already bound at conformance of the static `Self` like associated types, while the later is about having a generic static `Self`.

IOW you cannot do `Self<T>` statically without higher kinded type. The best you can get is generalized existential, e.g. `filter` returning a `Collection where .Element == T` or `Collection<T>` if protocols can be parameterized.

The compiler cannot eliminate virtual dispatching for existentials, because this is what existential is by definition — knowing how to manipulate it at static time, but not the type which varies at runtime. All non-class existentials are dispatched through their associated protocol witness tables.

Regards
Anders

On 3 May 2017, at 09:05, Howard Lovatt <howard.lovatt@gmail.com> wrote:

My experience with languages that have generalised existential is that they are superior in many circumstances; not just for collections, e.g. I gave the example of the comparison protocol.

I don't think methods called on a returned generalised existential have to be called via a Vtable. If the return type is Self<T> then the compiler can eliminate the Vtable for selfs that are value types. For selfs that are classes it would still have to use a Vtable though, because classes always use Vtables! In most cases the return type will be Self<T> and in most cases the Self will be a value type, so I would argue that in most cases a Vtable won't be used.

-- Howard.

On 2 May 2017, at 8:57 pm, Anders Ha <hello@andersio.co> wrote:

I would like to add that generalized existential is not really a better solution than letting the collection optionally and statically supply one. It consequentially forces all calls to the filtered collections virtual/dynamic.

Higher kinded type would ideally help, but we all know it is not coming anytime soon, or perhaps ever.

Regards
Anders

On 2 May 2017, at 08:41, Xiaodi Wu via swift-evolution <swift-evolution@swift.org> wrote:

Howard, this is also mentioned in the generics manifesto under "Opening existentials," and it's received plentiful discussion and will surely receive more as these issues become addressed in future proposals. Let's not divert the conversation here about map and filter.
On Mon, May 1, 2017 at 19:36 Howard Lovatt <howard.lovatt@gmail.com> wrote:
Yes, I know the change I suggested involves making generalised existentials. I am suggesting not making *any* changes until such effort is available. I understand that this would be after Swift 4. I think the wait would be worthwhile.

As an aside: Currently one of the big issues with generalised existentials in Swift is with Self (which you can think of as a form of generic argument). Currently:

   protocol Equatable {
       static func ==(lhs: Self, rhs: Self) -> Bool
       ...
   }
   struct Int: Equatable { ... }
   let e1: Equatable = 1
   let e2: Equatable = 2
   if e1 == e2 { ... } // error: e1 and e2 don't necessarily have the same dynamic type

I would replace this with:

   protocol Equatable<T> { // Use T instead of Self
       static func ==(lhs: T, rhs: T) -> Bool
       ...
   }
   struct Int: Equatable<Int> { ... }
   let e1: Equatable<Int> = 1
   let e2: Equatable<Int> = 2
   if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

As an aside on the aside, even better:

   protocol Equatable<T = Self> { // T defaults to Self
       static func ==(lhs: T, rhs: T) -> Bool
       ...
   }
   struct Int: Equatable { ... } // T is Int, the default is Self
   let e1: Equatable = 1 // T is Int, the default is Self
   let e2: Equatable = 2 // T is Int, the default is Self
   if e1 == e2 { ... } // No longer an error since they are both Equatable<Int>

Everything I am suggesting is done in other languages and from my personal experience works out better.

-- Howard.

On 2 May 2017 at 09:53, Xiaodi Wu <xiaodi.wu@gmail.com> wrote:
Howard, take a look at the generics manifesto section on generic protocols:

https://github.com/apple/swift/blob/master/docs/GenericsManifesto.md

It explains very nicely how what you're really asking for is not generic protocols but generalized existentials. This would be nice to have, but it's clearly not happening within the next month and it wouldn't change the solution for filter, for which this proposal is the obvious fix.

On Mon, May 1, 2017 at 18:09 Howard Lovatt via swift-evolution <swift-evolution@swift.org> wrote:

review of SE-0174 "Change `filter` to return an associated type"

  • What is your evaluation of the proposal?

I think a change in this 'area' is valuable because currently always returning an array from collection operations is limiting. However I think this proposal feels like 'papering' over problems rather than fixing the root cause. I think it would be better to reject this and do two more adventurous proposals instead:

1. Allow protocols to be generic, instead of associated types, so that you can write Sequence<T>
2. Allow Self to accept a generic argument, so that you can write Self<T>

With these to, admittedly much more major changes, you can then write:

   protocol Sequence<T> {
       func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Sequence<T>
       func map<M>(_ mapper: (T) throws -> M) rethrows -> Sequence<M>
   }
   extension RangeReplaceableCollection {
       func filter(_ isIncluded: (T) throws -> Bool) rethrows -> Self<T> {
           var result = Self<T>()
           for element in self {
               if try isIncluded(element) {
                    result.append(element)
               }
           }
          return result
       }
       func map<M>(_ mapper: (T) throws -> M) rethrows -> Self<M> {
           var result = Self<M>()
           for element in self {
               try result.append(mapper(element))
           }
          return result
       }
   }

Which I think both reads better and is more powerful since it allows map to be written also.

  • Is the problem being addressed significant enough to warrant a change to Swift?

Yes, return an array is a real pain

  • Does this proposal fit well with the feel and direction of Swift?

Yes and no, really smacks of papering over other flaws. Might box Swift into a corner were other problems can't be fixed because the underlying, real, problems still remain.

  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?

Virtually all other languages I have used, e.g. Java, Scala, use the solution I presented above.

  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?

Have been bitten by this and have written my own collection hierarchy to overcome this limitation, and others, of the current library.

-- Howard.

On 29 Apr 2017, at 10:06 am, Douglas Gregor <dgregor@apple.com> wrote:

Hello Swift community,

The review of SE-0174 "Change `filter` to return an associated type" begins now and runs through May 3, 2017. The proposal is available here:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reviews are an important part of the Swift evolution process. All reviews should be sent to the swift-evolution mailing list at

https://lists.swift.org/mailman/listinfo/swift-evolution
or, if you would like to keep your feedback private, directly to the review manager. When replying, please try to keep the proposal link at the top of the message:

Proposal link:

https://github.com/apple/swift-evolution/blob/master/proposals/0174-filter-range-replaceable.md
Reply text
Other replies
What goes into a review?

The goal of the review process is to improve the proposal under review through constructive criticism and, eventually, determine the direction of Swift. When writing your review, here are some questions you might want to answer in your review:

  • What is your evaluation of the proposal?
  • Is the problem being addressed significant enough to warrant a change to Swift?
  • Does this proposal fit well with the feel and direction of Swift?
  • If you have used other languages or libraries with a similar feature, how do you feel that this proposal compares to those?
  • How much effort did you put into your review? A glance, a quick reading, or an in-depth study?
More information about the Swift evolution process is available at

https://github.com/apple/swift-evolution/blob/master/process.md
Thank you,

-Doug Gregor

Review Manager

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

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

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

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