Need better name, want to hide generator


(Erica Sadun) #1

Source: http://swiftstub.com/788132715

Two questions:

1. Can anyone recommended a better name than Cartesian? 2D doesn't work for the compiler and I'm looking for something that doesn't seem "floating-point"-y
2. Is there a way to internalize the generator and not make it public? I'd ideally like to hide all details except the fact that this is a sequence of (Int, Int)

Thanks

-- Erica


(Jacob Bandes-Storch) #2

1. Maybe ProductGenerator?
2. Use AnyGenerator<(T, U)>?

I'd love to see something like this in stdlib:

func product<S1, S2>(s1: S1, s2: S2) ->
ProductSequence<S1.Generator.Element, S2.Generator.Element> {
    ...
}

where ProductSequence<T,U>.Generator.Element is (T, U).

So your example could be "for (x,y) in product(0..<4, 0..<2)".

Jacob Bandes-Storch

···

On Fri, Dec 18, 2015 at 1:22 PM, Erica Sadun via swift-users < swift-users@swift.org> wrote:

Source: http://swiftstub.com/788132715

Two questions:

1. Can anyone recommended a better name than Cartesian? 2D doesn't work
for the compiler and I'm looking for something that doesn't seem
"floating-point"-y
2. Is there a way to internalize the generator and not make it public? I'd
ideally like to hide all details except the fact that this is a sequence of
(Int, Int)

Thanks

-- Erica

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


(Jacob Bandes-Storch) #3

Oops, of course I meant product<S1: SequenceType, S2: SequenceType>(...) !

Jacob

···

On Fri, Dec 18, 2015 at 1:45 PM, Jacob Bandes-Storch <jtbandes@gmail.com> wrote:

1. Maybe ProductGenerator?
2. Use AnyGenerator<(T, U)>?

I'd love to see something like this in stdlib:

func product<S1, S2>(s1: S1, s2: S2) ->
ProductSequence<S1.Generator.Element, S2.Generator.Element> {
    ...
}

where ProductSequence<T,U>.Generator.Element is (T, U).

So your example could be "for (x,y) in product(0..<4, 0..<2)".

Jacob Bandes-Storch

On Fri, Dec 18, 2015 at 1:22 PM, Erica Sadun via swift-users < > swift-users@swift.org> wrote:

Source: http://swiftstub.com/788132715

Two questions:

1. Can anyone recommended a better name than Cartesian? 2D doesn't work
for the compiler and I'm looking for something that doesn't seem
"floating-point"-y
2. Is there a way to internalize the generator and not make it public?
I'd ideally like to hide all details except the fact that this is a
sequence of (Int, Int)

Thanks

-- Erica

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


(Erica Sadun) #4

At a minimum, this gives me http://swiftstub.com/60017598

