Swiftのmap, filter, reduce, etc...は(あたりまえだけど)for, if, switch, whileからできている

## はじめに
Swiftで開発していると、`forEach`, `map`, `filter`, `reduce`といったメソッドは非常に便利に感じます。
実は、これらのメソッドは(考えてみたらあたりまえですが)`for`, `if`, `switch`, `while`からできています。
そのことを再確認することでこれらのメソッドへの理解が深まるのではと思い、記事を書きました。

この記事では多くをSwiftのリポジトリから引用しているため、バージョンアップで実装が変わる可能性がある点に注意してください(Swift　3.1を前提に書いてます)。

## forEach

まずはシンプルなforEachから始めましょう。

#### forEachの使い方

forEachの使い方は、

```swift:forEach_usage
[1, 2, 3, 4, 5].forEach {
    print($0, terminator: ", ")
}
// 1, 2, 3, 4, 5 と出力
```

です。forEachにクロージャ式を渡して、そのクロージャ式を順に実行してくれます。

#### forEachを分解

forEachの内部の挙動は、[こちら](https://github.com/apple/swift/blob/swift-3.1-branch/stdlib/public/core/Sequence.swift#L1045-L1051)から確認することができます。

以下引用です。

```swift:forEach_internal
extension Sequence {
    public func forEach(_ body: (Element) throws -> Void) rethrows {
        for element in self {
            try body(element)
        }
    }
}
```

Sequenceのprotocol extensionで定義されています。
for文で各要素を取り出して、クロージャ式を順に実行しています。割と単純ですね。

## map(配列版)

mapです。どんどんいきます。
#### mapの使い方

```swift:map_usage
let doubledArray = [1, 2, 3, 4, 5].map { $0 * 2 }
print(doubledArray) // [2, 4, 6, 8, 10]
```

要素それぞれに順にクロージャ式を実行していき、それぞれの結果から新しい配列を作っています。

#### mapを分解する

mapの内部の挙動は2種類あるようで、[Sequence](https://github.com/apple/swift/blob/swift-3.1-branch/stdlib/public/core/Sequence.swift#L803-L820)と[Collection](https://github.com/apple/swift/blob/swift-3.1-branch/stdlib/public/core/Collection.swift#L1297-L1318)で異なった実装になっています。

以下引用です(コメントは筆者によるものです)。

```swift:map_internal_sequence
extension Sequence {
    public func map<T>(
        _ transform: (Iterator.Element) throws -> T
    ) rethrows -> [T] {
        // 結果を格納するための配列を用意する
        let initialCapacity = underestimatedCount
        var result = ContiguousArray<T>()
        result.reserveCapacity(initialCapacity)

        var iterator = self.makeIterator()

        // 順にtransformを実行して、配列に追加する
        for _ in 0..<initialCapacity {
            result.append(try transform(iterator.next()!))
        }
        while let element = iterator.next() {
            result.append(try transform(element))
        }
        return Array(result)
    }
}
```

```swift:map_internal_collection
extension Collection {
    public func map<T>(
        _ transform: (Iterator.Element) throws -> T
    ) rethrows -> [T] {
        // 結果を格納するための配列を用意する
        let count: Int = numericCast(self.count)
        if count == 0 {
            return []
        }
        var result = ContiguousArray<T>()
        result.reserveCapacity(count)

        var i = self.startIndex
        // 順にtransformを実行して、配列に追加する
        for _ in 0..<count {
            result.append(try transform(self[i]))
            formIndex(after: &i)
        }

        _expectEnd(of: self, is: i)
        return Array(result)
    }
}
```

SequenceとCollectionで実装が異なる理由は、Collectionにのみ`count`や`subscript`の機能があるからのようです(mapは他と比べて使用頻度が多いからか配列のアロケーションを最小限にするなど手の込んだチューニングになっている印象です)。
Collectionに`_expectEnd`という関数があります。これは[開発中のテスト用関数みたい](https://github.com/apple/swift/blob/master/stdlib/public/core/Arrays.swift.gyb#L1869-L1873)なので気にしなくて良さそうです。

SequenceとCollectionで若干の違いはあるものの、単純化して書くと

```swift:
public func map<T>(_ transform: (Element) throws -> T) rethrows -> [T] {
    var result = ContiguousArray<T>()
    for element in self {
        result.append(transform(element))
    }
    return Array(result)
}
```

と解釈してもほとんどの場合問題ないはずです(あるとしたらカリカリにチューニングしたい時ぐらいですかね)。

ひとつ気になる点として、SequenceもCollectionもContiguousArrayに結果を追加していって、返す直前でArrayに変換しています。最初からArrayを使えば良いような気もしますが、ContiguousArrayの[ドキュメント](https://developer.apple.com/reference/swift/contiguousarray)を読むと単純にパフォーマンスのためのようなので、あまり気にしなくてもいいのではないでしょうか(もし間違ってたら教えてください🙇)。

以上まとめると、

1. 結果を格納する配列を用意する
2. for文で回して結果を順に配列に追加していく
3. 配列を返す

でした。

## map(Optional版)

Optional型にもmapがあります。どんどん行きます。

#### mapの使い方

```swift:OptionalMapUsage
let optionalInt1 = Int("134") // Optional(134)
let optionalInt2 = Int("abc") // nil

optionalInt1.map { $0 + 100 } // Optional(234)
optionalInt2.map { $0 + 100 } // nil
```

値がnilならnilのまま、nilでなければ値にクロージャ式を当てはめてくれます。

#### mapを分解する

Optionalのmapの実装は[こちら](https://github.com/apple/swift/blob/swift-3.1-branch/stdlib/public/core/Optional.swift#L160-L169)です。

以下引用です(コメントは筆者によるものです)。

```swift:OptionalMapInternal
public struct Optional<Wrapped> {
    public func map<U>(_ transform: (Wrapped) throws -> U) rethrows -> U? {
        switch self {
        case .some(let y): // nilでない場合
          return .some(try transform(y)) // transformで変換
        case .none: // .noneはnilのことです
          return .none // nilを返すだけ
    }
}
```

switchで`nil`か否か判断しているだけですね。

## reduce

reduceです。

#### reduceの使い方

```swift:reduce_usage
let sumOfSquare = [1, 2, 3, 4, 5].reduce(0) {
    $0 + $1 * $1
}
print(sumOfSquare) // 55 (1 + 4 + 9 + 16 + 25 = 55)
```

各要素を畳み込んでくれます。

#### reduceを分解する

reduceのソースコードは[こちら](https://github.com/apple/swift/blob/swift-3.1-branch/stdlib/public/core/SequenceAlgorithms.swift.gyb#L601-L611)です。

ソースコードのリンク先について注意点があります。リンク先のファイルは`.swift`ではなく、`.gyb`という拡張子になっています。
`.gyb`というファイルはそのままでは読めないので`.swift`ファイルに変換する必要があります。
変換方法は[こちらの記事](https://oleb.net/blog/2016/10/swift-stdlib-source/)が参考になります。

以下引用(`.swift`に変換済み)です。

```swift:ReduceInternal
extension Sequence {
    public func reduce<Result>(
        _ initialResult: Result,
        _ nextPartialResult:
          (_ partialResult: Result, Iterator.Element) throws -> Result) rethrows -> Result {
        var accumulator = initialResult
        for element in self {
            accumulator = try nextPartialResult(accumulator, element)
        }
        return accumulator
    }
}
```

これもfor文で順に`nextPartialResult`を使っているだけです。

## filter

#### filterの使い方

```swift:filter_usage
let evenNumbers = [1, 2, 3, 4, 5].filter({
    $0 % 2 == 0
})
print(evenNumbers) // [2, 4]
```

特定の条件を満たすもののみを抽出します。

#### filterを分解する

filterのソースコードは[こちら](https://github.com/apple/swift/blob/swift-3.1-branch/stdlib/public/core/Sequence.swift#L838-L853)です。

以下引用です(コメントは筆者による)。

```swift:filter_internal
extension Sequence {
    public func filter(
        _ isIncluded: (Iterator.Element) throws -> Bool
    ) rethrows -> [Iterator.Element] {
        // 結果を格納する配列を作成する
        var result = ContiguousArray<Iterator.Element>()
        var iterator = self.makeIterator()

        // isIncludedがtrueになれば配列に追加
        while let element = iterator.next() {
            if try isIncluded(element) {
                result.append(element)
            }
        }

        return Array(result)
    }
}
```

while文で回して、`isIncluded`が`true`なら配列に追加しています。

## prefix(while:)

最後にSwift 3.1で追加されたprefix(while:)です。

#### prefix(while:)の使い方

```swift:prefix_usage
let prefixBeforeFour = [1, 2, 3, 4, 5, 4, 3, 2, 1].prefix(while: {
    $0 != 4
})
print(prefix)
```

条件に当てはまらなくなるまでの要素を返してくれます。

#### prefix(while:)を分解する

prefix(while:)の実装は[こちら](https://github.com/apple/swift/blob/swift-3.1-branch/stdlib/public/core/Sequence.swift#L1304-L1317)から見られます。

以下引用です

```swift:prefix_internal
extension Sequence {
    public func prefix(
        while predicate: (Iterator.Element) throws -> Bool
    ) rethrows -> AnySequence<Iterator.Element> {
        var result: [Iterator.Element] = []

        for element in self {
            guard try predicate(element) else {
                break
            }
            result.append(element)
        }
        return AnySequence(result)
    }
}
```

for文を使っているだけです。

## 分解ケーススタディー(filterとprefix(while:))

下のコードを見てください。Nの2乗の数列を返すSequenceです。

```swift:SquareSequence
// nの2乗の数列: 0, 1, 4, 9, 16, 25...
struct SquareSequence: Sequence {
    func makeIterator() -> SquareIterator {
        return SquareIterator()
    }
}

struct SquareIterator: IteratorProtocol {
    private var n = 0
    mutating func next() -> Int? {
        let square = n * n
        n += 1
        return square
    }
}
```

上記の様に実装した`SquareSequence`を使って2000までの値を取り出したいとします。
たとえばこういうコードはどうでしょう。

```swift
// NG: 桁あふれで強制終了します
let squareValuesUntil2000WithFilter = SquareSequence().filter { %0 < 2000 }

// OK: 0, 1, 4, 9,..., 1936
let squareValuesUntil2000WithPrefix = SquareSequence().prefix { %0 < 2000 }
```

なぜfilterを使うと強制終了するかは、filterの実装を見ると一目瞭然です。
`let squareValuesUntil2000WithFilter = SquareSequence().filter { %0 < 2000 }`は、下記のコードと同等だからです。

```swift
var squareValuesUntil2000WithFilter = ContiguousArray<Iterator.Element>()
var iterator = SquareSequence().makeIterator()

// iterator.next()が`nil`を返すまで止まらない!!!
while let element = iterator.next() {
    if try isIncluded(element) {
        result.append(element)
    }
}

squareValuesUntil2000WithFilter = Array(squareValuesUntil2000WithFilter)
```

強制終了を防ぐためには、桁あふれを検知したら`next()`で`nil`を返すようにするかprefix(while:)を使えばよいことがわかります。