ポエム
Swift

【考察】なぜ Swift に `popLast()` があって `popFirst()` がないのか

さらにいうと、なぜ Swift に remove は removeFirst()removeLast() もあるのに、pop は popLast() しかなく、popFirst() がないのか。

※本記事はあくまで個人的な考察であり、公式見解ではありません。

実は今日 Slack で @bannzai さんからこんな質問をいただきました:

Array に popFirst ってメソッド無いんだけど、生やすのはご法度なのかな

直感的に「おそらくそれは意図的に入れなかったので、自分で使う分には拡張で作っても問題ないけど多分 Proposal に出しても通らない」と思ったけど、なぜなのかはすぐには答えられなかったので、考えてみました。

popLast()removeLast() は、何が違うのでしょう?

まず、両方とも配列から最後の要素を取り外しす操作です。つまり、コードで書くと、こんな風になります:

var a = [1, 2, 3]
a.removeLast() // a == [1, 2]
a.popLast() // a == [1]

では、何が違うかというと、removeLast() は、配列に要素がなかったら、ない要素を削除しようとしてランタイムで落ちます1が、popLast() はそのまま配列に何も操作を加えず落ちません。

それだけか?

実はもうちょっと両方深掘りしてみると、面白いことに、両方とも戻り値があって、削除された値を返しています。removeLast() の方は @discardableResult の修飾子があるので戻り値を使わなくてもワーニング出ませんが。

Swift ではどういう時に @discardableResult 使うかというと、普通の戻り値があるメソッドはインスタンスに何かの操作を加えることなく、計算した結果を戻り値として返すのが本来の目的ですが、時にはインスタンスに何か操作を加えるのが本来の目的だが、ついでに戻り値がおまけとしてつくメソッドがあります。そういうメソッドに @discardableResult を宣言に入れることによって、コンパイラに「このメソッドを読んだけど戻り値ははあくまでおまけだから使わなくてもいいよ」ということを教えます。そして removeLast() だけでなく、removeFirst()@discardableResult メソッドです。

そして popLast() の戻り値は Element? になっているのに対し、removeLast() の戻り値は Element です。空配列に removeLast() 呼ぶと返す Element がないから落ちるのも当然ですね。

ではなぜ、Element? を返す popFirst() がないのか?

いいえ、正確には popFirst() は Swift に存在しているのです。多くの人がそれが気づいていないかもしれませんが。

しかし、上記のコード、a.popFirst() を書こうとしてもコンパイルエラーになります。なぜなのか。

上のリンクをもうちょっと詳しくみてみると、その外に extension Collection where SubSequence == Self が書いてあるのを気づけます。ここのミソはまさに最後の where SubSequence == Self の制約です。通常の ArraySubSequenceArray ではなく ArraySlice ですので、この制約に満足せず、だから popFirst() が使えません。

なぜ popFirst() だけこの制約があるのか。

この謎をとくためには、removeFirst()removeLast() の違いを見てみる必要があります。

この二つのメソッド、「最初を削除か最後を削除か」だけの違いに見えるかもしれませんが、実はもう一つの違いがあります。複雑度です。removeLast() は $O(1)$ であるに対し、removeFirst() は $O(n)$ です

なぜこのようになっているのかは具体的に SIL 読んでないのであくまで推測ですが、配列の最後の要素を削除するには最後の要素をメモリからクリアするだけで終了ですが、最初の要素を削除するには最初の要素をメモリから削除したあと、その後の全ての要素を 1 個ずつ前のメモリに移す必要があります(もしくは別のメモリ容量を確保して丸ごとそっちのメモリに移す必要があります)。そのため、大して違わない操作に見えても、最終的にマシンコードに落とし込んだらパフォーマンスが全く違います。removeFirst()popFirst() も、配列の操作においては同じことをするので、パフォーマンスには同じものになると推測できます。

じゃあなぜ Array において remove には removeFirst() があるのに pop に popFirst() がないのか、それはまた remove 系の戻り値と、pop 系の戻り値の違いに理由があるのではないかと、個人的に思います。

-> Element の戻り値と -> Element? の戻り値、ほぼ同じようですが、ユースケースとして一つ大きな違いがあり、Optional には Optional Binding という機構がありますので、それを利用した Flow Control は Swift では多く見られます。そしてさらにそれをループ条件に組み込むことができ、while let value = optionalValue でループが組めます。これは非 Optional ではできないことです。

そしてループは当然繰り返し演算ですので、複雑度は $O(n)$ です。この $O(n)$ の複雑度を維持してこれ以上複雑にならないためには、ループ条件が $O(1)$ である必要があります。しかし popFirst() は前述通り、Array の場合 $O(n)$ になりますので、ループ条件に組み込むのはあまり適しているとは言い難いです。

ちなみに、無理やりこの $O(n)$ の popFirst() をループ条件に組み込んだらどうなるのかというと、$O(n)$ のループが回る度にさらに $O(n)$ の処理を行いますので、$O(n^2)$ の複雑度になります2

そして上の popFirst() の実装のリンクをクリックしてみると分かりますが、その popFirst() は $O(1)$ だと説明されています。なぜそうなっているかというと、中身の実装は self = self[index(after: startIndex)..<endIndex] となっています。CollectionsubscriptSubSequence を取得できますが、SubSequence が自分自身の型ととな時である場合、メモリ上の複雑な操作はないと推測されるため $O(1)$ 複雑度に維持できると推測できます。この popFirst() は $O(1)$ の複雑度だからこそ、Optional の戻り値を持つメソッドとして組み込むことが許されたと思われます。

では、それでも popFirst() を使いたい、しかもまさにその while let first で使いたい場合はどうすればいいのか?答えは簡単です。ArraySubSequenceArraySlice ですが、ArraySliceSubSequence は自分と同じく ArraySlice です。ですので、ArraySlice を一回作っちゃえばいいです:

let a = [1, 2, 3]
var sliceA = ArraySlice(a)
while let first = sliceA.popFirst() {
    print(first) // 1; 2; 3;
}

  1. 正確にはコンパイルが -Ounchecked の場合なら落ちませんが 

  2. popFirst() のたびに配列の要素が一つ減るので、通常の $O(n^2)$ よりは少しマシになりますが(参考リンク)