SE-0094 | Swift Evolution↗

Add sequence(first:next:) and sequence(state:next:) to the stdlib

Proposal: SE-0094↗
Authors: Lily Ballard, Erica Sadun
Review Manager: Chris Lattner
Status: Implemented (Swift 3.0)

01 何が問題だったのか

Swiftでは、初期値から出発してクロージャを繰り返し適用しながら値をひとつずつ生み出していきたい場面がよくあります。たとえば、ある値を2倍しながら閾値まで並べていく、ビューの階層を親方向にたどる、といった処理です。

// 0.1, 0.2, 0.4, 0.8, ...（4 未満の間だけ）
// someView, someView.superview, someView.superview.superview, ...

しかし、Swift 2時点の標準ライブラリにはこの「畳み込みの逆」にあたる操作が用意されていませんでした。reduce(_:_:) はシーケンスを畳み込んで単一の値を得る操作ですが、その対をなす「単一の値からシーケンスを広げる（unfold する）」操作がなかったわけです。

さらに、SE-0007 でCスタイルの for ループが削除されたことで、「単純なカウントアップではない、非線形・非数値的な漸化式で値を並べる」書き方の受け皿が薄くなっていました。for-in と Range / stride では表しにくく、結局 while ループと可変な状態変数で書き下すしかない、という状況になりがちでした。

// 「ある要素から親をたどる」のような処理を書くために
// 毎回こうした手書きループが必要だった
var current: UIView? = someView
while let view = current {
  // view を使う
  current = view.superview
}

この操作はかつてSE-0045で iterate(_:apply:) / unfold(_:applying:) として提案されましたが、命名上の理由で却下されていました。機能自体の有用性は変わらず認められていたため、より Swift らしい名前を与えて再提案することが求められていました。

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

標準ライブラリにグローバル関数として sequence(first:next:) と sequence(state:next:) の2つを追加します。どちらも、初期値や状態にクロージャを遅延適用していく「潜在的に無限の」シーケンスを返します。

public func sequence<T>(first: T, next: (T) -> T?) -> UnfoldSequence<T>
public func sequence<T, State>(state: State, next: (inout State) -> T?) -> UnfoldSequence<T>

next クロージャが nil を返した時点でシーケンスは終了します。nil を返さなければ無限に値を生み続けます。名前は、関数型言語での定番である unfold ではなく、Swift で自然に読める sequence が採用されました（unfold はSwift利用者にとって意味が伝わりにくいと判断されたためです）。戻り値の型は UnfoldSequence という名前になっています。

`sequence(first:next:)` の使い方

first で指定した値を最初に返し、以降は直前の値にクロージャを適用した結果を順に返します。[first, next(first), next(next(first)), ...] というイメージです。

// 0.1 から 2 倍ずつ、4 未満の間だけ取り出す
for x in sequence(first: 0.1, next: { $0 * 2 }).prefix(while: { $0 < 4 }) {
  print(x)
}
// 0.1, 0.2, 0.4, 0.8, 1.6, 3.2

ビュー階層を親方向にたどる、といった処理も素直に書けます。next で nil を返せばそこで打ち切られるため、ルートまでの有限列として扱えます。

for view in sequence(first: someView, next: { $0.superview }) {
  // someView, someView.superview, ...（superview が nil になった時点で終了）
}

Haskell の iterate に相当しますが、Swift 版は next が nil を返したときに終わるので、常に無限列とは限らない点が違いです。

`sequence(state:next:)` の使い方

こちらは状態を inout でクロージャに渡し、クロージャが返した値をそのまま要素として流します。状態は next の中で自由に更新でき、nil を返したところでシーケンスが終了します。

// フィボナッチ数列を (前の値, いまの値) を状態として生成する
let fibs = sequence(state: (0, 1)) { (pair: inout (Int, Int)) -> Int? in
  let next = pair.0
  pair = (pair.1, pair.0 + pair.1)
  return next
}

for x in fibs.prefix(10) {
  print(x)
}
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Haskell の unfoldr に相当する操作ですが、状態を「返り値として返す」のではなく inout で受け渡す設計になっています。こうすることで、配列など値型の状態を扱う際に、不要なコピーオンライト（CoW）によるコピーが起きにくくなります。

sequence(first:next:) は sequence(state:next:) があれば原理的には表現できますが、単純に書き直すと評価が前のめりになりすぎてしまい（1要素先まで余分に計算してしまう）、正しく実装するのは見た目より面倒です。そのため、高頻度で使える形として両方を用意するという選択が取られています。

使いどころ

reduce(_:_:) の対として、初期値からシーケンスを「広げる」用途に。
SE-0007 で削除されたCスタイル for ループのうち、非線形な漸化式（2倍ずつ増やす、ノードをたどる、など）で値を並べるケースの置き換えに。
prefix(while:) / prefix(_:) / drop(while:) といった Sequence のメソッドと組み合わせれば、無限列を安全に切り出して使えます。

既存コードへの影響

純粋な追加であり、既存コードへの影響はありません。