Generics with Generators and Sequences in Swift

Question

I have a fairly good understanding of OO programming and Swift, however, one area that really leaves me stumped is Generators and Sequences (I am fine with the concept of protocols by the way).

For example, I completed this exercise from the Swift Guide (Apple)

“EXPERIMENT Modify the anyCommonElements function to make a function that returns an array of the elements that any two sequences have in common.”

Turning this:

func​ ​anyCommonElements​ <​T​, ​U​ ​where​ ​T​: ​SequenceType​, ​U​: ​SequenceType​, ​T​.​Generator​.​Element​: ​Equatable​, ​T​.​Generator​.​Element​ == ​U​.​Generator​.​Element​> (​lhs​: ​T​, ​rhs​: ​U​) -> ​Bool​ {   
    for​ ​lhsItem​ ​in​ ​lhs​ {
        for​ ​rhsItem​ ​in​ ​rhs​ {
            if​ ​lhsItem​ == ​rhsItem​ {
                return​ ​true
            }
        }
    }
    return​ ​false
}

Into this:

func anyCommonElements <T, U where T: SequenceType, U: SequenceType, T.Generator.Element: Equatable, T.Generator.Element == U.Generator.Element> (lhs: T, rhs: U) -> [T.Generator.Element]? {
var commonElements:[T.Generator.Element]? = nil
    for lhsItem in lhs {
        for rhsItem in rhs {
            if lhsItem == rhsItem {
                if (commonElements == nil)
                {
                    commonElements = []  //init the array if not already
                }
                commonElements?.append(lhsItem) //add matching item to the array
            }
        }
    }
    return commonElements? //return nil or array of matched elements
}

I'm happy with the solution I've written and it works well, including the Optional return, however I am lost as to why the type of the commonElements return array needs to be this:

var commonElements:[T.Generator.Element]

Rather than this:

var commonElements:[T]

I've read a fair bit on the subject, including:

https://schani.wordpress.com/2014/06/06/generators-in-swift/

http://robots.thoughtbot.com/swift-sequences

http://natashatherobot.com/swift-conform-to-sequence-protocol/

But I am still completely lost - can someone please help explain this in simple terms or is it just a little abstract and not easy to describe?

Would really appreciate it, Thanks, John

Update for Swift 5: (using Sequence instead of SequenceType, Iterator instead of Generator, and new Where syntax.

func anyCommonElements <T, U> (lhs: T, rhs: U) -> [T.Iterator.Element] where T: Sequence, U: Sequence, T.Iterator.Element: Equatable, T.Iterator.Element == U.Iterator.Element {
    var commonElements:[T.Iterator.Element] = []
    for lhsItem in lhs {
        for rhsItem in rhs {
            if lhsItem == rhsItem {
                commonElements.append(lhsItem) //add matching item to the array
            }
        }
    }
    return commonElements //return nil or array of matched elements
}

In fact, you can just do T.Element now, and forget about the Iterator.

Answer 1

T is a sequence type. For simplicity, let's take a special and familiar case and say T is an array.

Then the type of thing contained in the array is T.Generator.Element. This is because of the way the Array struct is defined. Keep in mind that Array is a generic. It is a SequenceType, which is a (generic) protocol with an empty type alias Generator, which is constrained to be a GeneratorType, which in turn is a (generic) protocol that has an empty type alias Element. When the generic is specialized, those empty type aliases are "filled in" with an actual type. All sequences are like that. So if T is an Array, then T.Generator.Element means "the actual type of this array's actual elements".

So [T.Generator.Element] means "an array of the same kind of element as the original array's elements.

Your proposed expression, [T], would mean an array of arrays, which is not what we want.

Okay, now generalize T back to any sequence (array, string of character, etc.) and that explanation keeps on working.