My first reading of the Swift books and of the generated Swift library header (remember, you can see the header by command-double-clicking on any Swift type) left me quite confused about the proper way to write generics and extensions to generics.

As usual, I favor learning-by-doing for such things [skydiving joke omitted] — I paged through a book on “Type Theory” to no avail — so, in a recent update to my SwiftChecker app I tried to include a useful extension.

Here is a (slightly edited) part of it:

public extension Dictionary {
	/**	Merges a sequence of values into a Dictionary by specifying
		a filter function. The filter function can return nil to filter
		out that item from the input Sequence, or return a (key,value)
		tuple to insert or change an item. In that case, value can be
		nil to remove the item for that key. */
	mutating func merge <T, S: SequenceType where S.Generator.Element == T>
		(seq: S, filter: (T) -> (Key, Value?)?) {
		var gen = seq.generate()
		while let t: T = {
			if let (key: Key, value: Value?) = filter(t) {
				self[key] = value
}	// end of Dictionary extension

To explain this, first recall that types can include typealias declarations within their definitions; this is much used for generic types, but can also be used everywhere. Here’s the declaration for Sequence from the library header:

protocol SequenceType : _Sequence_Type {
    typealias Generator : GeneratorType
    func generate() -> Generator

and of the GeneratorType protocol it uses:

protocol GeneratorType {
    typealias Element
    mutating func next() -> Element?

Going backwards: the GeneratorType protocol defines an associated type with the typealias declaration, in this case, Element. This is a placeholder type that will become an actual type when the protocol is adopted. These associated types form a hierarchy, so that you can refer to GeneratorType.Element and, further up, to Sequence.Generator.Element, and so forth.

Now look again at the merge method I define in my extension to Dictionary:

	mutating func merge <T, S: SequenceType where S.Generator.Element == T>
		(seq: S, filter: (T) -> (Key, Value?)?) { // ... etc.

Inside the <> after the method name are the type constraints. When I call merge on a Dictionary, this means that:

  • T is a placeholder type (with no constraints) used for the rest of the definition
  • S is another placeholder that is constrained to conform to the SequenceType protocol, and further (by using the where clause)
  • the generate() function for S must return a Generator whose Element is equal to T, and also
  • T is inferred from the argument type of the function/closure passed as the last argument to merge, and finally
  • this function/closure must return an Optional tuple of type (Key, Value?).

But what is this (Key, Value?) type, then? Recall that we’re extending Dictionary, so that type’s associated type hierarchy is also available; checking the declaration in the library header, we see:

struct Dictionary<Key : Hashable, Value> : CollectionType, DictionaryLiteralConvertible {
    typealias Element = (Key, Value)
    typealias Index = DictionaryIndex<Key, Value>
    ... etc.

so our type constraint will match Key and Value to those pertaining to the particular Dictionary that merge is being called on! To be more clear, we could even write (Dictionary.Key, Dictionary.Value?) in our definition.

Let’s look at a specific example of that. Notice that, where in the type constraints we refer to the placeholder type names (on the left of the typealias declarations), we refer to specific types wherever one is defined.

let strs = [ "10", "11", "12", "xyz" ]	// this is an Array  and therefore
					// its Generator.Element is String
let dict = [ 0:"0" ]	// this is a Dictionary <Int, String> and therefore
			// its Key is Int and Value is String
dict.merge (strs) { (s) in	// s is inferred to be strs's Generator.Element,
				// that is, a String
	let v = s.toInt()	// v is an Optional , will be nil for "xyz"
	return v ? (v!, s) : nil	// returns a valid tuple or nil
// dict will now contain [ 0:"0", 10:"10", 11:"11", 12:"12" ]

You can verify that everything matches our type constraints either directly or by type inference. If you change anything that doesn’t fit — say, by declaring s as anything but String inside the closure, or changing the type it returns — you’ll see a syntax error. (Assuming, of course, that no other extension has matching constraints.)

That said, currently (Xcode 6.0b5) the library header still has some bugs. Specifically, many type constraints either have too many prefixes removed, or show the wrong hierarchy, so you’ll see things like <S : Sequence where T == T> which won’t compile if you copy & paste it. No doubt this will be fixed soon.

Update: oops. Fixed the return, above.

Update#2: updated for Xcode 6.0b5 — many of those typenames either lost or gained a Type suffix.