Swift Digest
Reduce with inout
01 何が問題だったのか
Swift の Sequence には、要素を一つずつたたみ込んで単一の値にまとめる reduce メソッドがあります。従来の reduce は次のようなシグネチャを持ち、combine クロージャが毎回新しい結果を返す形になっていました。
extension Sequence {
func reduce<A>(_ initial: A, _ combine: (A, Iterator.Element) -> A) -> A
}
この形のままでは、結果を値型（たとえば Array や Dictionary）で持つ場合に、要素ごとに結果のコピーが発生しえます。とくに要素を追加していくようなケースでは、クロージャ内で新しい配列を作って返す必要があり、計算量の観点でも書き心地の観点でも扱いづらいという問題がありました。
たとえば、隣接する重複要素を取り除く uniq を従来の reduce で書くと、次のようにクロージャ内で result + [element] を返す形になります。
extension Sequence where Iterator.Element: Equatable {
func uniq() -> [Iterator.Element] {
return reduce([]) { (result: [Iterator.Element], element) in
guard result.last != element else { return result }
return result + [element]
}
}
}
result + [element] は毎回既存の配列をコピーして新しい配列を生成するため、全体の計算量は O(n^2) になってしまいます。本来なら append で済む処理が、reduce の形に合わせるために非効率になっている状態です。
また、Dictionary のように mutating なメソッド（添字代入など）で更新するのが自然な型を扱う場合にも、従来の reduce では一度クロージャ内で var のコピーを作り、最後にそれを return する、という冗長な書き方を強いられます。
extension Sequence where Iterator.Element: Hashable {
func frequencies() -> [Iterator.Element: Int] {
return reduce([:]) { (result, element) in
var result = result // コピーを作って
result[element, default: 0] += 1
return result // 返す必要がある
}
}
}
このように、既存の reduce は「結果を徐々に組み立てる」用途に対して、効率面でも記述面でも最適とは言えない状況でした。
02 どのように解決されるのか
Sequence に、結果を inout で受け取る新しい reduce のオーバーロードが追加されます。既存の reduce は残したまま、最初の引数に into: というラベルを付けた別メソッドとして提供されます。
extension Sequence {
func reduce<A>(
into initial: A,
_ combine: (inout A, Iterator.Element) -> ()
) -> A {
var result = initial
for element in self {
combine(&result, element)
}
return result
}
}
クロージャは結果の値を返すのではなく、inout で渡された result をその場で変更します。呼び出し側から見ると、「initial を起点に、各要素で結果を更新していく」という素直なモデルになります。
使い方
隣接する重複を取り除く uniq は、新しい reduce(into:_:) を使うと append で直接結果を伸ばせるようになり、計算量も O(n) に収まります。
extension Sequence where Iterator.Element: Equatable {
func uniq() -> [Iterator.Element] {
return reduce(into: []) { (result: inout [Iterator.Element], element) in
if result.last != element {
result.append(element)
}
}
}
}
inout の配列は、オプティマイザによって実質的にミュータブルな変数として扱われるため、毎回配列をコピーし直すコストが発生しません。
Dictionary を組み立てる場合も、添字経由の代入をそのまま書けます。要素の出現頻度を数える frequencies は次のように書けます。
extension Sequence where Iterator.Element: Hashable {
func frequencies() -> [Iterator.Element: Int] {
return reduce(into: [:]) { (result: inout [Iterator.Element: Int], element) in
if let value = result[element] {
result[element] = value + 1
} else {
result[element] = 1
}
}
}
}
従来の reduce のように「var のコピーを作ってから return する」という手順は不要です。
既存の reduce との関係
この変更は純粋な追加であり、既存の reduce(_:_:) はそのまま残ります。combine 内で mutating な操作を行わないアルゴリズム（たとえば数値の総和のように、結果を関数的に合成していくもの）には、引き続き従来の reduce が向いています。一方、配列や辞書のように「少しずつ要素を足していく」処理には、新しい reduce(into:_:) を使うのが自然です。
引数ラベルが into: で区別されるため、型推論への負荷もかからず、用途に応じて両者を使い分けられます。