[Review] Add a Lazy flatMap for Sequences of Optionals


(Douglas Gregor) #1

Hello Swift community,

The review of “Add a Lazy flatMap for Sequences of Optionals” begins now and runs through Thursday, December 17th. The proposal is available here:

  https://github.com/apple/swift-evolution/blob/master/proposals/0008-lazy-flatmap-for-optionals.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.

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 you 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

  Cheers,
  Doug Gregor
  Review Manager


(Dave Abrahams) #2

First, I’d like to thank Oisin <https://github.com/oisdk> for his proposal. It’s great to see people filling in gaps.

  * What is your evaluation of the proposal?

The basic idea is solid and obviously appropriate. I have some quibbles with the proposed solution.

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

Yes; it’s a non-uniformity, nonuniformities create complexity for users.

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

Yes.

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

A quick reading, but I’m deeply familiar with the domain, having written the lazy facilities we have in the stdlib.

I don’t see why the proposal states, “Optional probably wouldn't have a BidirectionalIndexType“. It seems to me that as a collection, an optional’s index should be random access, just like CollectionOfOne’s.

I’d like to suggest a different implementation approach that not only handles the bidirectional issue but also probably reduces the amount of code involved: create a generic CollectionOfZeroOrOne<T> that wraps a T?, and implement the x.flatmap(f) where f returns an optional as x.flatmap { CollectionOfZeroOrOne(f($0)) }

What do you think?

-Dave


(Dmitri Gribenko) #3

What's the advantage? Why would we want to have a type that is isomorphic
to Optional, except that conforms to CollectionType?

Dmitri

···

On Tue, Dec 15, 2015 at 6:29 PM, Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

I’d like to suggest a different implementation approach that not only
handles the bidirectional issue but also probably reduces the amount of
code involved: create a generic CollectionOfZeroOrOne<T> that wraps a T?,
and implement the x.flatmap(f) where f returns an optional as x.flatmap {
CollectionOfZeroOrOne(f($0)) }

--
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>*/


(Donnacha Oisín Kidney) #4

Now that I think about it, of course CollectionOfZeroOrOne would (or Optional) have a random access index. I’ll update the proposal to include that.

I really like the CollectionOfZeroOrOne solution. The semantics and types certainly make more sense. I’m not sure that it reduces the amount of code, though: the three extensions are still needed, plus an extra struct. (I suppose that’s not counting the extra version of LazyFilterCollection. Am I right in saying that that is intended to be added?)

Here’s what I have for the collection (I tried to mimic the standard library’s CollectionOfOne):

public struct CollectionOfZeroOrOne<Element> : CollectionType {

  public typealias Index = Bit
  
  public init(_ element: Element?) {
    self.element = element
  }
  
  public var startIndex: Index {
    return .Zero
  }
  
  public var endIndex: Index {
    switch element {
    case .Some: return .One
    case .None: return .Zero
    }
  }
  
  public func generate() -> GeneratorOfOne<Element> {
    return GeneratorOfOne(element)
  }
  
  public subscript(position: Index) -> Element {
    if case .Zero = position, let result = element {
      return result
    } else {
      fatalError("Index out of range")
    }
  }
  
  let element: Element?
}

Does that seem reasonable?

···

On 16 Dec 2015, at 02:29, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

First, I’d like to thank Oisin <https://github.com/oisdk> for his proposal. It’s great to see people filling in gaps.

  * What is your evaluation of the proposal?

The basic idea is solid and obviously appropriate. I have some quibbles with the proposed solution.

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

Yes; it’s a non-uniformity, nonuniformities create complexity for users.

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

Yes.

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

A quick reading, but I’m deeply familiar with the domain, having written the lazy facilities we have in the stdlib.

I don’t see why the proposal states, “Optional probably wouldn't have a BidirectionalIndexType“. It seems to me that as a collection, an optional’s index should be random access, just like CollectionOfOne’s.

I’d like to suggest a different implementation approach that not only handles the bidirectional issue but also probably reduces the amount of code involved: create a generic CollectionOfZeroOrOne<T> that wraps a T?, and implement the x.flatmap(f) where f returns an optional as x.flatmap { CollectionOfZeroOrOne(f($0)) }

