apple / apple/swift-algorithms

Add API for counting all objects in a collection

Open
#243 2 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.