Swiftでhead、tailにパターンマッチできる遅延リスト

関数型言語のように `head` と `tail` にパターンマッチでき、かつ遅延評価して無限リストを扱える `List` のライブラリ [_ListK_](https://github.com/koher/ListK) を Swift で作りました。

```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_](https://github.com/thoughtbot/runes) の演算子と互換性がある
- ネストした `reduceRight` でも遅延評価が働く
- リストだけのシンプルなライブラリになっている（余計なものが入らない）

## Listをhead、tailにパターンマッチできて何がうれしいか

Haskell などの関数型言語では、リスト（配列のようなもの）とパターンマッチングを多用します。そのためにはリストを `head` （先頭の要素）と `tail` （残りの要素）にパターンマッチすることが欠かせません。

たとえば、リストの要素の和を求める関数 `sum` は Haskell ではパターンマッチングを使って次のように書けます。最初の行はシグネチャの宣言なので、中身は 2 行目と 3 行目の 2 行だけです。

```haskell
-- 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 でパターンマッチングを使わずに書こうとすると、次のようなコードになってしまいます。

```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` にパターンマッチすることができます。

```swift
enum List<Element> {
    case None
    case Some(Element, () -> List<Element>)
}
```

_ListK_ を使えば、Haskell のコードと同じくパターンマッチングを使って `sum` を実装することができます。

```swift
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が遅延評価されると何がうれしいか

リストが遅延評価されると、無限リストを扱うことができます。

```swift
let infinite: List<Int> = List { $0 } // [0, 1, 2, 3, 4, ...]
```

リストから要素を取り出すときに初めて値が評価されるので、無限の領域を確保しなくても無限リストを実現することができるのです。

しかし、無限に要素を返すイテレータのようなものを作るくらいならそれほど難しくないでしょう。リスト全体で一貫して遅延評価するように実装することで、 `map` や `filter` などの操作を無限リストに適用できるようになります。 `map` や `filter` はリスト全体に対する操作なので、一見無限リストを適用すると永久に処理が終わらないように思えます。しかし、遅延評価があれば `map` の変換や `filter` の判定は実際に要素を取り出すときに初めて実行されるので、先行して無限に計算をする必要はありません。

```swift
let mapped: List<Int> = infinite.map { $0 * $0 } // [0, 1, 4, 9, 16, ...]
```

無限リストを使うときは、そのままでは無限ゆえに使えないことが多いので、 `take` などのメソッドを使って必要な要素を取り出して使います。

```swift
// 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 人を取り出したいとします（画面にユーザーのリストを表示してページングするような処理を考えて下さい）。その場合、次のようなコードで書けます。

```swift
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 ページ目を表示するには次のようにします。

```swift
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` を使って実装することができます。

```swift
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` が実行できません。

```swift
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` の第二引数を関数とすることで、ネストしても途切れず遅延評価が働くようにしています。

```swift
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_](https://github.com/thoughtbot/runes) です。演算子には優先順位や結合があるので、同じ演算子を複数のモジュールで宣言して優先順位が異なるなどすると衝突の可能性があります。みんなが _Runes_ を使っていればそういう問題も起こらないわけです。

モナド的なものを作ろうとするとそれらの演算子は頻出します。 [_antitypical/Result_](https://github.com/antitypical/Result) や [_robrix/Either_](https://github.com/robrix/Either) 、  [_thoughtbot/Argo_](https://github.com/thoughtbot/Argo) の `Decoded` 、僕が作った [_koher/PromiseK_](https://github.com/koher/PromiseK) なんかでも実装されています。

_ListK_ では `List` に対して `>>-`, `<*>`, `<^>` などのメソッドを実装しています。

```swift
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](https://github.com/thoughtbot/Curry) で実装されているような関数を想定しています。

## 問題点

主に再帰を使って実装されているため、コールスタックが深くなるとスタックオーバーフローになってしまいます。

```swift
sum(List { $0 }.take(100000)) // スタックオーバーフロー
```

こればかりはどうしようもないですが、多くのケースでは問題なく使えるのではないかと考えています。