Trying to make a recursive flatten function

I wanted to make a recursive flatten that can deep upto any levels.
I thought of making Flatten structure like this:

struct Flatten<Iter: Iterator> where Iter::Item: Iterator{
	iterator_array: Vec<Flatten<Iter>>,
}

But, it would still doesn't work because at certain point you need define something like if Item is an Iterator, then flatten Item else return the Item as result. I'm not able to define this condition. How can I define this condition?.
Basically I want an output like this.
flatten([1,2,3])==1,2,3
flatten([[1,2,3],[1,2]])==1,2,3,1,2
flatten([[[1,2,3],[1,2]],[[1,2,3],[1,2]]])==1,2,3,1,2,1,2,3,1,2
Is there anyway I can do like this?

I think it is impossible for now.

Flatten should use different implementations for the case <Iter as IntoIterator>::Item implements IntoIterator, and for the case <Iter as IntoIterator>::Item does not implement IntoIterator.
However, it would be impossible to implement "when some type does not implement some trait, then ..." without specialization, which is unstable.

2 Likes

I’ve found a way that utilizes some clever type inference. Basically, it works as long as you know what item type you’re expecting.

// implementation of `deep_flatten()` omitted

fn i_want_i32s(i: impl Iterator<Item=i32>) {
    println!("got: {:?}", i.collect::<Vec<_>>());
}

fn main() {
    let x = vec![1,2,3].into_iter();
    let y = vec![vec![],vec![1,2],vec![3,4]].into_iter();
    let z = vec![vec![],vec![vec![1],vec![2,3]],vec![vec![4,5,6],vec![7]]].into_iter();
    i_want_i32s(x.deep_flatten());
    i_want_i32s(y.deep_flatten());
    i_want_i32s(z.deep_flatten());
}

Output:

got: [1, 2, 3]
got: [1, 2, 3, 4]
got: [1, 2, 3, 4, 5, 6, 7]

(click here to see the implementation)

@lo48576 you might be interested in this as well.

13 Likes

Woah bro, this code is too advanced for me. I had no idea there is a thing called trait inheritance until after seeing your code. I'm really struggling to understand the code. Especially at this line.impl<Depth, I: Iterator, T> DeepFlattenIteratorOf<(Depth,),T> for I. Why doing this (Depth,) make the compiler treat it differently rather than just writing Depth? Also awkward question :grimacing:, since you showed that you can write recursive flatten but with a limitation that the type must manually typed. Should I put your reply as solution? I also think that if that RFC comes to stable, we can write the function without that above limitation. So, for now I'll be keeping the post as unanswered.

Ah, yeah I should probably explain that Depth thing.

I'm pretty much encoding the depth (by which I mean: how many steps of flattening are applied) as a type.

For a type T, the type (T,) is the type of single-element-tuples containing a T (tuple types allow trailing commas in general, for example (i32, i32,) is the same as (i32, i32) - for single element tuples the trailing comma is just mandatory) - but for my purposes it is just a new type different from T. My encoding is: depth 0 is () and depth 1 is ((),) and depth 2 is (((),),) and depth 3 is ((((),),),) and so on. This Depth parameter is then to avoid potential conflicts from the DeepFlattenIteratorOf trait. Leaving it out will make the compiler unhappy. Nonetheless, if the type inference knows that it needs to find out whether some iterator implements DeepFlattenIteratorOf<Depth, Item> for an unknown depth but a concrete known type item, it is able to make progress nonetheless and on the way it can figure out the missing Depth type step by step, too.

And in case you're wondering how I came up with this in the first place: I came up with similar ways of doing ad-hoc code-generation/overloaded-functions with the aid of type inferences and traits (called type classes there) in Haskell. And Rust's type system is apparently similar enough that the approach somewhat transfers.

Regarding the solution, you can do whatever you like. There's no rules about the solution feature on URLO. Getting ones solution approved isn't really worth anything either. I think solutions are mostly a convenience for other readers. Any new readers of the thread can quickly see that the original poster thinks their question has been answered and there's a quick link to the answer at the top of the thread. Also people who want to help answer the question can see that OP doesn't think there's any more answer needed.

6 Likes