Reconsidering the (Element -> T?) variant of SequenceType.flatMap


(Andy Matuschak) #1

Hello, all! This SequenceType-implemented flatMap recently caused some confusion on my team:

func flatMap<T>(@noescape transform: (Self.Generator.Element) throws -> T?) rethrows -> [T]

I’m a big fan of this operator in various functional libraries, but I admit I was a bit surprised to see the “flatMap” terminology appear in the Swift stdlib in the first place—its naming is certainly a notch obscure!

From the reactions of teammates in code reviews involving these methods, there was a significant difference in comprehensibility between the Element -> [T] variant and the Element -> T? variant. The former was easily explained by “it’s a map, followed by a flatten,” whereas the same explanation failed in the latter case.

I expect that the inspiration came from Scala, where the equivalent definition has a transformer essentially of type Element -> GeneratorType<T>; separately, their optionals are implicitly convertible to (their equivalent of) GeneratorType. So, in the end, in Scala, you can effectively flatMap with an Element -> T? transformer.

But Optional doesn’t implement GeneratorType, and I’d (weakly) argue that it shouldn’t. And if we think about flatMap in the context of a monadic bind (I do, anyway!), it’s especially surprising that the transformer is operating in a different monadic context (Optional) than the receiver (SequenceType). Unless we made Optional adopt SequenceType, in which case we could consider the bind to be happening in that context.

In conclusion, I argue that this overload is confusing both to folks unfamiliar with FP (because it doesn’t feel like Optionals can be flattened) and to folks familiar with FP (because it implies binding across monadic contexts).

···

~

In terms of what to do instead: I do think that this is a useful method, and I’d like to keep this functionality easily accessible! Two ideas:

1. We expose a separate operator like:

extension SequenceType where Generator.Element: OptionalType {
  func filterNils() -> [Generator.Element.Wrapped]
}

// To deal with limitations on protocol extension type restriction:
protocol OptionalType {
  typealias Wrapped
  func flatMap<Result>(@noescape f: Wrapped -> Result?) -> Result?
}
extension Optional: OptionalType {}

Clients would do myArray.map(optionalReturningTransform).filterNils(). There would be some performance impact from the intermediate array.

2. We give the foo variant a more specific name, e.g. mappedArrayFilteringNils etc. Naming this is tricky (which probably implies it should be decomposed?).


(Lily Ballard) #2

I use that flatMap() variant on sequences very often. I don't think I've
actually _ever_ used the variant that returns [T]. I understand the
monadic argument you're making, but I believe the practical choice here
is to keep this flatMap() variant as-is. Giving it a different name
would I think reduce clarity, since it's conceptually performing the
same operation (e.g. the closure returns some value that is flattened;
whether the values an array or an optional it doesn't matter), and
adding .filterNils() would not only reduce clarity but would, as you
said, have a performance impact.

Personally, I'd be in favor of making Optional conform to SequenceType.
I've filed a radar on it before, and I seem to recall a message
(probably to this list) yesterday suggesting the exact same thing. It
may even want to go ahead and adopt CollectionType too, completely
replacing CollectionOfOne (though the ability to subscript an optional
may be confusing, so it may be better to just adopt SequenceType and
keep CollectionOfOne around for CollectionType use-cases).

-Kevin Ballard

···

On Fri, Dec 4, 2015, at 03:26 PM, Andy Matuschak wrote:

Hello, all! This SequenceType-implemented flatMap recently caused some
confusion on my team:

func flatMap<T>(@noescape transform: (Self.Generator.Element) throws
-> T?) rethrows -> [T]

I’m a big fan of this operator in various functional libraries, but I
admit I was a bit surprised to see the “flatMap” terminology appear in
the Swift stdlib in the first place—its naming is certainly a notch
obscure!

From the reactions of teammates in code reviews involving these
methods, there was a significant difference in comprehensibility
between the Element -> [T] variant and the Element -> T? variant. The
former was easily explained by “it’s a map, followed by a flatten,”
whereas the same explanation failed in the latter case.

I expect that the inspiration came from Scala, where the equivalent
definition has a transformer essentially of type Element ->
GeneratorType<T>; separately, their optionals are implicitly
convertible to (their equivalent of) GeneratorType. So, in the end, in
Scala, you can effectively flatMap with an Element -> T? transformer.

But Optional doesn’t implement GeneratorType, and I’d (weakly) argue
that it shouldn’t. And if we think about flatMap in the context of a
monadic bind (I do, anyway!), it’s especially surprising that the
transformer is operating in a different monadic context (Optional)
than the receiver (SequenceType). Unless we made Optional adopt
SequenceType, in which case we could consider the bind to be happening
in that context.

In conclusion, I argue that this overload is confusing both to folks
unfamiliar with FP (because it doesn’t feel like Optionals can be
flattened) and to folks familiar with FP (because it implies binding
across monadic contexts).

~

In terms of what to do instead: I do think that this is a useful
method, and I’d like to keep this functionality easily accessible!
Two ideas:

1. We expose a separate operator like:

extension SequenceType where Generator.Element: OptionalType { func
filterNils() -> [Generator.Element.Wrapped] }

// To deal with limitations on protocol extension type restriction:
protocol OptionalType { typealias Wrapped func
flatMap<Result>(@noescape f: Wrapped -> Result?) -> Result? }
extension Optional: OptionalType {}

Clients would do myArray.map(optionalReturningTransform).filterNils().
There would be some performance impact from the intermediate array.

2. We give the foo variant a more specific name, e.g.
   mappedArrayFilteringNils etc. Naming this is tricky (which probably
   implies it should be decomposed?).

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


(Dmitri Gribenko) #3

This would be an interesting direction, but we have discussed it a
long time ago, and found an issue in the way it would interact with
implicit promotions to optionals. Basically, in a call to a function
accepting a Sequence, one would be able to write any non-sequence,
non-optional value, that would be implicitly promoted to optional, and
thus eligible to be passed as a Sequence. This is the only argument
for not adding this conformance that I know of, but it is a show
stopper unfortunately.

Dmitri

···

On Fri, Dec 4, 2015 at 3:34 PM, Kevin Ballard <kevin@sb.org> wrote:

Personally, I'd be in favor of making Optional conform to SequenceType. I've filed a radar on it before, and I seem to recall a message (probably to this list) yesterday suggesting the exact same thing.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Lily Ballard) #4

