apple / apple/swift-algorithms
Pitch: `common()` — the shared value of a sequence, or `nil`
- Dominant language
- Swift
- Stars
- 6.3k
- Forks
- 483
- PR merge metrics
- No merged PRs in 30d
Description
## Introduction
I'd like to pitch an algorithm that answers the question "do all the elements of this sequence agree, and if so, on what?" — returning the agreed-upon element, or `nil` if they don't agree.
```swift
[1, 1, 1].common() // Optional(1)
[1, 1, 2].common() // nil
[1].common() // Optional(1)
([] as [Int]).common() // nil
```
## Motivation
This is `allSatisfy` and `first` fused into one pass, and it comes up whenever you need to
collapse a collection down to a single representative value *only if* the collection is
in agreement.
The canonical case is a multiple-selection inspector UI — a pattern found across editors,
design tools, spreadsheets, and IDEs, where a field shows a concrete value when every
selected object agrees, and a "Multiple values" placeholder otherwise:
```swift
// Show the shared font size, or nil to display the mixed-values placeholder
fontSizeField.value = selectedLayers.common(\.fontSize)
```
Other places it shows up:
- **Batch validation.** "Can I process these invoices together?" → they must share a currency:
`guard invoices.common(\.currency) != nil else { throw MixedCurrencies() }`
- **Tabular data.** Every row in a parsed CSV should have the same column count;
`rows.common(\.count)` both checks this and hands you the width directly.
- **Merging configuration.** Collapsing a set of per-target settings into a single value
when they don't conflict.
- **Geometry.** Checking a set of points shares an x-coordinate before treating them as a
vertical line.
### What this looks like today
The natural workaround needs two passes and states the projection twice:
```swift
let currency = invoices.first?.currency
let sharedCurrency = invoices.allSatisfy { $0.currency == currency } ? currency : nil
```
That's easy to get subtly wrong (note that it quietly returns `nil` for an empty sequence
only because `first` was `nil` — the intent isn't visible), it can't early-exit cleanly
without restructuring, and it forces the projection into two places that must be kept in
sync. A `reduce`-based version fares worse:
```swift
let sharedCurrency = invoices.dropFirst().reduce(invoices.first) { acc, invoice in
acc?.currency == invoice.currency ? acc : nil
}
```
...which traverses the whole sequence even after a mismatch, and doesn't work on
single-pass sequences at all.
## Proposed solution
Three overloads — a bare form for `Equatable` elements, a `by:` form taking a binary
predicate (following `min(by:)` and `max(by:)`), and an unlabelled projection form that
reads like `map`:
```swift
// Equatable elements
[3, 3, 3].common() // Optional(3)
// Custom equivalence
let word = ["hello", "Hello"]
words.common(by: { $0.lowercased() == $1.lowercased() }) // Optional("hello")
// Projection — returns the projected value, not the element
let layers = [Layer(size: 12), Layer(size: 12), Layer(size: 12)]
layers.common(\.size) // Optional(12)
```
## Detailed design
```swift
extension Sequence where Element: Equatable {
/// Returns the sequence's single shared element, or `nil` if the elements
/// are not all equal.
///
/// - Returns: The first element, if every element is equal to it;
/// otherwise, `nil`. Returns `nil` for an empty sequence.
/// - Complexity: O(*n*)
public func common() -> Element?
}
extension Sequence {
/// Returns the sequence's single shared element, or `nil` if the elements
/// are not all equivalent according to the given predicate.
public func common(
by areEquivalent: (Element, Element) throws -> Bool
) rethrows -> Element?
/// Returns the value the given projection produces for every element, or
/// `nil` if it does not produce the same value for all of them.
///
/// - Returns: The projection of the first element, if the projection of
/// every element is equal to it; otherwise, `nil`. Returns `nil` for an
/// empty sequence.
/// - Complexity: O(*n*)
public func common(
_ projection: (Element) throws -> T
) rethrows -> T?
}
```
**Semantics.** The first element is retained and every subsequent element is compared
against *it* — not against its immediate predecessor. For a proper equivalence relation
these coincide; for a non-transitive predicate passed to `by:` they don't, so the
documentation should state the comparison order explicitly.
**Complexity.** O(*n*) time, O(1) space, single pass, with early exit on the first
mismatch. Works on single-pass sequences.
**Implementation sketch.**
```swift
public func common(
by areEquivalent: (Element, Element) throws -> Bool
) rethrows -> Element? {
var iterator = makeIterator()
guard let first = iterator.next() else { return nil }
while let next = iterator.next() {
guard try areEquivalent(first, next) else { return nil }
}
return first
}
```
The `Equatable` overload forwards to this one. The projection overload needs its own
implementation, since it returns `T` rather than `Element`:
```swift
public func common(
_ projection: (Element) throws -> T
) rethrows -> T? {
var iterator = makeIterator()
guard let first = try iterator.next().map(projection) else { return nil }
while let next = try iterator.next().map(projection) {
guard first == next else { return nil }
}
return first
}
```
Note that this calls `projection` exactly once per element, which matters if it is
expensive or has side effects.
## Prior art
Rust's `itertools` ships both halves of this: `all_equal()` returning `bool`, and
`all_equal_value()`, which returns the shared item on success and an error carrying the
first two differing elements on failure. It treats an empty iterator as `all_equal() == true`
but as an *error* case for `all_equal_value()` — the same tension discussed under open
questions below.
## Alternatives considered
**`allEqual() -> Bool`.** Strictly less useful: callers who want the value have to follow
up with `first`, which reintroduces the two-pass shape this is meant to remove. The
Boolean is trivially recoverable as `common() != nil` (or, for the empty-sequence
semantics, see below). Could reasonably ship alongside, but shouldn't ship instead.
**Returning the mismatch for diagnostics.** A `Result` or a
throwing variant could report *which* two elements disagreed, which is useful for error
messages in the validation cases above. This costs a bespoke error type and makes the
common case noisier at the call site. Optional seems like the right default; a diagnostic
variant could be added later.
**Distinguishing empty case specially.** For a multiple-selection UI, if there's no common value, the UI often distinguishes between mixed values versus no values. This could be encapsulated by a custom enum, but that would likely be in the way for majority of use cases. It's easy enough for callers to check `isEmpty` when `common()` returns `nil`.
**Having the projection overload return the `Element`** rather than the projected value.
This would make all three overloads return `Element?`, which is tidier as a signature set
and preserves more information. It was rejected because the call site reads against it:
`layers.common(\.size)` looks like it should hand back the size, and recovering it via
`layers.common(\.size)?.size` is redundant. Callers who want the element instead can
reach for `common(by:)` with a projecting predicate.
**Naming.** `common()` is proposed for its brevity and because it reads naturally at the
call site, but arguments could be made that it isn't fully clear. One could object that "common" carries a set-intersection connotation in a collection context ("the elements these two have in common"), which is close to the
opposite of the meaning here. Alternatives: `uniformValue()` avoids that reading entirely
("uniform" meaning *the same throughout*) at the cost of some verbosity;
`allEqualValue()` follows the itertools precedent directly but leads with a
Boolean-sounding phrase while returning an Optional, and reads awkwardly in front of a
key path; `sharedValue()` has the same intersection problem as `common()`; `constantValue()` and
`unanimousValue()` are both accurate, but the former reads mathematical and the latter
isn't a term of art.
## Open questions
1. **Should the projection be unlabelled?** `common(\.fontSize)` mirrors `map` and reads
well, but the package's existing projection-vs-predicate pairs use an explicit label —
`chunked(on:)` alongside `chunked(by:)`. A labelled `common(on:)` would match that
precedent at some cost to fluency. I prefer the unlabelled form, but consistency within
the package may matter more.
2. **Empty sequences.** The proposal returns `nil`, which conflates "empty" with "not
uniform". Vacuously, an empty sequence *is* uniform — it just has no value to return,
so Optional can't distinguish the cases. In practice the inspector-UI and validation
uses both want `nil` for empty, and `Element?` is much nicer than `Element??`. Worth
confirming this is the right trade.
3. **Name.** Per the alternatives above, I'm interested in input here.
4. **Scope.** Should a companion `allEqual() -> Bool` ship at the same time, or is the
Optional sufficient?
Contributor guide
Research direction
The issue does not name implementation files or tests. Start by reviewing the package's existing projection APIs, especially chunked(on:) and chunked(by:), then resolve the open questions about naming, projection labeling, empty sequences, and scope before defining completion and tests.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- swift
- Domain
- tooling
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 38/100