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

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

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

Swift 4 ではこれに加えて次のような `reduce` が加わることになりました（ [SE-0171](https://github.com/apple/swift-evolution/blob/master/proposals/0171-reduce-with-inout.md) ）。

```swift
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` を作りたいとします[^1]。

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

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

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

```swift
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) になってしまいます[^2]。

## ありきたりな解決策

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

```swift
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 行で書けます。

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

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

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

## 新しいreduceによる解決策

イミュータブルプログラミングは最近のプログラミングの一つの潮流ではありますが、 Swift ではイミュータブルにこだわる必要はありません。なぜなら、 Swift は値型中心の言語で、ミュータブルな値型はイミュータブルな参照型と等価だからです（[参考 1](http://qiita.com/koher/items/81767a345d5ed53c04b7#swift%E3%81%AEarray%E3%81%8C%E3%83%9F%E3%83%A5%E3%83%BC%E3%82%BF%E3%83%96%E3%83%AB%E3%81%A7%E3%82%82covariant%E3%81%AA%E3%81%AE%E3%81%AF%E3%81%AA%E3%81%9C%E3%81%8B), [参考 2](http://qiita.com/omochimetaru/items/7265e440418b38088ccb) ）。

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

```swift
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` で渡される）ことです。

> ```swift
func reduce<T>(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` であればそれと同様の恩恵を受けることができます[^4]。

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

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

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

## 余談

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

## まとめ

Before:

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

After:
	
```swift
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) で実行できたりもします](http://qiita.com/dankogai/items/9e19cd92f398f9780b35#comment-6cadb4c379585bed6a63)。ただ、その要件が（僕の知る限りは）明確に仕様化されていないので、それに依存したコードを書くのは気持ち悪さを払拭できません。

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

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