# Lazy flatMap for Optionals

**URL:** <https://forums.swift.org/t/lazy-flatmap-for-optionals/127>\
**Category:** Discussion\
**Created:** [December 4, 2015, 10:38pm UTC](https://forums.swift.org/t/lazy-flatmap-for-optionals/127 "2015-12-04T22:38:44Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Donnacha\_Oisin\_Kidne](https://avatars.discourse-cdn.com/v4/letter/d/eada6e/32.png) [@Donnacha\_Oisin\_Kidne](https://forums.swift.org/u/Donnacha_Oisin_Kidne)\
**Post date:** [December 4, 2015, 10:38pm UTC](https://forums.swift.org/t/lazy-flatmap-for-optionals/127/1 "2015-12-04T22:38:44Z")

</div>

Currently, several of the methods on SequenceType in the standard library have lazy variants. flatMap, though, (seems) to have a version missing: while there’s a lazy version for nested sequences, there’s no lazy version for sequences of Optionals. Is there maybe a reason for this that I haven’t thought of? At any rate, here’s what I had in mind:

public struct FlatMapOptionalGenerator\<G: GeneratorType, Element\>: GeneratorType {  
&nbsp;&nbsp;private let f: G.Element -\> Element?  
&nbsp;&nbsp;private var g: G  
&nbsp;&nbsp;public mutating func next() -\> Element? {  
&nbsp;&nbsp;&nbsp;&nbsp;while let x = g.next() {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if let y = f(x) {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return y  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;return nil  
&nbsp;&nbsp;}  
}

public struct FlatMapOptionalSequence\<S: LazySequenceType, Element\>: LazySequenceType {  
&nbsp;&nbsp;private let f: S.Generator.Element -\> Element?  
&nbsp;&nbsp;private let s: S  
&nbsp;&nbsp;public func generate() -\> FlatMapOptionalGenerator\<S.Generator, Element\> {  
&nbsp;&nbsp;&nbsp;&nbsp;return FlatMapOptionalGenerator(f: f, g: s.generate())  
&nbsp;&nbsp;}  
}

extension LazySequenceType {  
&nbsp;&nbsp;public func flatMap\<T\>(transform: Generator.Element -\> T?) -\> FlatMapOptionalSequence\<Self, T\> {  
&nbsp;&nbsp;&nbsp;&nbsp;return FlatMapOptionalSequence(f: transform, s: self)  
&nbsp;&nbsp;}  
}

Does this seem like a good idea?

Oisin.

---

<div class="post-metadata">

**Author:** ![gribozavr](https://avatars.discourse-cdn.com/v4/letter/g/65b543/32.png) [@gribozavr](https://forums.swift.org/u/gribozavr)\
**Post date:** [December 5, 2015, 7:54am UTC](https://forums.swift.org/t/lazy-flatmap-for-optionals/127/2 "2015-12-05T07:54:25Z")

</div>

Hi Oisin,

This is just an omission. Please submit a formal proposal as a pull  
request to the swift-evolution repository.

Dmitri

> **···**
>
> On Fri, Dec 4, 2015 at 2:38 PM, Donnacha Oisín Kidney \< oisin.kidney@gmail.com\> wrote:
> 
> > Currently, several of the methods on SequenceType in the standard library  
> > have lazy variants. flatMap, though, (seems) to have a version missing:  
> > while there’s a lazy version for nested sequences, there’s no lazy version  
> > for sequences of Optionals. Is there maybe a reason for this that I  
> > haven’t thought of? At any rate, here’s what I had in mind:
> > 
> > public struct FlatMapOptionalGenerator\<G: GeneratorType, Element\>:  
> > GeneratorType {  
> > &nbsp;&nbsp;private let f: G.Element -\> Element?  
> > &nbsp;&nbsp;private var g: G  
> > &nbsp;&nbsp;public mutating func next() -\> Element? {  
> > &nbsp;&nbsp;&nbsp;&nbsp;while let x = g.next() {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if let y = f(x) {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return y  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;&nbsp;&nbsp;return nil  
> > &nbsp;&nbsp;}  
> > }
> > 
> > public struct FlatMapOptionalSequence\<S: LazySequenceType, Element\>:  
> > LazySequenceType {  
> > &nbsp;&nbsp;private let f: S.Generator.Element -\> Element?  
> > &nbsp;&nbsp;private let s: S  
> > &nbsp;&nbsp;public func generate() -\> FlatMapOptionalGenerator\<S.Generator, Element\>  
> > {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return FlatMapOptionalGenerator(f: f, g: s.generate())  
> > &nbsp;&nbsp;}  
> > }
> > 
> > extension LazySequenceType {  
> > &nbsp;&nbsp;public func flatMap\<T\>(transform: Generator.Element -\> T?) -\>  
> > FlatMapOptionalSequence\<Self, T\> {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return FlatMapOptionalSequence(f: transform, s: self)  
> > &nbsp;&nbsp;}  
> > }
> > 
> > Does this seem like a good idea?
> 
> --  
> 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\>\*/

---

<div class="post-metadata">

**Author:** ![gribozavr](https://avatars.discourse-cdn.com/v4/letter/g/65b543/32.png) [@gribozavr](https://forums.swift.org/u/gribozavr)\
**Post date:** [December 6, 2015, 9:11am UTC](https://forums.swift.org/t/lazy-flatmap-for-optionals/127/3 "2015-12-06T09:11:19Z")

</div>

Hi,

Thank you for the proposal.

Defining only one overload would cause the collection-ness of the input to  
be lost. Please take a look at the current flatMap() overloads in  
stdlib/public/core/FlatMap.swift: there's one in LazySequenceType, another  
one in LazyCollectionType, and one more in LazyCollectionType with  
bidirectional indices.

I'm also not a fan of introducing a specialized result type for this  
operation: given that we need three overloads, this approach would add six  
more types to the library (three sequences and three generators). Current  
flatMap() overloads compose existing types, but they rely on intermediate  
data structure being a sequence or a collection. Optional is not a  
sequence, so that exact approach won't work here. Can you think of another  
way we could combine existing types to express the result of this operation?

Dmitri

> **···**
>
> On Fri, Dec 4, 2015 at 2:38 PM, Donnacha Oisín Kidney \< oisin.kidney@gmail.com\> wrote:
> 
> > Currently, several of the methods on SequenceType in the standard library  
> > have lazy variants. flatMap, though, (seems) to have a version missing:  
> > while there’s a lazy version for nested sequences, there’s no lazy version  
> > for sequences of Optionals. Is there maybe a reason for this that I  
> > haven’t thought of? At any rate, here’s what I had in mind:
> > 
> > public struct FlatMapOptionalGenerator\<G: GeneratorType, Element\>:  
> > GeneratorType {  
> > &nbsp;&nbsp;private let f: G.Element -\> Element?  
> > &nbsp;&nbsp;private var g: G  
> > &nbsp;&nbsp;public mutating func next() -\> Element? {  
> > &nbsp;&nbsp;&nbsp;&nbsp;while let x = g.next() {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if let y = f(x) {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return y  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;&nbsp;&nbsp;return nil  
> > &nbsp;&nbsp;}  
> > }
> > 
> > public struct FlatMapOptionalSequence\<S: LazySequenceType, Element\>:  
> > LazySequenceType {  
> > &nbsp;&nbsp;private let f: S.Generator.Element -\> Element?  
> > &nbsp;&nbsp;private let s: S  
> > &nbsp;&nbsp;public func generate() -\> FlatMapOptionalGenerator\<S.Generator, Element\>  
> > {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return FlatMapOptionalGenerator(f: f, g: s.generate())  
> > &nbsp;&nbsp;}  
> > }
> > 
> > extension LazySequenceType {  
> > &nbsp;&nbsp;public func flatMap\<T\>(transform: Generator.Element -\> T?) -\>  
> > FlatMapOptionalSequence\<Self, T\> {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return FlatMapOptionalSequence(f: transform, s: self)  
> > &nbsp;&nbsp;}  
> > }
> 
> --  
> 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\>\*/

---

<div class="post-metadata">

**Author:** ![Donnacha\_Oisin\_Kidne](https://avatars.discourse-cdn.com/v4/letter/d/eada6e/32.png) [@Donnacha\_Oisin\_Kidne](https://forums.swift.org/u/Donnacha_Oisin_Kidne)\
**Post date:** [December 6, 2015, 4:06pm UTC](https://forums.swift.org/t/lazy-flatmap-for-optionals/127/4 "2015-12-06T16:06:27Z")

</div>

(forgot to cc the mailing list)

You can define it in terms of a map-filter-map chain, like this:

extension LazySequenceType {  
&nbsp;&nbsp;  
&nbsp;&nbsp;@warn\_unused\_result  
&nbsp;&nbsp;public func flatMap\<T\>(transform: Elements.Generator.Element -\> T?)  
&nbsp;&nbsp;&nbsp;&nbsp;-\> LazyMapSequence\<LazyFilterSequence\<LazyMapSequence\<Elements, T?\>\>, T\> {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return self  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.map(transform)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.filter { opt in opt != nil }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.map { notNil in notNil! }  
&nbsp;&nbsp;}  
}

The version for LazyCollectionType can be done similarly:

extension LazyCollectionType {  
&nbsp;&nbsp;  
&nbsp;&nbsp;@warn\_unused\_result  
&nbsp;&nbsp;public func flatMap\<T\>(transform: Elements.Generator.Element -\> T?)  
&nbsp;&nbsp;&nbsp;&nbsp;-\> LazyMapCollection\<LazyFilterCollection\<LazyMapCollection\<Elements, T?\>\>, T\> {  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return self  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.map(transform)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.filter { opt in opt != nil }  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.map { notNil in notNil! }  
&nbsp;&nbsp;}  
}

There seems to be no performance overhead vs the custom struct version in my (very preliminary) testing.

The version for a LazyCollectionType with a BidirectionalIndexType would rely on a similar LazyFilterCollection, but a BidirectionalFilterCollection doesn’t exist (I think). Is that something that might be included in this proposal?

Oisin.

> **···**
>
> > On 6 Dec 2015, at 09:11, Dmitri Gribenko \<gribozavr@gmail.com\> wrote:
> > 
> > On Fri, Dec 4, 2015 at 2:38 PM, Donnacha Oisín Kidney \<oisin.kidney@gmail.com \<mailto:oisin.kidney@gmail.com\>\> wrote:  
> > Currently, several of the methods on SequenceType in the standard library have lazy variants. flatMap, though, (seems) to have a version missing: while there’s a lazy version for nested sequences, there’s no lazy version for sequences of Optionals. Is there maybe a reason for this that I haven’t thought of? At any rate, here’s what I had in mind:
> > 
> > public struct FlatMapOptionalGenerator\<G: GeneratorType, Element\>: GeneratorType {  
> > &nbsp;&nbsp;private let f: G.Element -\> Element?  
> > &nbsp;&nbsp;private var g: G  
> > &nbsp;&nbsp;public mutating func next() -\> Element? {  
> > &nbsp;&nbsp;&nbsp;&nbsp;while let x = g.next() {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if let y = f(x) {  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return y  
> > &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;&nbsp;&nbsp;}  
> > &nbsp;&nbsp;&nbsp;&nbsp;return nil  
> > &nbsp;&nbsp;}  
> > }
> > 
> > public struct FlatMapOptionalSequence\<S: LazySequenceType, Element\>: LazySequenceType {  
> > &nbsp;&nbsp;private let f: S.Generator.Element -\> Element?  
> > &nbsp;&nbsp;private let s: S  
> > &nbsp;&nbsp;public func generate() -\> FlatMapOptionalGenerator\<S.Generator, Element\> {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return FlatMapOptionalGenerator(f: f, g: s.generate())  
> > &nbsp;&nbsp;}  
> > }
> > 
> > extension LazySequenceType {  
> > &nbsp;&nbsp;public func flatMap\<T\>(transform: Generator.Element -\> T?) -\> FlatMapOptionalSequence\<Self, T\> {  
> > &nbsp;&nbsp;&nbsp;&nbsp;return FlatMapOptionalSequence(f: transform, s: self)  
> > &nbsp;&nbsp;}  
> > }
> > 
> > Hi,
> > 
> > Thank you for the proposal.
> > 
> > Defining only one overload would cause the collection-ness of the input to be lost. Please take a look at the current flatMap() overloads in stdlib/public/core/FlatMap.swift: there's one in LazySequenceType, another one in LazyCollectionType, and one more in LazyCollectionType with bidirectional indices.
> > 
> > I'm also not a fan of introducing a specialized result type for this operation: given that we need three overloads, this approach would add six more types to the library (three sequences and three generators). Current flatMap() overloads compose existing types, but they rely on intermediate data structure being a sequence or a collection. Optional is not a sequence, so that exact approach won't work here. Can you think of another way we could combine existing types to express the result of this operation?
> > 
> > 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\>\>\*/

---

<div class="post-metadata">

**Author:** ![gribozavr](https://avatars.discourse-cdn.com/v4/letter/g/65b543/32.png) [@gribozavr](https://forums.swift.org/u/gribozavr)\
**Post date:** [December 7, 2015, 1:04am UTC](https://forums.swift.org/t/lazy-flatmap-for-optionals/127/5 "2015-12-07T01:04:57Z")

</div>

> (forgot to cc the mailing list)
> 
> You can define it in terms of a map-filter-map chain, like this:
> 
> extension LazySequenceType {
> 
> &nbsp;&nbsp;@warn\_unused\_result  
> &nbsp;&nbsp;public func flatMap\<T\>(transform: Elements.Generator.Element -\> T?)  
> &nbsp;&nbsp;&nbsp;&nbsp;-\> LazyMapSequence\<LazyFilterSequence\<LazyMapSequence\<Elements, T?\>\>, T\>  
> {  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return self  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.map(transform)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.filter { opt in opt != nil }  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.map { notNil in notNil! }  
> &nbsp;&nbsp;}  
> }
> 
> The version for LazyCollectionType can be done similarly:
> 
> extension LazyCollectionType {
> 
> &nbsp;&nbsp;@warn\_unused\_result  
> &nbsp;&nbsp;public func flatMap\<T\>(transform: Elements.Generator.Element -\> T?)  
> &nbsp;&nbsp;&nbsp;&nbsp;-\> LazyMapCollection\<LazyFilterCollection\<LazyMapCollection\<Elements,  
> T?\>\>, T\> {  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return self  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.map(transform)  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.filter { opt in opt != nil }  
> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.map { notNil in notNil! }  
> &nbsp;&nbsp;}  
> }

I like this.

> The version for a LazyCollectionType with a BidirectionalIndexType would  
> rely on a similar LazyFilterCollection, but a BidirectionalFilterCollection  
> doesn’t exist (I think). Is that something that might be included in this  
> proposal?

Indeed. I think that would be a separate proposal.

Dmitri

> **···**
>
> On Sun, Dec 6, 2015 at 8:06 AM, Donnacha Oisín Kidney \<oisin.kidney@gmail.com\> wrote:
> 
> --  
> 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\>\*/