But I remember reading *somewhere* (can't remember) that we were supposed to avoid AnyGenerator/AnySequence and they were on the way out. Am I out of my mind?

-- E

···

On Dec 18, 2015, at 2:47 PM, Jacob Bandes-Storch <jtbandes@gmail.com> wrote:

Oops, of course I meant product<S1: SequenceType, S2: SequenceType>(...) !

Jacob

On Fri, Dec 18, 2015 at 1:45 PM, Jacob Bandes-Storch <jtbandes@gmail.com <mailto:jtbandes@gmail.com>> wrote:
1. Maybe ProductGenerator?
2. Use AnyGenerator<(T, U)>?

I'd love to see something like this in stdlib:

func product<S1, S2>(s1: S1, s2: S2) -> ProductSequence<S1.Generator.Element, S2.Generator.Element> {
    ...
}

where ProductSequence<T,U>.Generator.Element is (T, U).

So your example could be "for (x,y) in product(0..<4, 0..<2)".

Jacob Bandes-Storch

On Fri, Dec 18, 2015 at 1:22 PM, Erica Sadun via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:
Source: http://swiftstub.com/788132715

Two questions:

1. Can anyone recommended a better name than Cartesian? 2D doesn't work for the compiler and I'm looking for something that doesn't seem "floating-point"-y
2. Is there a way to internalize the generator and not make it public? I'd ideally like to hide all details except the fact that this is a sequence of (Int, Int)

Thanks

-- Erica

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


(Erica Sadun) #5

p.s. http://swiftstub.com/195460039

(I'm sure this could be done more lazily and well)

···

On Dec 18, 2015, at 2:47 PM, Jacob Bandes-Storch <jtbandes@gmail.com> wrote:

Oops, of course I meant product<S1: SequenceType, S2: SequenceType>(...) !

Jacob

On Fri, Dec 18, 2015 at 1:45 PM, Jacob Bandes-Storch <jtbandes@gmail.com <mailto:jtbandes@gmail.com>> wrote:
1. Maybe ProductGenerator?
2. Use AnyGenerator<(T, U)>?

I'd love to see something like this in stdlib:

func product<S1, S2>(s1: S1, s2: S2) -> ProductSequence<S1.Generator.Element, S2.Generator.Element> {
    ...
}

where ProductSequence<T,U>.Generator.Element is (T, U).

So your example could be "for (x,y) in product(0..<4, 0..<2)".

Jacob Bandes-Storch

On Fri, Dec 18, 2015 at 1:22 PM, Erica Sadun via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:
Source: http://swiftstub.com/788132715

Two questions:

1. Can anyone recommended a better name than Cartesian? 2D doesn't work for the compiler and I'm looking for something that doesn't seem "floating-point"-y
2. Is there a way to internalize the generator and not make it public? I'd ideally like to hide all details except the fact that this is a sequence of (Int, Int)

Thanks

-- Erica

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


(Dmitri Gribenko) #6

You can use AnySequence and AnyGenerator, but they come at a cost of
dynamic dispatch for every call. In this case, if you want this component
to be suitable for performance-critical code, I would suggest to avoid them
for now.

Dmitri

···

On Fri, Dec 18, 2015 at 1:22 PM, Erica Sadun via swift-users < swift-users@swift.org> wrote:

2. Is there a way to internalize the generator and not make it public? I'd
ideally like to hide all details except the fact that this is a sequence of
(Int, Int)

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


(Rob Mayoff) #7

1. Can anyone recommended a better name than Cartesian? 2D doesn't work
for the compiler and I'm looking for something that doesn't seem
"floating-point"-y

"AllPairs" seems self-explanatory.

"CrossJoin" should be intuitive to anyone familiar with relational
databases.

"product" sounds like it might be multiplying elements with each other.


(Joe Groff) #8

They aren't on the way out. We'd like to migrate them with first-class language support for protocol types with associated type constraints, but we wouldn't eliminate the functionality.

-Joe

···

On Dec 18, 2015, at 2:25 PM, Erica Sadun via swift-users <swift-users@swift.org> wrote:

At a minimum, this gives me http://swiftstub.com/60017598

But I remember reading *somewhere* (can't remember) that we were supposed to avoid AnyGenerator/AnySequence and they were on the way out. Am I out of my mind?


(Erica Sadun) #9

Lazier.

http://swiftstub.com/596982131

···

On Dec 18, 2015, at 3:32 PM, Erica Sadun <erica@ericasadun.com> wrote:

p.s. http://swiftstub.com/195460039

(I'm sure this could be done more lazily and well)

On Dec 18, 2015, at 2:47 PM, Jacob Bandes-Storch <jtbandes@gmail.com <mailto:jtbandes@gmail.com>> wrote:

Oops, of course I meant product<S1: SequenceType, S2: SequenceType>(...) !

Jacob

On Fri, Dec 18, 2015 at 1:45 PM, Jacob Bandes-Storch <jtbandes@gmail.com <mailto:jtbandes@gmail.com>> wrote:
1. Maybe ProductGenerator?
2. Use AnyGenerator<(T, U)>?

I'd love to see something like this in stdlib:

func product<S1, S2>(s1: S1, s2: S2) -> ProductSequence<S1.Generator.Element, S2.Generator.Element> {
    ...
}

where ProductSequence<T,U>.Generator.Element is (T, U).

So your example could be "for (x,y) in product(0..<4, 0..<2)".

Jacob Bandes-Storch

On Fri, Dec 18, 2015 at 1:22 PM, Erica Sadun via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:
Source: http://swiftstub.com/788132715

Two questions:

1. Can anyone recommended a better name than Cartesian? 2D doesn't work for the compiler and I'm looking for something that doesn't seem "floating-point"-y
2. Is there a way to internalize the generator and not make it public? I'd ideally like to hide all details except the fact that this is a sequence of (Int, Int)

Thanks

-- Erica

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


(Erica Sadun) #10

Here's what I ended up with. (The use-case for this ended up being light-weight game tile placement, not image processing or anything. )

func cartesianProduct<S1: SequenceType, S2: SequenceType>(s1: S1, _ s2: S2) -> AnySequence<(S1.Generator.Element, S2.Generator.Element)> {
    let items = s1.lazy.flatMap({
        item1 in s2.lazy.map({
            item2 in (item1, item2)})})
    return AnySequence {items.generate()}
}

func cartesianProduct<S1: SequenceType, S2: SequenceType, S3: SequenceType>(s1: S1, _ s2: S2, _ s3: S3) -> AnySequence<(S1.Generator.Element, S2.Generator.Element, S3.Generator.Element)> {
    let items = s1.lazy.flatMap({
        item1 in s2.lazy.flatMap({
            item2 in s3.lazy.map({
                item3 in (item1, item2, item3)})})})
    return AnySequence {items.generate()}
}

I initially suggested to the person I was helping:

for y in (...) {
    for x in (...) {
      ...
    }
}

But I'm glad I got to explore several alternative approaches. Thanks all. A few extra notes, to summarize everything into a single post:

Joe writes: "[AnySeq/Gen] aren't on the way out. We'd like to migrate them with first-class language support for protocol types with associated type constraints, but we wouldn't eliminate the functionality."

Dmitri adds: "You can use AnySequence and AnyGenerator, but they come at a cost of dynamic dispatch for every call. In this case, if you want this component to be suitable for performance-critical code, I would suggest to avoid them for now."

-- E

···

On Dec 18, 2015, at 11:08 PM, Rob Mayoff via swift-users <swift-users@swift.org> wrote:

1. Can anyone recommended a better name than Cartesian? 2D doesn't work for the compiler and I'm looking for something that doesn't seem "floating-point"-y

"AllPairs" seems self-explanatory.

"CrossJoin" should be intuitive to anyone familiar with relational databases.

"product" sounds like it might be multiplying elements with each other.

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


(Jacob Bandes-Storch) #11

Here's a more from-scratch approach, but I like yours better for obvious
reasons.

http://swiftstub.com/732424572

Jacob Bandes-Storch

···

On Fri, Dec 18, 2015 at 2:43 PM, Erica Sadun <erica@ericasadun.com> wrote:

Lazier.

http://swiftstub.com/596982131

On Dec 18, 2015, at 3:32 PM, Erica Sadun <erica@ericasadun.com> wrote:

p.s. http://swiftstub.com/195460039

(I'm sure this could be done more lazily and well)

On Dec 18, 2015, at 2:47 PM, Jacob Bandes-Storch <jtbandes@gmail.com> > wrote:

Oops, of course I meant product<S1: SequenceType, S2: SequenceType>(...) !

Jacob

On Fri, Dec 18, 2015 at 1:45 PM, Jacob Bandes-Storch <jtbandes@gmail.com> > wrote:

1. Maybe ProductGenerator?
2. Use AnyGenerator<(T, U)>?

I'd love to see something like this in stdlib:

func product<S1, S2>(s1: S1, s2: S2) ->
ProductSequence<S1.Generator.Element, S2.Generator.Element> {
    ...
}

where ProductSequence<T,U>.Generator.Element is (T, U).

So your example could be "for (x,y) in product(0..<4, 0..<2)".

Jacob Bandes-Storch

On Fri, Dec 18, 2015 at 1:22 PM, Erica Sadun via swift-users < >> swift-users@swift.org> wrote:

Source: http://swiftstub.com/788132715

Two questions:

1. Can anyone recommended a better name than Cartesian? 2D doesn't work
for the compiler and I'm looking for something that doesn't seem
"floating-point"-y
2. Is there a way to internalize the generator and not make it public?
I'd ideally like to hide all details except the fact that this is a
sequence of (Int, Int)

Thanks

-- Erica

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


(Janosch Hildebrand) #12

Hi Erica,

Just a quick side note with regards to:

Dmitri adds: "You can use AnySequence and AnyGenerator, but they come at a cost of dynamic dispatch for every call. In this case, if you want this component to be suitable for performance-critical code, I would suggest to avoid them for now."

This is very much true. But since Swift 2.0, that overhead can actually be avoided for AnyGenerator given enough context.

Basically, if the producer and consumer of the sequence are in the same module and with whole module optimization enabled (or putting all the relevant parts in the same file), AnyGenerator can be as fast as a native generator.

It's of limited usefulness and a bit weird to use AnyGenerator instead of AnySequence but it can be handy when:
  * performance is critical,
  * you want to use more than one sequence type (with different generators)
  * and can't use generic functions to solve your problem...

- Janosch


(Donnacha Oisín Kidney) #13

I was under the impression that the biggest speed bump for AnyGenerator was that it was a class, rather than a struct? All of the generators on the standard library non-“Any” sequences are structs, for instance.

···

On 20 Dec 2015, at 16:07, Janosch Hildebrand via swift-users <swift-users@swift.org> wrote:

  * and can't use generic functions to solve your problem...


(Janosch Hildebrand) #14

Oh, absolutely. It's just that the compiler is able to optimize through that under the right circumstances.

When the generator is constructed, wrapped with anyGenerator() and used in the same module, the compiler can in theory inline everything and get rid of any boxes and dynamic dispatch, basically reducing it back to the actual generator.

Basically, if the compiler can inline the AnyGenerator construction into the function where it's iterated over, this will work.
(But not if you construct the AnyGenerator with a closure. The compiler can't optimize that case (yet).)

This might have been one of the reasons the AnyGenerator implementation was changed from Swift 1.2 > 2.0. IIRC it always used a closure for the type erasure before 2.0...

Conceptually the same could also work for AnySequence I think. It's just that that is currently too complex for the optimizer to resolve even under ideal circumstances.

But this is more of a side-note about the current capabilities and limitations of the compiler. It's much simpler and more reliable to simply avoid AnyGenerator & AnySequence in most cases if their performance is an issue.

···

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

I was under the impression that the biggest speed bump for AnyGenerator was that it was a class, rather than a struct? All of the generators on the standard library non-“Any” sequences are structs, for instance.

On 20 Dec 2015, at 16:07, Janosch Hildebrand via swift-users <swift-users@swift.org <mailto:swift-users@swift.org>> wrote:

  * and can't use generic functions to solve your problem...

- Janosch