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
– Martin R, Commented Apr 23, 2018 at 11:07

vacawama · Accepted Answer · 2020-07-04 21:57:38Z

11

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 4, 2020 at 21:57

answered Apr 23, 2018 at 10:53

vacawama

155k32 gold badges283 silver badges315 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

ajrlewis Over a year ago

Thanks! Works great.

Martin R Over a year ago

Simpler: let value = acc[key, default: 0] + 1

Martin R Over a year ago

Have a look at your answer stackoverflow.com/a/30545629/1187415 :)

vacawama Over a year ago

LOL, I know @MartinR. I was focused on the question at hand this time and didn't look at the rest of the code.

Andreas Oetjen · Accepted Answer · 2018-04-23 10:56:12Z

1

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.

answered Apr 23, 2018 at 10:56

Andreas Oetjen

10.3k1 gold badge27 silver badges35 bronze badges

Collectives™ on Stack Overflow

Histogram of Array in Swift

2 Answers 2

4 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related