What do you think?

-Dave

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


(Rob Mayoff) #5

What's the advantage? Why would we want to have a type that is isomorphic
to Optional, except that conforms to CollectionType?

My question (apologies if it has been answered already) is: Why isn't
Optional a CollectionType, like it is in Scala?


(Dmitri Gribenko) #6

It looks reasonable, but I don't understand why adding
CollectionOfZeroOrOne improves the API. Dave?

Dmitri

···

On Wed, Dec 16, 2015 at 7:10 AM, Donnacha Oisín Kidney < swift-evolution@swift.org> wrote:

Now that I think about it, of course CollectionOfZeroOrOne would (or
Optional) have a random access index. I’ll update the proposal to include
that.

I really like the CollectionOfZeroOrOne solution. The semantics and types
certainly make more sense. I’m not sure that it reduces the amount of code,
though: the three extensions are still needed, plus an extra struct. (I
suppose that’s not counting the extra version of LazyFilterCollection. Am
I right in saying that that is intended to be added?)

Here’s what I have for the collection (I tried to mimic the standard
library’s CollectionOfOne):

public struct CollectionOfZeroOrOne<Element> : CollectionType {

[...]
}

Does that seem reasonable?

--
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>*/


(Dave Abrahams) #7

Now that I think about it, of course CollectionOfZeroOrOne would (or Optional) have a random access index. I’ll update the proposal to include that.

I really like the CollectionOfZeroOrOne solution. The semantics and types certainly make more sense. I’m not sure that it reduces the amount of code, though: the three extensions are still needed, plus an extra struct. (I suppose that’s not counting the extra version of LazyFilterCollection. Am I right in saying that that is intended to be added?)

I'm not sure I understand why we need another version of LazyFilterCollection. Can you explain?

Here’s what I have for the collection (I tried to mimic the standard library’s CollectionOfOne):

public struct CollectionOfZeroOrOne<Element> : CollectionType {

[...]
}

Does that seem reasonable?

It looks reasonable, but I don't understand why adding CollectionOfZeroOrOne improves the API. Dave?

It doesn't. I think it improves code reuse, and gives people an adapter to use when they want to pass an Optional where a Collection or Sequence is required.

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 <mailto:gribozavr@gmail.com>>*/

-Dave

···

On Dec 16, 2015, at 10:15 AM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Wed, Dec 16, 2015 at 7:10 AM, Donnacha Oisín Kidney <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:


(Donnacha Oisín Kidney) #8

