How would you go about writing data structures where nodes can have a variable amount of children?

[lenawanel]

first of thank you for your blog post series on recursion.

I'm trying to adapt the described approach to an hir of a simple toy language. this toy language has multiple nodes with a variable number of children.

I wanted to see if it would be possible to adapt this approach to my hir, since intuitively it should be possible to index the underlying vector of elements of a recursive tree using ranges or iterators of indexes.

my approach looks something like:

pub enum NodeLayer<A, T: IntoIterator<Item = A>> {
    Root(T),
    /* ... */
}

impl<A, T: IntoIterator<Item = A>> NodeLayer< A, T> {
    #[inline(always)]
    fn map<B, F: FnMut(A) -> B>(
        self,
        mut f: F,
    ) -> NodeLayer<B, Map<<T as IntoIterator>::IntoIter, F>> {
        match self {
            /* ... */
            NodeLayer::Root(root) => NodeLayer::Root(root.into_iter().map(f)),
        }
    }
}

pub struct NodeTopo {
    elems: Vec<NodeLayer<usize, Range<usize>>>,
}

impl<'src> NodeTopo<'src> {
    pub fn collapse_layers<A, T: IntoIterator<Item = A>, F: FnMut(NodeLayer<'src, A, T>) -> A>(
        self,
        mut collapse_layer: F,
    ) -> A {
        /* same as in the fist blogpost */ 
    }
}

but this results in a type error in the loop in the collapse_layers function (collapse_layer(layer)).

do you have any idea about how to make this work?

[inanna-malick]

Can you share the type error? This is interesting and I'd like to help make it work, but something you can do to get unblocked quickly is to remove IntoIterator and just use a Vec<A> instead.

I think the solution is going to look something like adding a FromIterator bound for T so you can go from T to an iterator that you then map over, then turn that iterator back into T

[dzmitry-lahoda]

I am here also because of some trees. I writing prefix sum(augmented that each node knows sum of values of all its children) binary search tree (AVL). I wrote some function - and they are recursive. I know that is slow, and need to replace with loop as done in std collection. I see some examples in this repo - will try.

So my problem is that I have complicated memory/perf requirements (i will run in ZK prover or in Wasm, with serde and without each transaction or batched, and normal runs). For these I will need to compare binary tree with multiple children tree. So hoping to have changes as small as possible from binary to multi children tree.

I do not have code yet, just thinking.