Swift 4の新しいreduceが素晴らしいので紹介する

これまでの reduce は次のようなシグネチャでした。

func reduce<T>(_ initial: T, _ combine: (T, Element) throws -> T) rethrows -> T

Swift 4 ではこれに加えて次のような reduce が加わることになりました（ SE-0171 ）。

func reduce<T>(into initial: T, _ combine: (inout T, Element) -> ()) -> T

この新しい reduce は、これまでの reduce の抱えていた問題を鮮やかに解決してくれるものなので、その素晴らしさについて説明します。

これまでのreduceの問題点

reduce を使って Array を生成する場合を考えてみます。たとえば、 [2, 3, 5] という Array があったときに [2, 2+3, 2+3+5] のように、その要素とそれまでの要素の合計値を格納した Array を作りたいとします¹。

そのような処理は reduce を使って↓のように書けます。

[2, 3, 5].reduce([]) { $0 + [($0.last ?? 0) + $1] }

しかし、 reduce を使って Dictionary を生成しようとするとうまくいきません。たとえば、 User の Array があったときに、 User の id から User を引けるような [Int: User] な Dictionary を生成したいとしましょう。

users.reduce([Int: User]()) {
	var result: [Int: User] = $0
	result[$1.id] = $1
	return result
}

なんと、 5 行になってしまいました。これには三つの問題があります。

1. 書きづらい
2. 可読性が低い
3. パフォーマンスが悪い

1 については単純に、 Array の生成なら 1 行で書けるコードが 5 行にも膨れ上がってしまい書きづらいということです。

2 については、 id → User へのマッピングをするというというのが本質的な処理なのに（ result[$1.id] = $1 ）、クロージャ式の中にそれ以外の処理（ var result: [Int: User] = $0, return result ）がごちゃごちゃと書かれており、ぱっと見でこのコードが何をしたいのかわかりづらいということです。

3 については、 result[$1.id] = $1 の時点でこの Dictionary （の内部的なバッファ）への参照が二つ（ $0 と result ）存在しており、 Copy-on-Write による最適化が働かず、この代入によって Dictionary 全体がコピーされてしまう可能性があります。そうすると id → User のマッピングは本来 O(N) でできる処理なのに、 O(N^2) になってしまいます²。

ありきたりな解決策

解決策として真っ先に思い浮かぶのが、 Array の + と同じようなものを Dictionary にも作ればいいんじゃないかということです（ただし、問題 3 は解決できないです）。

func +<Key: Hashable, Value>(lhs: [Key: Value], rhs: (Key, Value)) -> [Key: Value] {
	var result = lhs
	result[rhs.0] = rhs.1
	return result
}

この + があれば、前述の id → User のマッピングは次のように 1 行で書けます。

users.reduce([Int: User]()) { $0 + ($1.id, $1) }

めちゃくちゃシンプルになりましたね。

この + のような考え方は関数型的なイミュータブルプログラミングの発想です。つまり、 Dictionary に変更を加えたいときにそのインスタンスを変更するのではなく、変更が加えられた新しい Dictionary インスタンスを丸ごと作り直すというものです³。

新しいreduceによる解決策

イミュータブルプログラミングは最近のプログラミングの一つの潮流ではありますが、 Swift ではイミュータブルにこだわる必要はありません。なぜなら、 Swift は値型中心の言語で、ミュータブルな値型はイミュータブルな参照型と等価だからです（参考 1, 参考 2 ）。

新しい reduce はそんな値型の特性を使って鮮やかに問題を解決します。まずは、 id → User のマッピングが新しい reduce でどのように書けるのか見てみましょう。

users.reduce(into: [Int: User]()) { $0[$1.id] = $1 }

クロージャ式の中が $0[$1.id] = $1 だけでとても直感的です。まさに id → User のマッピングを表しています（問題 1, 2 の解決）。

reduce は元々関数型言語由来のもので、イミュータブルプログラミングと相性の良いように作られていました。これまでの reduce は処理の結果を combine の戻り値で返す必要があり、 Dictionary を組み立てる過程で新しい要素を追加する度に新しい Dictionary インスタンスを生成しなおす必要がありました。

新しい reduce は combine の戻り値で結果を返すのではなく、上記のように combine の引数に対して変更を加えることで結果を生成します。おもしろいのは、新しい reduce の combine の第 1 引数が参照渡しされる（ inout で渡される）ことです。

func reduce(into initial: T, _ combine: (inout T, Element) -> ()) -> T

結果 `T` が値型の場合、 `inout` でなければ第 1 引数に対して変更を加えてそれを結果に反映させることができません。 `combine` の第 1 引数が `inout` になっていることで、次のようなコードと等価のことができるわけです。

```swift
var result: [Int: User] = [:]
for user in users {
	result[user.id] = user
}

inout で直接結果の Dictionary に変更を加えているので、パフォーマンス上の問題も上記の for ループで書いたコードと等価です。クロージャをコールするオーバーヘッドについても、最適化によってクロージャ式がインライン化されることによって、なくなることが期待できます（問題 3 の解決）。

また、 for ループで書いた場合には minumumCapacity を指定して内部バッファの無駄なアロケートを避けることができますが、新しい reduce であればそれと同様の恩恵を受けることができます⁴。

users.reduce(into: [Int: User](minimumCapacity: n)) { $0[$1.id] = $1 }

なお、 Array の生成についてもパフォーマンス向上のために新しい reduce を使って書いた方が望ましいです。

[2, 3, 5].reduce(into: []) { $0.append(($0.last ?? 0) + $1) }

余談

この新しい reduce は、 try! Swift 2016 で来日された Chris Eidhof さんによって提案されたものです。 Chris さんは Functional Swift の著者でもあり、 Haskell 等の関数型言語に造詣が深い方です。そんな Chris さんが関数型的な手法にこだわらず、 Swift の値型の特性を利用した巧妙な提案をしているのを見て感銘を受けました。僕は、クロージャの引数を inout にするという方法は考えもしませんでした。 inout はどちらかと言えば避けるべきものという印象でしたが、今回の一件で値型との相性の良さを実感することができました。

まとめ

Before:

users.reduce([Int: User]()) {
	var result: [Int: User] = $0
	result[$1.id] = $1
	return result
}

After:

users.reduce(into: [Int: User]()) { $0[$1.id] = $1 }

これによって次の問題が解決できます。

1. 書きづらい
2. 可読性が低い
3. パフォーマンスが悪い

---

1. [2, 2+3, 2+3+5] のような Array の生成は例のための意味のない処理ではありません。このような Array を作っておくと、元の Array のある範囲の要素の和を O(1) で計算することができるようになります。たとえば、元の Array を array 、 [2, 2+3, 2+3+5] のような Array を integral とすると、 array[start...end].sum() の計算結果を integral[end] - integral[start - 1] で得ることができます。このような手法は 2 次元に拡張されて画像処理で多用され、 Integral image と呼ばれます。 ↩

2. ただし、 Swift は Copy-on-Write 関係の最適化を内部で色々とがんばっているらしく、このような場合でも O(N) で実行できたりもします。ただ、その要件が（僕の知る限りは）明確に仕様化されていないので、それに依存したコードを書くのは気持ち悪さを払拭できません。 ↩

3. インスタンスを丸ごと作り直すと言うとパフォーマンスが悪そうですが、 Haskell 等では巧妙に工夫されていて、 O(log N) で辞書に要素を加えてインスタンスを作り直すことができます。 ↩

4. @norio_nomura さんより Discord でコメントいただき追記しました。ありがとうございました。 ↩