Histogram of Array in Swift

Question

I'm trying to write a generic histogram function that operates on an Array, but I'm running into difficulties as Type 'Element' does not conform to protocol 'Hashable'.

extension Array {
    func histogram() -> [Array.Element: Int] {
        return self.reduce([Array.Element: Int]()) { (acc, key) in
                let value = (acc[key] == nil) ? 1 : (acc[key]! + 1)
                return acc.dictionaryByUpdatingKey(key: key, value: value)
        }
    }
}

where dictionaryByUpdatingKey(...) mutates an existing dictionary as follows:

extension Dictionary {
    func dictionaryByUpdatingKey(key: Dictionary.Key, value: Dictionary.Value) -> Dictionary {
        var mutableSelf = self
        let _ = mutableSelf.updateValue(value, forKey: key)
        return mutableSelf
    }
}

I have tried replacing Array.Element with AnyHashable and then forcing the key as! AnyHashable, but this seems messy and the return type should preferably be of the same type as the Array.Element and not of AnyHashable.

I wish to use the Array extension as follows:

let names = ["Alex", "Alex", "James"]
print(names.histogram()) // ["James": 1, "Alex": 2]

or

let numbers = [2.0, 2.0, 3.0]
print(numbers.histogram()) // [3.0: 1, 2.0: 2]

You should learn about `reduce(into:updateAccumulatingResult:)` which is more efficient in such cases. — Martin R, Apr 23 '18 at 11:07

vacawama · Accepted Answer · 2020-07-04T21:57:38.973

12

Add the generic where clause: where Element: Hashable to your extension:

extension Sequence where Element: Hashable {
    func histogram() -> [Element: Int] {
        return self.reduce([Element: Int]()) { (acc, key) in
            let value = acc[key, default: 0] + 1
            return acc.dictionaryByUpdatingKey(key: key, value: value)
        }
    }
}

I also incorporated @MartinR's suggestion of using the new default value for dictionary look ups.

Using reduce(into:_:) you can do this much more simply and efficiently:

extension Sequence where Element: Hashable {
    func histogram() -> [Element: Int] {
        return self.reduce(into: [:]) { counts, elem in counts[elem, default: 0] += 1 }
    }
}

edited Jul 04 '20 at 21:57

answered Apr 23 '18 at 10:53

vacawama

150,663
30
266
294

Thanks! Works great. – ajrlewis Apr 23 '18 at 10:57
2

Simpler: `let value = acc[key, default: 0] + 1` – Martin R Apr 23 '18 at 11:05
Have a look at your answer https://stackoverflow.com/a/30545629/1187415 :) – Martin R Apr 23 '18 at 11:10
LOL, I know @MartinR. I was focused on the question at hand this time and didn't look at the rest of the code. – vacawama Apr 23 '18 at 11:12

score 1 · Answer 2 · answered Apr 23 '18 at 10:56

First, you could limit the Element type to only be Hashable.

extension Array where Array.Element:Hashable {

After this, you might get another error because the swift compiler is a little "overstrained". Try to give him a hint:

typealias RT = [Array.Element: Int]

and use it everywhere. So:

extension Array where Array.Element:Hashable {
    typealias RT = [Array.Element: Int]
    func histogram() -> RT {
        return self.reduce(RT()) { (acc, key) in
            let value = (acc[key] == nil) ? 1 : (acc[key]! + 1)
            return acc.dictionaryByUpdatingKey(key: key, value: value)
        }
    }
}

finally should work.

Histogram of Array in Swift

2 Answers2

Linked