如何使用递归迭代器展平递归结构？

Question

我正在尝试展平递归结构，但我在使用递归迭代器时遇到了问题。

结构如下所示：

#[derive(Debug, Clone)]
pub struct C {
    name: String,
    vb: Option<Vec<B>>,
}

#[derive(Debug, Clone)]
pub struct B {
    c: Option<C>,
}

#[derive(Debug, Clone)]
pub struct A {
    vb: Option<Vec<B>>,
    flat_c: Option<Vec<C>>,
}

我的计划是遍历[=14=]向量并将其展平为flat_c。我希望它看起来像这样，或者至少是 Vec<String>:

Some([
    C {
        name: "foo",
        vb: None,
    },
    C {
        name: "bar",
        vb: None,
    },
    C {
        name: "fizz",
        vb: None,
    },
    C {
        name: "buzz",
        vb: None,
    },
])

这里是我设法做的，有点扁平化结构，但只针对最后一个元素，因为递归没有实现。

impl A {
    fn flat_c(self) -> Self {
        let fc: Vec<C> = self
            .vb
            .clone()
            .unwrap()
            .iter()
            .flat_map(|x| x.c.as_ref().unwrap().vb.as_ref().unwrap().iter())
            .cloned()
            .map(|x| x.c.unwrap())
            .collect();

        Self {
            flat_c: Some(fc),
            ..self
        }
    }
}

fn main() {
    let a = A {
        vb: Some(vec![
            B {
                c: Some(C {
                    name: "foo".to_string(),
                    vb: Some(vec![B {
                        c: Some(C {
                            name: "bar".to_string(),
                            vb: None,
                        }),
                    }]),
                }),
            },
            B {
                c: Some(C {
                    name: "fiz".to_string(),
                    vb: Some(vec![B {
                        c: Some(C {
                            name: "buzz".to_string(),
                            vb: None,
                        }),
                    }]),
                }),
            },
        ]),
        flat_c: None,
    };

    let a = a.flat_c();
    println!("a: {:#?}", a);
}

playground

flat_c的输出：

Some([
    C {
        name: "bar",
        vb: None,
    },
    C {
        name: "buzz",
        vb: None,
    },
])

我还没有深入研究这个问题可能需要的 Iterator 特征实现。

我该如何解决这个问题？也许使用 fold？也许甚至不需要递归方法？我很茫然。

Answer 1

我不确定你想要 "traverse the vb vector and flatten it into flat_c" 的结果是什么，但这里有一个稍微简单的展平递归结构的例子，使用 once for the value that corresponds to the current node, chain to concatenate it with its children and flat_map 展平一切：

use std::iter::once;

#[derive(Debug)]
struct S {
    name: String,
    children: Vec<S>,
}

impl S {
    fn flat(self) -> Vec<String> {
        once(self.name)
            .chain(self.children.into_iter().flat_map(|c| c.flat()))
            .collect()
    }
}

fn main() {
    let s = S {
        name: "parent".into(),
        children: vec![
            S {
                name: "child 1".into(),
                children: vec![],
            },
            S {
                name: "child 2".into(),
                children: vec![],
            },
        ],
    };
    println!("s: {:?}", s);
    println!("flat: {:?}", s.flat());
}

playground

Answer 2

有我的解决方案：

impl C {
    fn flat(&self) -> Vec<C> {
        let mut result = Vec::new();
        result.push(C {
            name: self.name.clone(),
            vb: None,
        });
        if self.vb.is_some() {
            result.extend(
                (self.vb.as_ref().unwrap().iter())
                    .flat_map(|b| b.c.as_ref().map(|c| c.flat()).unwrap_or(Vec::new())),
            );
        }
        return result;
    }
}

impl A {
    fn flat_c(self) -> Self {
        let fc = (self.vb.as_ref().unwrap().iter())
            .flat_map(|b| b.c.as_ref().unwrap().flat())
            .collect();

        Self {
            flat_c: Some(fc),
            ..self
        }
    }
}

它为 C 添加了 flat 函数，因为 C 是递归的来源，只有这个结构可以正确处理它。

因为那些 Options 它看起来很可怕并且很难处理神秘的错误消息。此解决方案假设初始 a 的所有 b.c 不是 None。否则，它会恐慌。我的建议是避免使用 Option<Vec> 并只使用空向量而不是 None.

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=09ea11342cdd733b03172c0fc13c85fd

Answer 3

熟悉常用数据结构是个好主意。你有一个tree, and there are several ways to traverse a tree。你没有明确指定使用哪种方法，所以我随意选择了一种易于实现的方法。

这里的关键是实现一个跟踪某些状态的迭代器：所有尚未访问的节点。在每次调用 Iterator::next 时，我们取下一个值，保存任何要访问的新节点，然后 return 该值。

一旦你有了迭代器，你就可以 collect 把它变成 Vec。

use std::collections::VecDeque;

impl IntoIterator for A {
    type IntoIter = IntoIter;
    type Item = String;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter {
            remaining: self.vb.into_iter().flatten().collect(),
        }
    }
}

struct IntoIter {
    remaining: VecDeque<B>,
}

impl Iterator for IntoIter {
    type Item = String;

    fn next(&mut self) -> Option<Self::Item> {
        self.remaining.pop_front().and_then(|b| {
            b.c.map(|C { name, vb }| {
                self.remaining.extend(vb.into_iter().flatten());

                name
            })
        })
    }
}

fn to_strings(a: A) -> Vec<String> {
    a.into_iter().collect()
}

#[derive(Debug, Clone)]
struct A {
    vb: Option<Vec<B>>,
}

#[derive(Debug, Clone)]
struct B {
    c: Option<C>,
}

#[derive(Debug, Clone)]
struct C {
    name: String,
    vb: Option<Vec<B>>,
}

fn main() {
    let example: A = A {
        vb: Some(vec![
            B {
                c: Some(C {
                    name: "Hello ".to_string(),
                    vb: None,
                }),
            },
            B {
                c: Some(C {
                    name: "World!".to_string(),
                    vb: None,
                }),
            },
        ]),
    };
    println!("The example struct: {:?}", example);
    //clone a copy for a second example, because to_strings() takes ownership of the example A struct
    let receipt: A = example.clone();
    println!("Iterated: {:?}", to_strings(example));
    // another example of using to_strings()
    println!(
        "As a string: {:?}",
        to_strings(receipt).into_iter().collect::<String>()
    );
}

从这里开始，如果您需要的话，应该直接创建 B 的迭代器。拥有所有 None 值似乎很愚蠢，所以我将它们排除在外并直接 returned Strings.

我还把它变成了按值迭代器。您可以按照相同的模式创建一个 returned 引用 B / String 的迭代器，并且只在需要时克隆它们。

另请参阅：

如何使用递归迭代器展平递归结构？

How do I flatten a recursive structure using recursive iterators?

recursion

flatten

rust