如何递归地实现对 Iterable 的深度扁平化？

Question

看过 flatten 之后，我一直在寻找 deepFlatten 的东西，也就是说，它不仅可以与 Iterable<Iterable<T>> 一起使用（与 Arrays，但为了简洁起见，现在让我们关注 Iterable），还有 Iterable<Iterable<Iterable<T>>>、Iterable<Iterable<Iterable<Iterable<T>>>> 等等...

当然，结果必须是 List<T>，标准 flatten() 不提供 - 它会 return List<Iterable<T>（或 List 嵌套更多 Iterables).

我正在尝试使用 reified 泛型：

inline fun <reified E, T> Iterable<E>.deepFlatten(): List<T> = when(E::class) {
    Iterable<*>::class -> (this as Iterable<Iterable<*>>).flatten().deepFlatten()
    else -> flatten()
}

但这显然充满了错误：

T 似乎无法推断
您不能拥有接口

::class

您不能递归 inline 函数

是否有解决上述问题的方法？或者，更好的是，是否有更简洁的方法来解决这个问题？

为了演示完整性的示例，我希望能够做到：

fun main() {
    val data: List<List<List<Int>>> = listOf(
            listOf(listOf(1, 2, 3), listOf(5, 6), listOf(7)),
            listOf(listOf(8, 9), listOf(10, 11, 12, 13))
    )

    print(data.deepFlatten()) // 1 2 3 4 5 6 7 8 9 10 11 12 13
}

嵌套的 Iterable 的深度（它们不必是同一类型 - 重要的是它们通常 Iterable）可以变化。

Answer 1

在 Java 中，您可以使用 java-stream:

实现完全相同的行为

使用Collection<?>:

public static Stream<?> deepFlatMap(Object o) {
   if (o instanceof Collection<?>) {
       return ((Collection<?>) o).stream().flatMap(i -> deepFlatMap(i));
   }
   return Stream.of(o);
}

使用Iterable<?>:

public static Stream<?> deepFlatMap(Object o) {
   if (o instanceof Iterable<?>) {
       Spliterator<?> spliterator = ((Iterable<?>) o).spliterator();
       return StreamSupport.stream(spliterator, false).flatMap(i -> deepFlatMap(i));
   }
   return Stream.of(o);
}

用法非常简单：deepFlatMap(list).forEach(System.out::println);

虽然我不会Kotlin，但我希望这至少能帮助你重写这个想法。

编辑：只要你想指定return目标泛型类型，你应该使用另一种包装方法（不要忘记在递归方法):

public static <T> Stream<T> deepFlatMap(Collection<?> collection) {
    return (Stream<T>) internalDeepFlatMap(collection);
}

public static Stream<?> internalDeepFlatMap(Object o) {
   if (o instanceof Collection<?>) {
       return ((Collection<?>) o).stream().flatMap(i -> internalDeepFlatMap(i));
   }
   return Stream.of(o);
}

显式指定通用类型的用法：

MyClass.<Integer>deepFlatMap(list).map(i -> i + 1).forEach(System.out::println);

Answer 2

fun <T> Iterable<*>.deepFlatten(): List<T> {
    val result = ArrayList<T>()
    for (element in this) {
        when (element) {
            is Iterable<*> -> result.addAll(element.deepFlatten())
            else -> result.add(element as T)
        }
    }
    return result
}
...

println(data.deepFlatten<Int>())

您必须显式指定类型，并且会失去编译时安全性。但它可以展平任何嵌套和不同类型元素的列表 ([1, "foo", [3, "bar"]] -> [ 1, "foo", 3, "bar"])

我更喜欢不同的解决方案。像这样：

typealias It2<T> = Iterable<Iterable<T>>
typealias It3<T> = Iterable<It2<T>>
typealias It4<T> = Iterable<It3<T>>
typealias It5<T> = Iterable<It4<T>>
//etc...

fun <T> It3<T>.flatten2(): List<T> = flatten().flatten()
fun <T> It4<T>.flatten3(): List<T> = flatten2().flatten()
fun <T> It5<T>.flatten4(): List<T> = flatten3().flatten()
//etc...

...
println(data.flatten2())

如何递归地实现对 Iterable 的深度扁平化？

How to recursively implement a deep flatten on Iterable?

generics

recursion

flatten

kotlin

kotlin-reified-type-parameters