如何在可迭代对象上实现递归深度展开？

Question

看到了flatten，我正在寻找一些东西，它将是一个deepFlatten，即它将不仅适用于Iterable<Iterable<T>>（对于Array来说基本相同，但为了简洁起见，现在让我们专注于Iterable），还适用于Iterable<Iterable<Iterable<T>>>，Iterable<Iterable<Iterable<Iterable<T>>>>等等......

当然，结果必须是List<T>，标准的flatten()无法提供这种结果 - 它会返回List<Iterable<T>（或带有更多嵌套Iterable的List）。

我试图使用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。

- Fureeish

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，我希望这可以帮助您重写这个想法。

---

编辑：只要您想指定返回目标泛型类型，您应该使用另一个包装器方法（不要忘记在递归方法中更改名称）：

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);

- Nikolas Charalambidis

---

有没有可能在返回类型中保留最内层的类型？在我的情况下，是 Int？到处抛出 Object 看起来有点不对劲，尤其是我们已经有了泛型。 - Fureeish

谢谢，这似乎是一个不错的解决方法，尽管我会继续尝试将其适应于 Kotlin 的 Sequence 而不是普通 Java 的 Stream。 - Fureeish

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())

- IR42