はじめに
私はSoroushと言います。今日はみなさんが SequenceとCollection について知りたいことをすべてお話しします。
Swiftを使って開発をしていると、よく順序を持ったリストを使うことがあります。99%のケースでArrayを使うことになります。しかしArrayやSwiftにおける他のCollectionプロトコルに準拠しているものやCollectionオブジェクトは入念に考えられたプロトコルのヒエラルキー、関連型、それ以外のコンポーネントの組み合わせによる素晴らしい機能が整っています。今回は、このプロトコルを使って、どうやって求める機能を実装していくのかお話します。
誰もが知りたいSequenceとCollectionの”ほぼ”すべて
すべては Sequence というプロトコルの上に成り立っています。SequenceはArrayを操作する際のバックボーンを提供しています。例えば、mapやfilterを使うときや、Sequenceで最初の要素を取得するためのメソッドは、このSequenceというプロトコルにすべて定義されています。シンプルです。すべてSequenceの上に実装されています。残りのプロトコルレイヤーははしごのように互いに重なりあっています。 自分たちがやっていることはこのはしごの一部を通ることです。 次に、CollectionとBidirectionalCollectionについてお話しましょう(RandomAccessCollectionやRangeReplaceableCollection, MutableCollectionについては取扱いません)。
Sequence
一番下のレベルから始めましょう。Sequenceです(そのままです)。Sequenceは要素を持ったリストです。これには気をつけることが2つあります。 1, 有限か無限かのどちらかになること。2, 一度しかイテレーションできないことです。2回以上イテレーションできることもありますが、２回以上イテレーションされることは保証されていません。
protocol Sequence {
associatedtype Iterator: IteratorProtocol
func makeIterator() -> Iterator
}
Sequenceプロトコルには２つのコンポーネントがあります。ひとつはIteratorという関連型（associatedtype）です。この関連型は IteratorProtocol に準拠している必要があります。もうひとつは、Iteratorを生成する関数で、宣言したIteratorと同じ型となっている必要があります。
IteratorProtocol
IteratorProtocolについては、Sequenceと同じようにプロトコルをイテレーションするために、もう１レベル深く潜る必要があります。Elementという関連型があり、そのElementは保持したり、イテレーションしようとしている型です。また、nextという関数があり、次の要素を返してIteratorとなります。
protocol IteratorProtcol {
associatedtype Element
mutating func next() -> Element?
}
IteratorProtcolはSequenceを構成しているもので、Sequenceが扱うものすべてに提供しているバックボーンです。 LinkedList を説明するために、これをつくってみましょう。LinkedListはSequenceに構造がフィットしていていいものです。アイテムを見て、次のアイテムを探し、次のアイテムを見ると、その次のアイテムを探します。
Example: LinkedList
これはLinkedListの一例です。最初のエレメントが、2番目のエレメントを示し、2番目のエレメントが3番目のエレメントを示し、3番目のエレメントが最後を示しています。SwiftでSequenceやLinkedListを定義するためには、いくつかの方法がありますが、私は、 列挙体(enum) を使うのがいいと思っています。列挙体はTというジェネリクスの型変数を持っており、その型にはLinkedListが格納されます。もう一つあります。この indirectというキーワード です。 indirect はLinkedListNode型を自分自身の内部で使うことを意味しています。 (変なことをしていると思わないでください。)
LinkedListには2つのcaseがあります。1つめはvalueで、その型はTとなります。次のvalueがあることが保証されていて、LinkedList全体と全く同じ型になります。これは他のエレメントを指しており、最終的にすべてのエレメントを通過してendに当たったら、それはLinkedListが終わったことを意味します。
しかし、まだ何もできません。列挙出来ませんし、for n ループできません(forループのようなものです)し、mapやfilterもできません。このツールを使い始められるようにするために、LinkedListをSequenceに準拠させたいと思います。
Sequenceに準拠させるためには、 makeIterator という関数を作る必要がありますが、Iterator型がどのようになるのかまだわかりません。まだ関連型であるIterator型を追加していないことにお気づきでしょうか。Swiftでは、そこに型をいれれば、どの型を使うべきなのかは勝手に判断してくれます。イテレーションを行うのにいくつかオブジェクトの型が必要です。
LinkedListIteratorをつくります。このLinkedListIteratorはジェネリクスの型変数T型で、nextを実行すると、常にvalueを返します。このvalueはT型になり、LinkedListには入れたい型を入れることができます。IteratorもIteratorProtocolにも準拠しており、Sequence型の制約によってそれを満たすことができます。IteratorはSequenceをステップしていくため、カーソルとして機能し、シーケンスのどこにあるかを知っている状態でなければなりません。その状態はcurrentで表され、現在指しているLinkedListの現在のノードになります。そのノードは、Iteratorのように、ジェネリクスの型変数Tになります。
それから、Optional
そのためにはswitch文を用意します。LinkedListNode型であるcurrentを分岐し、2つのcaseをもたせます。片方のcaseはとても簡単です。LinkedListの終わりなら、nilを返すようにします。valueがあるなら、すなわちエレメントがあり、nextがあることを意味します。そのエレメントを返すのは分かっていますね(簡単です)。エレメントを返しているのはわかりますが、nextのvalueについてはどうしたらよいでしょうか。nextはLinkedListNodeが指している次のエレメントを表します。current変数をアップデートし、nextを代入します。これによって、次のnextがcurrentで分岐したときに呼ばれるようになり、currentは更新されて新しいvalueかnilを返すことによってSequenceが終了します。Sequenceに準拠する必要があるのはこれですべてです。 これでIteratorの型がLinkedListIteratorということがわかりますし、そこに置くことができ、LinkedListの先頭から始めるようにセットすることができます。selfがLinkedListの先頭となり、最初から始まります。これがSequence型に準拠する必要のあることすべてなのです。
indirect enum LinkedListNode<T> {
case value(element: T, next: LinkedListNode<T>
case end
}
extension LinkedListNode: Sequence {
func makeIterator() -> LinkedListIterator<T> {
return LinkedListIterator(current: self)
}
}
struct LinkedListIterator<T>: IteratorProtocol {
var current: LinkedListNode<T>
mutating func next() -> T? {
switch current {
case let .value(element, next):
current = next
return element
case .end:
return nil
}
}
}
Squence型によって、forループでイテレーションできますし、mapやfilterが使えるようになりました (Sequenceによって使えるようになるものは他にもたくさんあります！)。
Iteratorを図を用いて見てみましょう。先程のLinkedListがあり、3つのエレメントがあります。
let iterator = LinkedListIterator<String>(current: linkedList)
print(iterator.next()) // => “A”
When we create out Iterator it has a pointer to the first value which is that current. Next, we set up our current to access the head of our LinkedList. When we call iterator.next it will return A. Then, it will alupdate that reference current to point to the second element in the LinkedList.
let iterator = LinkedListIterator<String>(current: linkedList)
print(iterator.next())
print(iterator.next()) // => “B”
iteratorを生成するときには、currentに最初の値を示すポインタがあります。次に、LinkedListの先頭にアクセスするためのcurrentを準備します。 iterator.nextを呼ぶと、Aが返ります。その後、currentの参照がLinkedListの2番目のエレメントを指すように更新されます。
もう一度nextを呼ぶと、Bが返り、カーソルが移動し、LinkedListの次のエレメントを指すようになります。endにぶつかるまで続きます。endにぶつかるとnilが返ることになり、それ以降nextを呼び出すとnilが返ります。ですがすべてのSequenceに何か追加したいときはどうしたらいいでしょうか？
オブジェクトが大量にあって、そのうちの何個がテストに通ったのか知りたいときがありますよね。これはとても良い例です。filterしてtestに通過したエレメントの配列を取得し、countで数えます。これは悪くはありませんが、余分な配列を作り、数を数えたらすぐに捨てられることになります。これは理想的ではありません。users.countと書き、テストを通したいのです。これはもっと高価で、もしRubyを書いたことがあれば、Enumerableモジュールととても似ていることにお気づきになると思います。この方がより良いし、すべてのSquenceにこの関数を追加できます。
まず、Sequence型のextensionを作成します。ここに関数を追加して、countと命名したいと思います。この関数はIntを返します。さらに引数も渡さなくてはいけませんね。この引数を読みやすくするためにshouldCountとします。ここで重要なのは、Sequenceの内部にあるエレメントの型をIterator.Elementとすることです。これによって、StringでもUserオブジェクトでもどんな型が入っていてもどの型を保持しているのかわかります。Sequenceによって、何をイテレーションする必要があるのかわかりますし、これがSequenceに準拠することで得られるものです。このfor n ループにアクセスでき、このエレメントをイテレーションして、各エレメントを取得し、保持しようとしていることがわかります。
countを必要としていることもわかります。count変数に保持しようとしています。0から始まり、終わりで返します。for ループの間で起こっていることは魔法です。 shouldCountがあれば、そのテストを通り、今回のケースなら、ユーザーがadminだったら、countを1増やすようにすればいいこともわかります。かなり直感的です。
let numberOfAdmins = users.filter({ $0.isAdmin }).count // => fine
let numberOfAdmins = users.count({ $0.isAdmin }) // => great
extension Sequence {
func count(_ shouldCount: (Iterator.Element) -> Bool) -> Int {
var count = 0
for element in self {
if shouldCount(element) {
count += 1
}
}
return count
}
}
以上がすべてのSequenceにextensionを追加する方法でした。他の型と同じように開いて、extensionを追加し、Sequence内部の型をIterator.Elementで参照します。これでしたいことは何でもできます。とても役立つextensionです。私はこれをほとんどのプロジェクトに追加していますし、そのうち、Swiftの標準ライブラリに入るかもしれませんね。
もうひとつSequenceに加えると役に立つのが、”Each Pair”(と私が呼んでいるもの)です。これは連続したエレメントやグループのペアを一緒にひとつのタプルに入れます。これはNumberのSequenceがあり、Numberの違いを知りたい場合に便利です。それらをペアにまとめて、2つのペアを互いに引き算することができます。これは、Viewが複数あり、ViewとViewの間にAuto LayoutのConstraintを追加する場合にも便利です。 _あるView、次にこのView、次にまた別のViewを持つことができます._Viewをペアとして操作し、View間にConstraintを追加してから、次のペアを操作できます。
zip(sequence, sequence.dropFirst()) // Sequence<(T, T)>
これが標準ライブラリではどのように実装されているのか見てみましょう。標準ライブラリでは、Sequenceから始まります。Each Pairが必要であるという実感を得るには、別の参照でそのSequenceのコピーを作成し、そのコピーから最初のエレメントを削除する必要があります。次に、それを一緒にzipして、同じエレメントを組み合わせ、最後のエレメントがなくなるようにします。一度このペアを作ると、このカラムはすぐに使用できます。エレメントを組み合わると、魔法が起こります。 Boom! 今度は、この式zipと2つのSequenceを使ってペアをグループ化しました。さらに、チェーンできるSequenceのメソッドとしてそれを入れたいと思います。これをEach Pairと呼び、mapを実行し、filterを行い、他にしたいことをすべて行います。
extension Sequence
where Self.SubSequence: Sequence,
Self.SubSequence.Iterator.Element == Self.Iterator.Element {
func eachPair() -> AnySequence<(Iterator.Element, Iterator.Element)> {
return AnySequence(zip(self, self.dropFirst()))
}
}
先程用いたアプローチから始めます。eachPairという関数があり、これはタプルのSequence、この場合は2つのエレメントを返します。すべての余分なものを中にzipします。AnySequenceという余分なコンポーネントがあり、これは型消去となります(Gwen Westonの型消去のトークを見ることをオススメします)。これをコンパイルしても動きません。Swiftのコンパイルエラーは SubSequence という引数を指しています。Swiftのコンパイラの制限によって、どのSubSequenceもSequenceだということすら表現できないのです。この制約を実装するかは自分たち次第です。
「SubSequenceを持たせ、そのSubSequenceもSequenceだと保証する」という制約を追加します。これをコンパイルすると、別のエラーに遭遇します。expressionは返り値に変換できません。 つまらないエラーですが、重要なのは、２番目のSelf.SubSequence.Iterator.ElementがSelf.Iterator.Elementにマッチしないということです。つまり、SubSequenceを持っていて、そのSubSequenceはSequenceでもありますが、SubSequenceの中の型が自分自身と同じ型ということはわからないのです。もうひとつ制約を加える必要があります。
Self.SubSequence.Iterator.ElementはSelf.Iterator.Elementと同じという制約です。これでコンパイルできます。今後は、Each Pairを必要に応じて使用できますが、これらの関連型を扱うことは、Swiftのプロトコルとコレクションシステムを扱う苦労の一部です。うれしいのが、欲しいresultを得ることができるということです。 以上がSequenceでした.
Collection
Sequenceの後は、レベルをひとつあげて、Collectionに行きましょう。どんなCollectionもSequenceを継承していて、CollectionはSequenceの抱えている2つの問題を解決します。すべてのCollectinoは常に有限となります。これが何を意味しているかというと、そこにエレメントが何個あるのか常にわかるということです。無限には決してなれませんし、Collectionは何回でもイテレーションすることができます。Sequenceでは、1回しかイテレーションできませんでしたが、Collectionでは何度でもイテレーションできるので、とても優れています。
Collectionプロトコルを見てみましょう。
protocol Collection {
associatedtype Index: Comparable
var startIndex: Index
var endIndex: Index
subscript(position: Index) -> Iterator.Element { get }
func index(after index: Index) -> Index
}
主に新しく加わったのは、Indexという関連型です。このIndexはArrayに適用すると、Intのようにみなすことができます。すべてのCollectionがこれをもっており、Dictionary型は自身のindexを持っており、普段は使うことも気にすることはありませんが、直感的です。indexを取得すると、開始位置と終了位置をシステムに指示するために、startIndex と endIndex が必要です。配列の場合、startIndexは0になりますが、ArraySliceの場合は他の位置にある可能性があります。次に、そのindexでエレメントを取得できるようにします。 subscript関数を使用します。現在見ているcurrentIndexの後にindexを取得する必要があります。Iteratorを扱う必要はありません。Swiftがすべてやってくれます。
CollectionにおけるforEachを実装例として見てみましょう。
func forEach(_ block: (Element) -> Void) {
var currentIndex = self.startIndex
while currentIndex < self.endIndex {
block(self[currentIndex])
currentIndex = self.index(after: currentIndex)
}
}
これを実装する必要はありません。もうすでに作られていますが、これがその作り方です。currentIndexから始まり、endIndexより小さいかを判定します。これが関連型であるIndexがComparableに準拠していた理由です。endIndexより小さいかどうかを判定します。blockに現在の値を渡して呼び、次に現在の値を更新して次のindexを表示します。endIndexに当たるまでイテレーションし続け、その後イテレーションは終了します。 この4つの関数を自身で実装することなくSequenceからすべて入手できます。
extension APIErrorCollection: Collection {
var startIndex: Int {
return _errors.startIndex
}
var endIndex: Int {
return _errors.endIndex
}
func index(after index: Int) -> Int {
return _errors.index(after: index)
}
subscript(position: Int) -> APIError {
return _errors[position]
}
}
普段はスクラッチでCollectionを作ることはありませんが、ある型をCollectionとして機能させたいことがあります。今回は、APIErrorCollectionです。この型はAPIErrorの配列を内部に持っていますが、実現したいコードは、ErrorのCollectionをCollectionとして扱えるようにすることです。エラーのプロパティはprivateなので、これができません(中を調べることはできません。)。 自分で作ったAPIErrorCollectionもCollectionとして作りたいです。これがすべて自由に使えるのです。
struct APIErrorCollection {
fileprivate let _errors: [APIError]
}
extension APIErrorCollection: Collection {
// ...
}
errorCollection.contains({ $0.id == "error.item_already_added" })
// compiles!
これを行うには、extensionが必要です。または、APIErrorCollectionをCollectionに準拠させる必要があります。Collectionのすべてに準拠した内部プロパティが既に存在するため、すべてを内部プロパティに送ることができます。 startIndexは errors.startIndexになり、indexは errors.endIndexになります。index(after)は内部プロパティに送られ、subscriptも内部プロパティに送られます。 直接送っています。 配列ではないものを配列のように扱うためにこれを行います。次に、そのCollection内に何らかのエラーが含まれているかどうかを確認するコードを書きます。Sequenceのように、この4つのプロパティで自由にmap、filterしたりすることができるものが出来ました。
Bidirectional Collection
BidirectionalCollectionは1つを除いては、Collectionにとても近いものです。CollectionがSequenceを継承のと同じように、Collectionを継承しますが、BidirectionalCollectionは前方向だけでなく、後方向にも進むことができます。後方向に進ませる機能を加えるには、もうひとつ関数を追加する必要があります。Collectionには index(after)という関数がありますが、BidirectionalCollectionでは、index(before)という関数を新たに追加します。この関数は、Collectionを逆順でステップします。
protocol Collection {
//...
func index(after index: Index) -> Index
}
protocol BidirectionalCollection: Collection {
func index(before index: Index) -> Index
}
BidirectionalCollectionによって自由に使えるようになるものの例のひとつとして、lastというプロパティがあります。 これにより、BidirectionalCollectionの最後のエレメントを取得することができますし、もしCollectionが空なら、nilが得られます。Collectionにこれが実装できないのは、Collectionの終端まで通り抜けて、最後のエレメントを返すからです。とても時間がかかります。最後から一つ前に戻り、そのvalueを返したいのです。Collectionが空であるかどうかを確認する必要があります。空であれば、単純にnilを返すことができ、完了したことがわかります。次に、endIndexを使い、ひとつ前のindexを取得します。それが最後のエレメントの次の要素です。最後に、そのindexの値を返します。
var last: Iterator.Element? {
guard !self.isEmpty else { return nil }
let indexOfLastItem = self.index(before: self.endIndex)
return self[indexOfLastItem]
}
BidirectionalCollectionによって、Collectionをひっくり返すのが簡単になります。逆向きに進むからです。使いやすくなりますね。
その他のプロトコル
他にも3つのプロトコルがあります。
- RandomAccessCollectionは値への高速なアクセスを実現します。ひとつずつ通過していくのではなく、求めるエレメントに直接アクセスできます。
- RangeReplaceableCollectionを使用すると、Collectionの途中のチャンクを別のものに置き換えることができます
- MutableCollectionを使うと、値を得るだけでなく、セットもできます。
SwiftのドキュメントやSwiftdoc.orgを見ると、これらプロトコルを確認したり、その動作を実現するためにどのような新しい関数を実装する必要があるかを調べることができます。うまくいけば、今回で学んだことでこれらのプロトコルを理解することができます。
Q & A
Q: SwiftにIterator型があって、表現力があったら、その表現力をどこに活かすことができますか？ Soroush: ほとんどの場合、Iterator型は、何かを作っているときやSwift標準ライブラリが使用するときに内部で使用されます。これに関しては心配する必要はありませんが、手動で何か進めるたいような時でも使うことができます。手動で何かを実行していたり、そうですね、ここでは違うページにスワイプしているとしましょう。毎回Collectionやindexを保持するのではなく、Iteratorを保持し、スワイプするたびにnextを呼び出すと、次の要素が表示され、次のスワイプが次に呼び出されます。このように表現力を高めるためにIterator型を使用します。
About the content
2017年3月のtry! Swift Tokyoの講演です。映像はRealmによって撮影・録音され、主催者の許可を得て公開しています。