Can implicit optional promotion not be redefined to only occur when the
destination type is explicitly optional (as opposed to being generic)?
The problem you describe sounds like it could affect third-party code as
well if anyone has a reason to declare a protocol and extend Optional to
conform to it.

-Kevin Ballard

···

On Fri, Dec 4, 2015, at 03:37 PM, Dmitri Gribenko wrote:

On Fri, Dec 4, 2015 at 3:34 PM, Kevin Ballard <kevin@sb.org> wrote:
> Personally, I'd be in favor of making Optional conform to SequenceType. I've filed a radar on it before, and I seem to recall a message (probably to this list) yesterday suggesting the exact same thing.

This would be an interesting direction, but we have discussed it a
long time ago, and found an issue in the way it would interact with
implicit promotions to optionals. Basically, in a call to a function
accepting a Sequence, one would be able to write any non-sequence,
non-optional value, that would be implicitly promoted to optional, and
thus eligible to be passed as a Sequence. This is the only argument
for not adding this conformance that I know of, but it is a show
stopper unfortunately.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Maxwell Swadling) #5

I can not reproduce this behaviour. I'm not sure which version of the compiler had this behaviour.

···

On 4 Dec 2015, at 3:37 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Fri, Dec 4, 2015 at 3:34 PM, Kevin Ballard <kevin@sb.org> wrote:

Personally, I'd be in favor of making Optional conform to SequenceType. I've filed a radar on it before, and I seem to recall a message (probably to this list) yesterday suggesting the exact same thing.

This would be an interesting direction, but we have discussed it a
long time ago, and found an issue in the way it would interact with
implicit promotions to optionals. Basically, in a call to a function
accepting a Sequence, one would be able to write any non-sequence,
non-optional value, that would be implicitly promoted to optional, and
thus eligible to be passed as a Sequence. This is the only argument
for not adding this conformance that I know of, but it is a show
stopper unfortunately.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dmitri Gribenko) #6

It can be created by third-party code, but many other problems can be
created by third-party code, too (like making String conform to
IntegerLiteralConvertible), so it is not a concern for me in that
sense.

Dmitri

···

On Fri, Dec 4, 2015 at 3:52 PM, Kevin Ballard <kevin@sb.org> wrote:

Can implicit optional promotion not be redefined to only occur when the
destination type is explicitly optional (as opposed to being generic)?
The problem you describe sounds like it could affect third-party code as
well if anyone has a reason to declare a protocol and extend Optional to
conform to it.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Dmitri Gribenko) #7

The fact that the compiler does not do it means it is not implementing
the language model. The compiler is not the source of truth about the
language, or we wouldn't have any bugs -- they all would be features.

Dmitri

···

On Fri, Dec 4, 2015 at 4:00 PM, Maxwell Swadling <maxs@apple.com> wrote:

On 4 Dec 2015, at 3:37 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Fri, Dec 4, 2015 at 3:34 PM, Kevin Ballard <kevin@sb.org> wrote:

Personally, I'd be in favor of making Optional conform to SequenceType. I've filed a radar on it before, and I seem to recall a message (probably to this list) yesterday suggesting the exact same thing.

This would be an interesting direction, but we have discussed it a
long time ago, and found an issue in the way it would interact with
implicit promotions to optionals. Basically, in a call to a function
accepting a Sequence, one would be able to write any non-sequence,
non-optional value, that would be implicitly promoted to optional, and
thus eligible to be passed as a Sequence. This is the only argument
for not adding this conformance that I know of, but it is a show
stopper unfortunately.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

I can not reproduce this behaviour. I'm not sure which version of the compiler had this behaviour.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Maxwell Swadling) #8

I think you were observing a bug at the time and it is safe to say it isn't part of the language. Otherwise programs like this would be accepted:

func f<a: CustomDebugStringConvertible>(x: a) {
    print(x.debugDescription)
}
f(1)

or

1.debugDescription

···

On 4 Dec 2015, at 4:01 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Fri, Dec 4, 2015 at 4:00 PM, Maxwell Swadling <maxs@apple.com> wrote:

On 4 Dec 2015, at 3:37 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:

On Fri, Dec 4, 2015 at 3:34 PM, Kevin Ballard <kevin@sb.org> wrote:

Personally, I'd be in favor of making Optional conform to SequenceType. I've filed a radar on it before, and I seem to recall a message (probably to this list) yesterday suggesting the exact same thing.

This would be an interesting direction, but we have discussed it a
long time ago, and found an issue in the way it would interact with
implicit promotions to optionals. Basically, in a call to a function
accepting a Sequence, one would be able to write any non-sequence,
non-optional value, that would be implicitly promoted to optional, and
thus eligible to be passed as a Sequence. This is the only argument
for not adding this conformance that I know of, but it is a show
stopper unfortunately.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

I can not reproduce this behaviour. I'm not sure which version of the compiler had this behaviour.

The fact that the compiler does not do it means it is not implementing
the language model. The compiler is not the source of truth about the
language, or we wouldn't have any bugs -- they all would be features.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/