Extend int arrays to be hashable?


(Jean-Denis Muys) #1

Hello,

I am struggling to convince Swift 3 (from Xcode 8 beta 6) to let me use an array of Int as dictionary keys.

It doesn’t work out of the box, because an array is not hashable:

var answers: [[Int]:Bool] = [:] // error: Type [Int] does not conform to Protocol Hashable

One way to work around that would be to use a string representation of the Int array but this is inefficient, and besides, String implements hashValue in a similar way (I suppose) that I can do for an Int Array.

I can extend Array to include a hash function:

extension Array where Element: Int {
    
    var hashValue: Int {
        return self.reduce(5381) {
            ($0 << 5) &+ $0 &+ $1
        }
    }
}

However, Swift naturally still complains:

var answers: [[Int]:Bool] = [:] // error: Type [Int] does not conform to Protocol Hashable

My problem is that I cannot add conformance to Hashable. The following attempt fails:

extension Array where Element: Int { // error: extension of type ‘Array’ with constraints cannot have an inheritance clause
    
    var hashValue: Int {
        return self.reduce(5381) {
            ($0 << 5) &+ $0 &+ $1
        }
    }
}

Is there a solution?

I also tried with no success to define a new confirming type as a subtype of Array<Int>:

struct HashableIntArray: Array<Int>, Hashable { // error: inheritance from non-protocol type Array<Int>
  // ...
}

I suppose I could make my HashableIntArray “have-a” Array<Int>, but then I would have to reimplement all the Array API with boilerplate code, which is really inelegant at best.

What did I miss?

Jean-Denis


(Brent Royal-Gordon) #2

Nothing. In the current version of Swift, the best solution is to write a wrapper HashableArray type. One thing which might help is that you don't really have to support the full interface of Array; it's enough to say:

  struct HashableArray<Element: Hashable>: Hashable {
    var elements: [Element]
    init(_ elements: [Element]) {
      self.elements = elements
    }
    
    var hashValue: Int { … }
    static func == (lhs: HashableArray, rhs: HashableArray) -> Bool { … }
  }

And then use the array operations on the `elements` property.

In the future, we hope to support conditional conformances, so you could say:

  extension Array: Hashable where Element: Hashable {
      var hashValue: Int {
          return self.reduce(5381) {
              ($0 << 5) &+ $0 &+ $1.hashValue
          }
      }
  }

But that happy day has not yet arrived.

(When that day *does* come, I wouldn't be surprised if the Hashable conformance is in the standard library and you don't even need to implement it yourself.)

···

On Sep 6, 2016, at 12:38 AM, Jean-Denis Muys via swift-users <swift-users@swift.org> wrote:

I suppose I could make my HashableIntArray “have-a” Array<Int>, but then I would have to reimplement all the Array API with boilerplate code, which is really inelegant at best.

What did I miss?

--
Brent Royal-Gordon
Architechies