Swift Digest
Add Collection Conformances for enumerated()
01 何が問題だったのか
Sequence の enumerated() メソッドは、要素にインデックス（正確には 0 から始まるオフセット）を付けた (offset: Int, element: Element) のペアの列を返します。ただし、その戻り値である EnumeratedSequence は Sequence にしか適合しておらず、Collection 以降のコレクションプロトコルには適合していませんでした。
そのため、元が Collection や BidirectionalCollection / RandomAccessCollection であっても、enumerated() を通した時点でコレクションとしての性質が失われ、次のような不都合が生じていました。
(1000..<2000).enumerated().dropFirst(500)のような操作が、本来なら定数時間で済むにもかかわらず、先頭から順に要素を読み飛ばす線形時間の操作になってしまいます。"abc".enumerated().reversed()のように列を反転しようとすると、軽量なReversedCollectionを返せず、新たに配列を確保してそこに要素を積み直すことになります。- SwiftUI の
ListやForEachのようにCollectionを要求するビューに、enumerated()の結果を直接渡すことができません。
もともと EnumeratedSequence に Collection 適合を追加できなかったのは、Sequence.SubSequence の要件（SE-0234 以前）や、protocol conformance に @available を付けられなかったという標準ライブラリの ABI 上の制約が理由でした。これらの制約が解消された現在では、後方互換性を保ったまま適合を追加できるようになっています。
02 どのように解決されるのか
EnumeratedSequence に対し、ベースとなる列 Base のコレクション適合に応じた条件付き適合を追加します。具体的には次の 3 つです。
@available(SwiftStdlib 6.1, *)
extension EnumeratedSequence: Collection where Base: Collection { /* ... */ }
@available(SwiftStdlib 6.1, *)
extension EnumeratedSequence: BidirectionalCollection
where Base: BidirectionalCollection { /* ... */ }
@available(SwiftStdlib 6.1, *)
extension EnumeratedSequence: RandomAccessCollection
where Base: RandomAccessCollection {}
これにより、ベースがコレクションであれば enumerated() の結果もそのままコレクションとして扱えるようになり、「問題」で挙げた不都合は解消されます。
// dropFirst が定数時間になります。
let tail = (1000..<2000).enumerated().dropFirst(500)
// ReversedCollection が返り、配列の確保を伴いません。
let reversed = "abc".enumerated().reversed()
// SwiftUI にもそのまま渡せます。
ForEach(Array(items.enumerated()), id: \.offset) { offset, item in
// 従来はこのように Array でくるむ必要がありましたが、
// 今後は enumerated() の結果を直接渡せます。
}
BidirectionalCollection 適合の条件
BidirectionalCollection については、「Base: BidirectionalCollection」と「Base: RandomAccessCollection」のどちらを条件にするかが設計上のポイントでした。EnumeratedSequence.Index にはベースのインデックスに加えてオフセット（Int）が含まれるため、末尾から 1 つ前のインデックスを求める index(before: endIndex) では、オフセットを計算するためにベースの count が必要になります。count はベースが RandomAccessCollection なら O(1) ですが、単なる BidirectionalCollection では O(n) です。
本 proposal では、より多くの型で BidirectionalCollection 由来のアルゴリズム（reversed() や suffix(_:) など）や、その効率的な特殊化が使えることを優先し、条件を Base: BidirectionalCollection としています。その結果、last のような末尾参照は、ランダムアクセスでないベースに対しては O(n) となる点に注意が必要です。
// 双方向だがランダムアクセスではないコレクション。
let evenNumbers = (0 ... 1_000_000).lazy.filter { $0.isMultiple(of: 2) }
let enumerated = evenNumbers.enumerated()
// endIndex 自体の取得は O(1) ですが...
let end = enumerated.endIndex
// ...末尾要素の参照は O(n) です。
let lastElement = enumerated.last!
ただし O(n) になるのは「末尾インデックスを起点にした後退」に限られ、reversed() を通した反復全体は従来どおり O(n) に収まります。O(n²) まで悪化するような落とし穴はありません。
LazySequenceProtocol は伝播させない
EnumeratedSequence に LazyCollectionProtocol（および LazySequenceProtocol）適合を追加することは見送られました。.lazy.enumerated().filter { ... }.map(\.element) のようなチェーンで enumerated() から先が lazy として扱われるようになると、戻り値型が [Element] ではなく LazyMapSequence<...> になり、既存コードをソースレベルで破壊するおそれがあるためです。今回の適合追加はコレクションプロトコルに限定され、lazy 性の伝播は従来どおり enumerated() の手前までで止まります。