Oops, sorry, I wasn’t very clear. I was just trying to compare the amount of code reuse and new types between the two versions. CollectionOfZeroOrOne would need three extensions (SequenceType, CollectionType BidirectionalIndexType as well as the extra struct itself. The filter version doesn’t really need a new struct, but to have a bidirectional version, you would need a LazyFilterBidirectionalCollection which doesn’t currently exist. I had thought that that was something which may be added anyway, though.

Oisin.

···

On 16 Dec 2015, at 19:08, Dave Abrahams <dabrahams@apple.com> wrote:

On Dec 16, 2015, at 10:15 AM, Dmitri Gribenko <gribozavr@gmail.com <mailto:gribozavr@gmail.com>> wrote:

On Wed, Dec 16, 2015 at 7:10 AM, Donnacha Oisín Kidney <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Now that I think about it, of course CollectionOfZeroOrOne would (or Optional) have a random access index. I’ll update the proposal to include that.

I really like the CollectionOfZeroOrOne solution. The semantics and types certainly make more sense. I’m not sure that it reduces the amount of code, though: the three extensions are still needed, plus an extra struct. (I suppose that’s not counting the extra version of LazyFilterCollection. Am I right in saying that that is intended to be added?)

I'm not sure I understand why we need another version of LazyFilterCollection. Can you explain?

Here’s what I have for the collection (I tried to mimic the standard library’s CollectionOfOne):

public struct CollectionOfZeroOrOne<Element> : CollectionType {

[...]
}

Does that seem reasonable?

It looks reasonable, but I don't understand why adding CollectionOfZeroOrOne improves the API. Dave?

It doesn't. I think it improves code reuse, and gives people an adapter to use when they want to pass an Optional where a Collection or Sequence is required.

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 <mailto:gribozavr@gmail.com>>*/

-Dave


(Dave Abrahams) #9

I don't remember the rationale, but it used to be that way <https://github.com/apple/swift/commit/fad874708e05cff56aec5587a4b0f49cdadc6d11> and during the run-up to the Swift 1 release IIRC several members of the Swift team objected to it. That's the answer to Dmitri's question: I have considered that to be off the table, but we could revisit it.

One cute effect, which might be too cute for some, is that

  if let x = y { ... }

becomes equivalent to

  for x in y { ... }

when y is an optional.

-Dave

···

On Dec 15, 2015, at 7:21 PM, Rob Mayoff via swift-evolution <swift-evolution@swift.org> wrote:

Dmitri wrote:
What's the advantage? Why would we want to have a type that is isomorphic to Optional, except that conforms to CollectionType?

My question (apologies if it has been answered already) is: Why isn't Optional a CollectionType, like it is in Scala?


(Dave Abrahams) #10

OK, maybe I need to think about this more carefully. Sorry if I drew incorrect/hasty conclusions.

···

On Dec 16, 2015, at 11:35 AM, Donnacha Oisín Kidney <oisin.kidney@gmail.com> wrote:

Oops, sorry, I wasn’t very clear. I was just trying to compare the amount of code reuse and new types between the two versions. CollectionOfZeroOrOne would need three extensions (SequenceType, CollectionType BidirectionalIndexType as well as the extra struct itself. The filter version doesn’t really need a new struct, but to have a bidirectional version, you would need a LazyFilterBidirectionalCollection which doesn’t currently exist. I had thought that that was something which may be added anyway, though.

Oisin.

On 16 Dec 2015, at 19:08, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:

On Dec 16, 2015, at 10:15 AM, Dmitri Gribenko <gribozavr@gmail.com <mailto:gribozavr@gmail.com>> wrote:

On Wed, Dec 16, 2015 at 7:10 AM, Donnacha Oisín Kidney <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Now that I think about it, of course CollectionOfZeroOrOne would (or Optional) have a random access index. I’ll update the proposal to include that.

I really like the CollectionOfZeroOrOne solution. The semantics and types certainly make more sense. I’m not sure that it reduces the amount of code, though: the three extensions are still needed, plus an extra struct. (I suppose that’s not counting the extra version of LazyFilterCollection. Am I right in saying that that is intended to be added?)

I'm not sure I understand why we need another version of LazyFilterCollection. Can you explain?

Here’s what I have for the collection (I tried to mimic the standard library’s CollectionOfOne):

public struct CollectionOfZeroOrOne<Element> : CollectionType {

[...]
}

Does that seem reasonable?

It looks reasonable, but I don't understand why adding CollectionOfZeroOrOne improves the API. Dave?

It doesn't. I think it improves code reuse, and gives people an adapter to use when they want to pass an Optional where a Collection or Sequence is required.

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 <mailto:gribozavr@gmail.com>>*/

-Dave

-Dave


(Max Moiseev) #11

FWIW: Strictly speaking Option in Scala is not a collection. It happens to have all the methods that make it look like one and also an implicit conversion that creates a List of zero or one element. Which is kind of what Dave suggests.

···

On Dec 15, 2015, at 7:21 PM, Rob Mayoff via swift-evolution <swift-evolution@swift.org> wrote:

What's the advantage? Why would we want to have a type that is isomorphic to Optional, except that conforms to CollectionType?

My question (apologies if it has been answered already) is: Why isn't Optional a CollectionType, like it is in Scala?

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


(Dave Abrahams) #12

Having discussed it with the team, I withdraw my objection to the implementation strategy. CollectionOfZeroOrOne is an orthogonal capability that should be handled separately, if at all.

So, +1 for acceptance, provided there are tests.

···

On Dec 16, 2015, at 12:14 PM, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

OK, maybe I need to think about this more carefully. Sorry if I drew incorrect/hasty conclusions.

On Dec 16, 2015, at 11:35 AM, Donnacha Oisín Kidney <oisin.kidney@gmail.com <mailto:oisin.kidney@gmail.com>> wrote:

Oops, sorry, I wasn’t very clear. I was just trying to compare the amount of code reuse and new types between the two versions. CollectionOfZeroOrOne would need three extensions (SequenceType, CollectionType BidirectionalIndexType as well as the extra struct itself. The filter version doesn’t really need a new struct, but to have a bidirectional version, you would need a LazyFilterBidirectionalCollection which doesn’t currently exist. I had thought that that was something which may be added anyway, though.

Oisin.

On 16 Dec 2015, at 19:08, Dave Abrahams <dabrahams@apple.com <mailto:dabrahams@apple.com>> wrote:

On Dec 16, 2015, at 10:15 AM, Dmitri Gribenko <gribozavr@gmail.com <mailto:gribozavr@gmail.com>> wrote:

On Wed, Dec 16, 2015 at 7:10 AM, Donnacha Oisín Kidney <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Now that I think about it, of course CollectionOfZeroOrOne would (or Optional) have a random access index. I’ll update the proposal to include that.

I really like the CollectionOfZeroOrOne solution. The semantics and types certainly make more sense. I’m not sure that it reduces the amount of code, though: the three extensions are still needed, plus an extra struct. (I suppose that’s not counting the extra version of LazyFilterCollection. Am I right in saying that that is intended to be added?)

I'm not sure I understand why we need another version of LazyFilterCollection. Can you explain?

Here’s what I have for the collection (I tried to mimic the standard library’s CollectionOfOne):

public struct CollectionOfZeroOrOne<Element> : CollectionType {

[...]
}

Does that seem reasonable?

It looks reasonable, but I don't understand why adding CollectionOfZeroOrOne improves the API. Dave?

It doesn't. I think it improves code reuse, and gives people an adapter to use when they want to pass an Optional where a Collection or Sequence is required.

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 <mailto:gribozavr@gmail.com>>*/

-Dave

-Dave

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

-Dave


(Jordan Rose) #13

IIRC we made it a CollectionType purely so we could use "for x in y" while "if let x = y" was being implemented. We didn't actually consider it properly.

Dmitri has mentioned at times that he's concerned about the implicit conversion to Optional kicking in when the contextual type is "T: CollectionType", but I don't think that would actually happen. We don't try random implicit conversions, only the ones that there's context for. But someone would need to verify that.

Jordan

···

On Dec 16, 2015, at 0:03 , Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

On Dec 15, 2015, at 7:21 PM, Rob Mayoff via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Dmitri wrote:
What's the advantage? Why would we want to have a type that is isomorphic to Optional, except that conforms to CollectionType?

My question (apologies if it has been answered already) is: Why isn't Optional a CollectionType, like it is in Scala?

I don't remember the rationale, but it used to be that way <https://github.com/apple/swift/commit/fad874708e05cff56aec5587a4b0f49cdadc6d11> and during the run-up to the Swift 1 release IIRC several members of the Swift team objected to it. That's the answer to Dmitri's question: I have considered that to be off the table, but we could revisit it.

One cute effect, which might be too cute for some, is that

  if let x = y { ... }

becomes equivalent to

  for x in y { ... }

when y is an optional.


(Lily Ballard) #14

I've stated in the past that I'd like to see Optional conform to
SequenceType. It may as well conform to CollectionType too. The only
real drawback I'm aware of is the addition of extra methods/properties
on Optional, which shouldn't actually be a problem, it just seems a
little noisy.

Incidentally, pre-1.0 Rust used to actually have a fair amount of code
that used a for-loop to iterate an Option. The Option type still is
iterable, but the introduction of `if let` into Rust served to replace
the existing uses of the for loop.

In any case, I'm broadly in favor of supporting lazy.flatMap. I'm
concerned about the specific implementation in the proposal because
LazyMapSequence<LazyFilterSequence<LazyMapSequence<Elements, T?>>, T> is
kind of a ridiculous type to be getting back from a single call to
flatMap(). I'm most in favor of making Optional conform to
CollectionType and using that to simply flatMap; barring that, the
CollectionOfZeroOrOne idea looks promising.

-Kevin Ballard

···

On Wed, Dec 16, 2015, at 12:03 AM, Dave Abrahams via swift-evolution wrote:

On Dec 15, 2015, at 7:21 PM, Rob Mayoff via swift-evolution <swift-
evolution@swift.org> wrote: Dmitri wrote:

What's the advantage? Why would we want to have a type that is
isomorphic to Optional, except that conforms to CollectionType?

My question (apologies if it has been answered already) is: Why isn't
Optional a CollectionType, like it is in Scala?

I don't remember the rationale, but it used to be that way[1] and
during the run-up to the Swift 1 release IIRC several members of the
Swift team objected to it. That's the answer to Dmitri's question: I
have considered that to be off the table, but we could revisit it.

One cute effect, which might be too cute for some, is that

if let x = y { ... }

becomes equivalent to

for x in y { ... }

when y is an optional.

-Dave

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

Links:

  1. https://github.com/apple/swift/commit/fad874708e05cff56aec5587a4b0f49cdadc6d11


(Jordan Rose) #15

After thinking about it for a bit, I'm against Optional conforming to CollectionType specifically because of those extra members on Optional. Quite a few of the operations on general SequenceTypes and CollectionTypes just don't make sense:

- elementsEqual/lexicographicalCompare
- dropFirst/Last
- joinWithSeparator
- min/maxElement
- reduce
- partition/sort
- split
- startsWith

It's not that CollectionOfZeroOrOne isn't sometimes useful; it's that users of Optional shouldn't be confronted with these useless APIs. Things like Array.init and Set.init that take sequences also feel weird to use with Optional.

This clicked with me after the discussion about Optional<Void> and Bool: just because two types are isomorphic (in the sense of having a bijection, i.e. value-preserving transformations in both directions) doesn't mean they're the same, or should be the same. This is similar to how implementing all the members of a protocol doesn't automatically mean you conform to the protocol; the protocol has semantic requirements too.

Jordan

···

On Dec 17, 2015, at 0:16 , Kevin Ballard via swift-evolution <swift-evolution@swift.org> wrote:

I've stated in the past that I'd like to see Optional conform to SequenceType. It may as well conform to CollectionType too. The only real drawback I'm aware of is the addition of extra methods/properties on Optional, which shouldn't actually be a problem, it just seems a little noisy.

Incidentally, pre-1.0 Rust used to actually have a fair amount of code that used a for-loop to iterate an Option. The Option type still is iterable, but the introduction of `if let` into Rust served to replace the existing uses of the for loop.

In any case, I'm broadly in favor of supporting lazy.flatMap. I'm concerned about the specific implementation in the proposal because LazyMapSequence<LazyFilterSequence<LazyMapSequence<Elements, T?>>, T> is kind of a ridiculous type to be getting back from a single call to flatMap(). I'm most in favor of making Optional conform to CollectionType and using that to simply flatMap; barring that, the CollectionOfZeroOrOne idea looks promising.

-Kevin Ballard

On Wed, Dec 16, 2015, at 12:03 AM, Dave Abrahams via swift-evolution wrote:

On Dec 15, 2015, at 7:21 PM, Rob Mayoff via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:
Dmitri wrote:

What's the advantage? Why would we want to have a type that is isomorphic to Optional, except that conforms to CollectionType?

My question (apologies if it has been answered already) is: Why isn't Optional a CollectionType, like it is in Scala?

I don't remember the rationale, but it used to be that way <https://github.com/apple/swift/commit/fad874708e05cff56aec5587a4b0f49cdadc6d11> and during the run-up to the Swift 1 release IIRC several members of the Swift team objected to it. That's the answer to Dmitri's question: I have considered that to be off the table, but we could revisit it.

One cute effect, which might be too cute for some, is that

  if let x = y { ... }

becomes equivalent to

  for x in y { ... }

when y is an optional.

-Dave

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto: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