関数型言語のように head と tail にパターンマッチでき、かつ遅延評価して無限リストを扱える List のライブラリ ListK を Swift で作りました。
func sum(xs: List<Int>) -> Int {
switch xs {
case .None: return 0
case let .Some(x, xs): return x + sum(xs()) // x (head), xs (tail) にパターンマッチング
}
}
sum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]) // 55
次のような特徴のリストライブラリがほしかったのですが、なかなか見つからなかったので自作することにしました。
-
headとtailにパターンマッチできる - 遅延評価される
- thoughtbot/Runes の演算子と互換性がある
- ネストした
reduceRightでも遅延評価が働く - リストだけのシンプルなライブラリになっている（余計なものが入らない）
Listをhead、tailにパターンマッチできて何がうれしいか
Haskell などの関数型言語では、リスト（配列のようなもの）とパターンマッチングを多用します。そのためにはリストを head （先頭の要素）と tail （残りの要素）にパターンマッチすることが欠かせません。
たとえば、リストの要素の和を求める関数 sum は Haskell ではパターンマッチングを使って次のように書けます。最初の行はシグネチャの宣言なので、中身は 2 行目と 3 行目の 2 行だけです。
-- Haskell
sum :: [Integer] -> Integer
sum [] = 0
sum (x:xs) = x + sum xs
3 行目の x:xs は、リストの先頭の要素を x に、残りの要素を xs にマッチさせるということです。 sum (x:xs) = x + sum xs が言っているのは、 sum とは、リストの最初の要素 x と残りの要素の和 sum xs を足したものであるということです。もし、残りの要素が存在しなければ sum xs が 2 行目の sum [] にマッチするため、残りの要素の和は 0 になります。まるで、 sum の定義をそのまま書き下したようなシンプルなコードです。
もし、 Swift でパターンマッチングを使わずに書こうとすると、次のようなコードになってしまいます。
func sum(numbers: [Int]) -> Int {
var sum: Int = 0
for number in numbers {
sum += number
}
return sum
}
Haskell のコードに比べてずいぶん複雑です。コードの行数よりも、ループを使って sum に逐次 number を足して、という構造がです。ループして要素を一つずつ取り出すというのは配列の和を求めるという本質とは関係なく、配列の和を求めるために行っている副次的な手続きです。
このように、パターンマッチングを使えば、コードから本質的でない処理を省きシンプルに記述することができます。
ListK の List は次のように enum で実装されているため、 head と tail にパターンマッチすることができます。
enum List<Element> {
case None
case Some(Element, () -> List<Element>)
}
ListK を使えば、Haskell のコードと同じくパターンマッチングを使って sum を実装することができます。
func sum(xs: List<Int>) -> Int {
switch xs {
case .None: return 0
case let .Some(x, xs): return x + sum(xs())
}
}
.None と .Some という名前は Optional にならいました。他の候補としては、 .Nil と .Cons や .Empty と .Node などあったんですが、対になっているのと、一番意味がわかりやすかったので。
.Some の第二パラメータが List<Element> ではなく () -> List<Element> なのは遅延評価を実現するためです。そのため、↑のコードで xs を使うときに xs() となっています。
Listが遅延評価されると何がうれしいか
リストが遅延評価されると、無限リストを扱うことができます。
let infinite: List<Int> = List { $0 } // [0, 1, 2, 3, 4, ...]
リストから要素を取り出すときに初めて値が評価されるので、無限の領域を確保しなくても無限リストを実現することができるのです。
しかし、無限に要素を返すイテレータのようなものを作るくらいならそれほど難しくないでしょう。リスト全体で一貫して遅延評価するように実装することで、 map や filter などの操作を無限リストに適用できるようになります。 map や filter はリスト全体に対する操作なので、一見無限リストを適用すると永久に処理が終わらないように思えます。しかし、遅延評価があれば map の変換や filter の判定は実際に要素を取り出すときに初めて実行されるので、先行して無限に計算をする必要はありません。
let mapped: List<Int> = infinite.map { $0 * $0 } // [0, 1, 4, 9, 16, ...]
無限リストを使うときは、そのままでは無限ゆえに使えないことが多いので、 take などのメソッドを使って必要な要素を取り出して使います。
// take で先頭の 5 要素を取り出す
let taken: List<Int> = mapped.take(5) // [0, 1, 4, 9, 16]
infinite を take してから map するのではなく、 map してから take できたことに注目して下さい。 map や filter などの処理を無限リストのまま実行し、最後に take して利用できるところが遅延評価のパワーです。
たとえば、これが map でなく filter だったらどうでしょうか？仮に今、ユーザーのリスト users を持っているとしましょう。ユーザーの中から、特定のタグに興味がある人だけを残して、最初の 10 人を取り出したいとします（画面にユーザーのリストを表示してページングするような処理を考えて下さい）。その場合、次のようなコードで書けます。
let result: List<User> = users.filter { $0.tags.contains(tag) }.take(10)
遅延評価でなければ、 filter を実行した時点で（何億人いるかもしれない）ユーザー全体に対して filter の判定処理が働き、その後最初の 10 人だけ take することになってしまいます。それでは、ほとんどのユーザーに対する判定処理は無駄になってしまいます。遅延評価なら必要になるまで処理が走らないので、条件にマッチした最初の 10 人以上は処理が実行されません。
先に take して filter するというのはどうでしょうか？条件にマッチするユーザーがどれだけいるかわからないのに、先に take するのは難しいです。 10 人しか take しなかったら一人でも当てはまらなかったら 10 人を返すことができないですし、余分に take したら無駄が生じてしまうかもしれません。しかも、たとえ 100 人 take してから filter するとしても必ず 10 人返すことを保証することはできません。また他にも条件にマッチするユーザーがいるかもしれないのに、 1 ページ目に表示されるユーザーが 10 人未満になってしまう可能性を排除できません。
このように、遅延評価によって巨大なリストを効率よく操作できたり、無限リストすら操作をすることが可能になります。
ちなみに、↑のユーザーの例で 2 ページ目を表示するには次のようにします。
let result: List<User> = users.filter { $0.tags.contains(tag) }.drop(10).take(10)
ネストされたreduceRightと遅延評価
リストを扱う上で reduce, reduceRight は欠かせません。
関数型言語ではループを使わずパターンマッチングと再帰を使ってプログラムを書きますが、ループを表現するために再帰を使わずとも reduce, reduceRight を使えば解決する場合も多いです。 reduce, reduceRight は多様なケースに対応できる汎用的な高階関数（メソッド）です。
たとえば、 map も filter も reverse も contains もみんな reduce, reduceRight を使って実装することができます。
func map<T>(transform: Element -> T) -> List<T> {
return reduceRight(List<T>()) { x, xs in List<T>(head: transform(x), tail: xs()) }
}
func filter(includeElement: Element -> Bool) -> List<Element> {
return reduceRight(List()) { x, xs in includeElement(x) ? List(head: x, tail: xs()) : xs() }
}
func reverse: List<Element> {
return reduce(List()) { xs, x in List(head: x, tail: xs) }
}
func contains(element: Element) -> Bool {
return reduceRight(false) { x, contains in x == element || contains() }
}
特に、 reduceRight は無限リストに対しても利用できるので重宝します。しかし、 Swift では Foo を () -> Foo として扱うことで評価を遅延させ、さらに @autoclosure を組み合わせることで Foo を自動的に () -> Foo に包むことで遅延評価を実現するので、それに対応していないと reduceRight をネストするときに遅延評価が途切れてしまいます。
例えば、 flatten を実装するには次のように reduceRight をネストします。一段目で遅延評価が途切れてしまうと、無限リストに対する flatten が実行できません。
func flatten<Element>(xss: List<List<Element>>) -> List<Element> {
return xss.reduceRight(List<Int>()) { xs, flattened in
xs.reduceRight(flattened()) { x, flattened in
List(head: x, tail: flattened())
}
}
}
reduceRight はとても汎用的なメソッドなので、無限リストと複雑に組み合わせてもうまく動作してほしいところです。そこで、 ListK では次のように initial と combine の第二引数を関数とすることで、ネストしても途切れず遅延評価が働くようにしています。
func reduceRight<T>(@autoclosure(escaping) initial: () -> T, combine: (Element, () -> T) -> T) -> T {
switch self {
case .None:
return initial()
case .Some(let head, let tail):
return combine(head, { tail().reduceRight(initial, combine: combine) })
}
}
Haskellっぽい演算子
Haskell では、 flatMap は >>=, apply は <*>, map は <$> という演算子で表されます。
Swift ではそのままでは演算子に使えない文字があったり不都合があるので、 flatMap を >>-, apply を <*>, map を <^> という演算子で表すのが主流になっています。それらの演算子をモジュールごとにばらばらに宣言するのではなく、統一的に扱おうという目的で作られているのが thoughtbot/Runes です。演算子には優先順位や結合があるので、同じ演算子を複数のモジュールで宣言して優先順位が異なるなどすると衝突の可能性があります。みんなが Runes を使っていればそういう問題も起こらないわけです。
モナド的なものを作ろうとするとそれらの演算子は頻出します。 antitypical/Result や robrix/Either 、 thoughtbot/Argo の Decoded 、僕が作った koher/PromiseK なんかでも実装されています。
ListK では List に対して >>-, <*>, <^> などのメソッドを実装しています。
let xs: List<Int> = List { $0 } // [0, 1, 2, 3, 4, ...]
let ys: List<Int> = xs >>- { $0 % 2 == 0 ? [$0] : [] } // [0, 2, 4, 6, 8, ...]
let zs: List<Int> = curry(*) <^> [2, 3] <*> [5, 7] // [10, 14, 15, 21]
ただし、上記コードの curry は thoughtbot/Curry で実装されているような関数を想定しています。
問題点
主に再帰を使って実装されているため、コールスタックが深くなるとスタックオーバーフローになってしまいます。
sum(List { $0 }.take(100000)) // スタックオーバーフロー
こればかりはどうしようもないですが、多くのケースでは問題なく使えるのではないかと考えています。