apple / apple/swift-algorithms
Add API for counting all objects in a collection
- Dominant language
- Swift
- Stars
- 6.3k
- Forks
- 483
- PR merge metrics
- No merged PRs in 30d
Description
# Goal
It pretty common to want to take a collection of items, and count the number of occurrences of each item. e.g.
```swift
let input = ["a", "b", "c", "b", "a"]
let desiredOutput = ["a": 2, "b": 2, "c": 1]
```
# Today
There's 2 relatively short ways to achieve this today:
1. Using `reduce`: `input.reduce(into: [:]) { $0[default: 0] += 1 }`
Reduce is [really general](https://github.com/amomchilov/Blog/blob/master/Don't%20abuse%20reduce.md), and isn't particularly readable, especially for beginners. The performance here is good though, allocating a single dictionary and mutating it in-place.
2. Using `group(by:)`: `group(by: { $0 }).mapValues(\.count)`
We could use the `group(by:)` helper that I added to Swift Algorithms, but it allocates a ton of intermediate arrays for all the groups, when all we need is their counts.
# Proposed solution
The exact name is TBD, but I'm proposing a function like:
```swift
extension Sequence where Element: Hashable {
func tallied() -> [Element: Int] {
return reduce(into: [:]) { $0[default: 0] += 1 }
}
}
```
We could also consider taking a `by:` parameter, to count things by a value other than themselves. Though perhaps `.lazy.map` would be better. E.g. `input.tallied(by: \.foo)` could be expressed as `input.lazy.map(\.foo).tallied()`
# Alternatives
## A more general "collectors" API
Similar to Java collectors, which let you express transformations over streams, collecting into Arrays, Dictionaries, Counters, or anything else you might like.
This could pair well with Swift Collections, e.g. if we added a new `CountedSet` (a native Swift alternative to [`NSCountedSet`](https://developer.apple.com/documentation/foundation/nscountedset). E.g. we could have:
```swift
input.grouping(by: \.foo, collectingInto: { CountedSet() })
```
# Prior art
| Language | Name |
|----------|------|
| Python | [`collections.Counter`](https://docs.python.org/3/library/collections.html#collections.Counter)
| Ruby | [`tally`](https://rubyapi.org/3.4/o/enumerable#method-i-tally) |
| Java | [`java.util.stream.Collectors.counting()`](https://docs.oracle.com/javase/8/docs/api/java/util/stream/Collectors.html#counting--)
| JavaScript (Lodash) | [`countBy`](https://lodash.com/docs#countBy) |
C#, Rust don't have helpers for this.
Contributor guide
Research direction
No implementation file or test is named. Start by reviewing the existing reduce and group(by:) APIs in Swift Algorithms, then resolve the proposed counting API's name and scope; done means an agreed design and a tested sequence-counting implementation.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- swift
- Domain
- api
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100