Edited at
SwiftDay 16

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

More than 1 year has passed since last update.

これは Swift Advent Calendar 2017 16日目の投稿です。

なんと昨日15日目が空いてしまっています、誰か埋めてください。


前提


そもそも flatten とは

直訳すると、他動詞で「平らにする」という意味で、Swiftと戯れているエンジニアは、「 flatMapflatten + 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の flatMapflatten + 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

flatMapflatten + 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(などなど)はこんな時に使う!