SwiftでRubyのflatten()を再現する

これは [Swift Advent Calendar 2017](https://qiita.com/advent-calendar/2017/swift) 16日目の投稿です。
なんと昨日15日目が空いてしまっています、誰か埋めてください。

# 前提

## そもそも `flatten` とは

直訳すると、他動詞で「平らにする」という意味で、Swiftと戯れているエンジニアは、「 `flatMap` は `flatten + map` である」というのを聞いたことがあるのではないでしょうか。
~~しかし、Swift 3.0以降には `flatten()` は実装されていません。~~
[@koher](https://qiita.com/koher)さんから、 `joined()` にリネームされたことを教えていただきました。
https://github.com/apple/swift-evolution/blob/master/proposals/0133-rename-flatten-to-joined.md

```swift
let array: [[Int]] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

print(array.joined().first)
// Optional(1)
```

## Swift 2.xの場合
SwiftでもSwift 2.x時代は `flatten()` が実装されていました。
ただし、Swiftの場合は `FlattenCollection<Self>` か `FlattenBidirectionalCollection<Self>` が返り値で、遅延評価とされていました。

```swift
// Swift 2.xの時
let array: [[Int]] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

print(array.flatten())
// FlattenBidirectionalCollection<Array<Array<Int>>>(_base: [[1, 2, 3], [4, 5, 6], [7, 8, 9]])

print(array.flatten().first)
// Optional(1)
```

Swiftの `flatMap` が `flatten + map` と言われるのは、この特性から。

```swift
// Swift 2.xの時
let array: [[Int]] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

print(array.flatten().map { $0 })
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

// Swift 4.xでも動く
print(array.flatMap { $0 })
// [1, 2, 3, 4, 5, 6, 7, 8, 9]
```

# 本題

## Rubyの場合

Rubyでも同様な `flatten(level)` が存在します。

```ruby
array = [1, 2, 3, [4, 5, 6], [7, [8, 9]]]

p array.flatten(1)
# [1, 2, 3, 4, 5, 6, 7, [8, 9]]
```

Rubyではさらに、以下のようなことができます。

```ruby
array = [1, 2, 3, [4, 5, 6], [7, [8, 9]]]

p array.flatten(2)
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

p array.flatten
# [1, 2, 3, 4, 5, 6, 7, 8]
```

levelは、n重ネストをlevelの回数まで `flatten` 処理をすることを表します。

これの再現が、今回のお題です。

## お題の整理

今回のお題の条件をまとめます。

* SwiftでRubyの `flatten` 処理を再現する
    * levelを指定することで、指定分のネストを平坦化する
    * levelがネスト数を超えた場合は、ネスト数分の平坦化した値を返す
* ただし、Rubyでの引数なし `flatten` は考えない

    ```ruby
    array = [1, 2, 3, [4, 5, 6], [7, [8, 9]]]

    p array.flatten
    # [1, 2, 3, 4, 5, 6, 7, 8]
    ```

* 型情報は維持する

## Swiftの `flatMap`

「 `flatMap` は `flatten + map` である」とは言うものの、Swiftの `flatMap` では、そもそもネストしたArrayに対しての `flatten` 処理が行なえません。

```swift
let array: [Any] = [1, 2, 3, [4, 5, 6], [7, [8, 9]]]

print(array.flatMap({ $0 }))
// [1, 2, 3, [4, 5, 6], [7, [8, 9]]]
```

## 独自型で表現する

Sequenceに対しての処理を考えると、型の世界から離れざるを得ないようです。
ということで、独自型で `[1, 2, 3, [4, 5, 6], [7, [8, 9]]]` に相当する表現をして、解決してみました。

```swift
indirect enum Value<T> {
    case single(element: T)
    case multiple(values: [Value])
    
    func flatten(_ level: UInt) -> Value {
        switch self {
        case .single:
            return self
        case .multiple(let values):
            var results: [Value] = values
            for _ in 0..<level {
                var stack: [Value] = []
                for v in results {
                    switch v {
                    case .single:
                        stack.append(v)
                    case .multiple(let vs):
                        for a in vs {
                            switch a {
                            case .single:
                                stack.append(a)
                            case .multiple(let b):
                                stack.append(Value.multiple(values: b))
                            }
                        }
                    }
                }
                results = stack
            }
            return Value.multiple(values: results)
        }
    }
}
```

```swift
let value1 = Value.single(element: 1)
print(value1.flatten)
// single(1)

let value2 = Value.multiple(values: [Value.single(element: 1),
                                     Value.single(element: 2),
                                     Value.single(element: 3),
                                     Value.multiple(values: [Value.single(element: 4),
                                                             Value.single(element: 5),
                                                             Value.single(element: 6)]),
                                     Value.multiple(values: [Value.single(element: 7),
                                                             Value.multiple(values: [Value.single(element: 8),
                                                                                     Value.single(element: 9)])])])
// let array = [1, 2, 3, [4, 5, 6], [7, [8, 9]]] と同等と考えます

print(value2.flatten(1))
// multiple([__lldb_expr_1.Value<Swift.Int>.single(1), 
//           __lldb_expr_1.Value<Swift.Int>.single(2),
//           __lldb_expr_1.Value<Swift.Int>.single(3), 
//           __lldb_expr_1.Value<Swift.Int>.single(4), 
//           __lldb_expr_1.Value<Swift.Int>.single(5),
//           __lldb_expr_1.Value<Swift.Int>.single(6),
//           __lldb_expr_1.Value<Swift.Int>.single(7), 
//           __lldb_expr_1.Value<Swift.Int>.multiple([__lldb_expr_1.Value<Swift.Int>.single(8), 
//                                                    __lldb_expr_1.Value<Swift.Int>.single(9)])])

print(value2.flatten(2))
// multiple([__lldb_expr_1.Value<Swift.Int>.single(1), 
//           __lldb_expr_1.Value<Swift.Int>.single(2), 
//           __lldb_expr_1.Value<Swift.Int>.single(3), 
//           __lldb_expr_1.Value<Swift.Int>.single(4), 
//           __lldb_expr_1.Value<Swift.Int>.single(5), 
//           __lldb_expr_1.Value<Swift.Int>.single(6), 
//           __lldb_expr_1.Value<Swift.Int>.single(7), 
//           __lldb_expr_1.Value<Swift.Int>.single(8), 
//           __lldb_expr_1.Value<Swift.Int>.single(9)])

print(value2.flatten(3))
// multiple([__lldb_expr_1.Value<Swift.Int>.single(1), 
//           __lldb_expr_1.Value<Swift.Int>.single(2), 
//           __lldb_expr_1.Value<Swift.Int>.single(3), 
//           __lldb_expr_1.Value<Swift.Int>.single(4), 
//           __lldb_expr_1.Value<Swift.Int>.single(5), 
//           __lldb_expr_1.Value<Swift.Int>.single(6), 
//           __lldb_expr_1.Value<Swift.Int>.single(7), 
//           __lldb_expr_1.Value<Swift.Int>.single(8), 
//           __lldb_expr_1.Value<Swift.Int>.single(9)])
```

ということで型を残しつつ、多重ネストをlevel分 `flatten` できました。

# まとめ

~~ここまでやっといてなんですが、UseCase思いつかない...~~

お題に対しての解決はできましたが、もっときれいに解決できそうな気がしているので、回答求む。

## お題

* SwiftでRubyの `flatten` 処理を再現する
    * levelを指定することで、指定分のネストを平坦化する
    * levelがネスト数を超えた場合は、ネスト数分の平坦化した値を返す
* ただし、Rubyでの引数なし `flatten` は考えない
* 型情報は維持する


また、以下の条件もクリアしたいところです。
こちらも解決案があれば、ぜひお願いします。

>  * ただし、Rubyでの引数なし `flatten` は考えない

```ruby
array = [1, 2, 3, [4, 5, 6], [7, [8, 9]]]

p array.flatten
# [1, 2, 3, 4, 5, 6, 7, 8]
```

# 参考
https://ruby-doc.org/core-2.2.0/Array.html#method-i-flatten
[flatMap()の前にflatten()を調べる（予想外に深かった）](http://swiftlife.hatenablog.jp/entry/2016/01/05/142850)
[Swiftのmap, filter, reduce（などなど）はこんな時に使う！](https://qiita.com/motokiee/items/cf83b22cb34921580a52)