实现指树时“添加删除检查规则时溢出”

Question

我正在尝试定义一个手指树结构并实现其基本操作作为 Rust 中的练习。我提出了以下内容，基本上就是本文中描述的内容。

use self::FingerTree::{Empty, Single, Deep};
use self::Digit::{One, Two, Three, Four};

enum Digit<A> {
    One(A),
    Two(A, A),
    Three(A, A, A),
    Four(A, A, A, A),
}

enum Node<V, A> {
    Node2(V, A, A),
    Node3(V, A, A, A),
}

enum FingerTree<V, A> {
    Empty,
    Single(A),
    Deep {
        size: V,
        prefix: Digit<A>,
        tree: Box<FingerTree<V, Node<V, A>>>,
        suffix: Digit<A>,
    },
}

fn main() {
    let e: FingerTree<i32, String> = Empty;
}

编译给我一个我不明白的错误：

use self::FingerTree::{Empty, Single, Deep};
use self::Digit::{One, Two, Three, Four};

enum Digit<A> {
    One(A),
    Two(A, A),
    Three(A, A, A),
    Four(A, A, A, A),
}

enum Node<V, A> {
    Node2(V, A, A),
    Node3(V, A, A, A),
}

enum FingerTree<V, A> {
    Empty,
    Single(A),
    Deep {
        size: V,
        prefix: Digit<A>,
        tree: Box<FingerTree<V, Node<V, A>>>,
        suffix: Digit<A>,
    },
}

fn main() {
    let e: FingerTree<i32, String> = Empty;
}

为什么这不起作用？我该如何让它发挥作用？

Answer 1

您已经创建了一个无限类型。

实例化FingerTree<V, A>实例化FingerTree<V, Node<V, A>>实例化FingerTree<V, Node<V, Node<V, A>>>实例化实例化……而且看不到尽头。

编译器无法判断该类型在运行时实际上不会被使用，因此要做好最坏的准备。最坏的情况是无限的。

只需替换 的类型tree即可Box<FingerTree<V, A>>解决问题，尽管它可能不适合当前的情况。