これは Swift Advent Calendar 2017 16日目の投稿です。
なんと昨日15日目が空いてしまっています、誰か埋めてください。
前提
そもそも flatten とは
直訳すると、他動詞で「平らにする」という意味で、Swiftと戯れているエンジニアは、「 flatMap は flatten + map である」というのを聞いたことがあるのではないでしょうか。
しかし、Swift 3.0以降には flatten() は実装されていません。
@koherさんから、 joined() にリネームされたことを教えていただきました。
https://github.com/apple/swift-evolution/blob/master/proposals/0133-rename-flatten-to-joined.md
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 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 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) が存在します。
array = [1, 2, 3, [4, 5, 6], [7, [8, 9]]]
p array.flatten(1)
# [1, 2, 3, 4, 5, 6, 7, [8, 9]]
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は考えない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 処理が行なえません。
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]]] に相当する表現をして、解決してみました。
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)
}
}
}
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は考えない
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()を調べる（予想外に深かった）
Swiftのmap, filter, reduce（などなど）はこんな時に使う！