SE-0515 | Swift Evolution↗

Allow `reduce` to produce noncopyable results

Proposal: SE-0515↗
Authors: Ben Cohen
Review Manager: Joe Groff
Status: Accepted

01 何が問題だったのか

Sequence の reduce(_:_:) と reduce(into:_:) は、初期値と累積結果を使ってシーケンスをひとつの値に畳み込むための API です。従来これらのメソッドは、結果型 Result に対して暗黙に copyable であることを要求していました。例えば reduce(_:_:) の既存の実装は次のようになっています。

func reduce<Result>(
  _ initialResult: Result,
  _ nextPartialResult:
    (_ partialResult: Result, Element) throws -> Result
) rethrows -> Result {
  var accumulator = initialResult
  for element in self {
    accumulator = try nextPartialResult(accumulator, element)
  }
  return accumulator
}

initialResult は非イニシャライザ引数のデフォルトである borrow で受け取られ、実装の最初のステップとして var accumulator = initialResult とコピーしてミュータブルな変数を作っています。このコピー前提の実装では、non-copyable な型を累積結果にできません。

一方、non-copyable 型は SE-0390 で導入されて以降、型の意味や性能を細かく制御するための強力な手段として使われており、畳み込みの累積結果としても自然に登場します。しかし、アキュムレータがコピーできない型だと var accumulator = initialResult の時点でコンパイルが通らず、せっかくの reduce が使えませんでした。

また、copyable な型に限って見ても、現在の borrow ベースの呼び出し規約には無駄があります。initialResult は呼び出された直後にどのみちコピーされますし、nextPartialResult の partialResult も借用して受け取って新しい値を返す形になっているため、毎ステップで借用・コピー・返却が発生します。多くの呼び出しでは初期値が reduce のためだけに作られており、そのまま所有権を渡してしまえば余分なコピーは不要です。

02 どのように解決されるのか

Sequence.reduce(_:_:) と reduce(into:_:) を、結果型 Result が non-copyable（~Copyable）でも使えるように一般化し、あわせて reduce(_:_:) の initialResult を consuming で受け取るように変更します。

extension Sequence {
  public func reduce<Result: ~Copyable>(
    _ initialResult: consuming Result,
    _ nextPartialResult:
      (_ partialResult: consuming Result, Element) throws -> Result
  ) rethrows -> Result

  public func reduce<Result: ~Copyable>(
    into initialResult: consuming Result,
    _ updateAccumulatingResult:
      (_ partialResult: inout Result, Element) throws -> ()
  ) rethrows -> Result
}

`reduce(_:_:)` の新しい実装

initialResult を consuming で受け取るようになったことで、コピーして新しい変数に受け直す必要がなくなり、そのまま累積用の変数として使えます。

public func reduce<Result: ~Copyable>(
  _ initialResult: consuming Result,
  _ nextPartialResult:
    (_ partialResult: consuming Result, Element) throws -> Result
) rethrows -> Result {
  for element in self {
    initialResult = try nextPartialResult(initialResult, element)
  }
  return initialResult
}

nextPartialResult のクロージャも partialResult を consuming で受け取り、新しい値として返すため、累積結果は毎ステップで所有権ごと引き継がれます。借用してコピーを返すような実装と違い、同じ値が書き換えられながら使い回される形になります。

copyable な型での呼び出し感

結果型が copyable な場合でも、動作は従来と変わりません。呼び出し側が値を手放してよい文脈（最後の使用など）では、オプティマイザがコピーを省略できます。初期値が reduce のためにその場で作られるケースが多いため、この最適化は実際によく効きます。

non-copyable なアキュムレータでの利用例

non-copyable な型を累積結果として reduce に渡せるようになります。例えば、~Copyable な FileHandle 風の型にシーケンスから書き込んでいくような処理が、reduce で素直に表現できます。

struct FileHandle: ~Copyable {
  consuming func write(_ line: String) -> FileHandle {
    // 書き込んで自身を返す
    return self
  }
}

let lines = ["a", "b", "c"]
let handle = lines.reduce(FileHandle()) { h, line in
  h.write(line)
}

`reduce(into:_:)` との関係

reduce(into:_:) はもともと initialResult を consuming で受け取っていたため、今回の変更は Result: ~Copyable の追加だけです。reduce(_:_:) が新しい実装では reduce(into:_:) とほぼ等価になるため、どちらを使うかは主にエルゴノミクスの問題になります。例えば Array への append を使った古典的な「世界一遅い map」も、次のように書き直せば reduce(into:_:) と同じ性能で動きます。

// 従来（二次オーダーになる書き方）
array.reduce([]) { $0 + [$1] }

// 新しい reduce(_:_:) での書き方
array.reduce([]) { $0.append($1); return $0 }

// reduce(into:_:) を使う書き方（従来から利用可能）
array.reduce(into: []) { $0.append($1) }

ただし、+ を使った書き方が二次オーダーになる原因のうち、今回の変更で解消されるのは「アキュムレータの不要なコピー」だけです。+ が引数を borrow して毎回新しい配列を作ってしまう点や、[$1] で一時的な配列バッファが確保されてしまう点は引き続き残ります。

今後の展望

Future Direction として、reduce を ~Escapable な値にも対応させる可能性が挙げられています。実現には関数本体とクロージャ引数の両方に lifetime annotation が必要で、後者は現時点の Swift ではまだサポートされていません。あくまで将来的な方向性であり、現時点で保証されるものではありません。

Allow reduce to produce noncopyable results