Implementing Set.addSequence in Swift

Question

I've implemented a Set in Swift that uses Dictionary keys. I want to implement an addAll(sequence) method that takes any sequence type over the Elements in the Set, but I'm getting an error that doesn't make sense. Here's my code

struct Set<Element: Hashable> {
    var hash = [Element: Bool]()

    init(elements: [Element] = []) {
        for element in elements {
            self.hash[element] = true
        }
    }

    var array: [Element] {
        return hash.keys.array
    }

    func contains(element: Element) -> Bool {
        return hash[element] ?? false
    }

    mutating func add(element: Element) {
        hash[element] = true
    }

    mutating func add(array: [Element]) {
        for element in array {
            hash[element] = true
        }
    }

    mutating func add<S : SequenceType where S.Generator.Element == Element>(sequence: S) {
        for element in sequence { // Error here: "Cannot convert the expression's type 'S' to type 'S'
            hash[element] = true
        }
    }

    mutating func remove(element: Element) {
        hash[element] = nil
    }
}

I'm getting this error in XCode 6.1 and 6.0.1.

I wanted to follow the semantics of Array's extend method, but that type signature doesn't even compile for me.

Am I doing something wrong, or should I file a Radar?

edit: just found https://github.com/robrix/Set/blob/master/Set/Set.swift, which has this implementation:

public mutating func extend<S : SequenceType where S.Generator.Element == Element>(sequence: S) {
    // Note that this should just be for each in sequence; this is working around a compiler crasher.
    for each in [Element](sequence) {
        insert(each)
    }
}

However, that just converts sequence into an Array, which kind of defeats the purpose of SequenceType altogether.

Answer 1

Update: This has been fixed in Swift 1.2 (Xcode 6.3 beta 3), the original code from the question compiles without errors. (Also, defining a custom set type is not necessary anymore because Swift 1.2 has a native Set type built-in.)

---

Old answer: It looks like a bug to me, but perhaps someone can explain it.

Possible workarounds:

• Convert the sequence argument to SequenceOf<Element> explicitly:

  mutating func add<S : SequenceType where S.Generator.Element == Element>(sequence: S) {
      for element in SequenceOf<Element>(sequence)  {
          hash[element] = true
      }
  }
  

• (As in https://stackoverflow.com/a/27181111/1187415) Replace the for-loop by a while-loop using next() of the sequence generator, and type annotate the element explicitly with element : Element:

  mutating func add<S : SequenceType where S.Generator.Element == Element>(sequence: S) {
      var gen = sequence.generate()
      while let element : Element = gen.next() {
          hash[element] = true
      }
  }
  

• (From "Creating a Set Type in Swift") Use map:

  mutating func add<S : SequenceType where S.Generator.Element == Element>(sequence: S) {
      map(sequence) {
          self.hash[$0] = true
      }
  }
  

Answer 2

The best I could come up with was the map solution that Martin also produced. Interestingly enough, manually expanding the for loop as:

mutating func add<S : SequenceType where S.Generator.Element == Element>(sequence: S) {
    var generator = sequence.generate()
    while let item = generator.next() {
        self.hash[item] = true
    }
}

Produces yet another error message at generator.next():

Cannot convert the expression's type '()' to type 'Self.Element??'

It might be somewhat more optimal to use reduce instead of map, as that doesn't build an array to discard:

mutating func add<S : SequenceType where S.Generator.Element == Element>(sequence: S) {
    reduce(sequence, ()) {
        self.hash[$1] = true
    }
}