How to recursively implement a deep flatten on Iterable?

Question

Having seen flatten, I was looking for something that would be a deepFlatten, i.e., it would work with not only Iterable<Iterable<T>> (it's pretty much the same for Arrays, but let's focus on Iterable now for brevity), but also with Iterable<Iterable<Iterable<T>>>, Iterable<Iterable<Iterable<Iterable<T>>>> and so on...

Of course, the result would have to be List<T>, which the standard flatten() doesn't provide - it would return List<Iterable<T> (or a List with more nested Iterables).

I was trying to work with reified generics:

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

But this obviously is flooded with errors:

• T seems pretty undeducible
• You cannot have a ::class of an interface
• You cannot recurse on an inline function

Are there any workarounds on the above problems? Or, even better, is there a cleaner approach to the problem?

---

To demonstrate an example for completeness, I'd like to be able to do:

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
}

The depth of nested Iterables (they need not be the same type - it's important that they are generically Iterable) can vary.

Answer 1

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

You have to specify the type explicitly and you lose compile-time safety. But it can flatten lists of any nesting and with elements of different types ([1, "foo", [3, "bar"]] -> [ 1, "foo", 3, "bar"])

I would prefer a different solution. Something like this:

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

Answer 2

In Java, you might achieve the very same behavior using java-stream:

Using Collection<?>:

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

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

The usage is pretty straightforward: deepFlatMap(list).forEach(System.out::println);

As long as I don't know Kotlin, I hope this can at least help you with rewriting the idea.

---

Edit: As long as you want to specify the return target generic type, you should use another wrapper method (don't forget to change the name in the recursive method):

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

Usage with specifying the generic type explicitly:

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