最近、Rustで二分木のデータ構造を実装してみました。二分木はそれぞれ、ルートの値と左の部分木、右の部分木を持ちます。まずは、かなり素直なこのPythonの実装から始めました。

class Tree:
  def __init__(self, val, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

これで、次のような凝った木のオブジェクトを宣言できます。

t = Tree(15,
      Tree(12,
           None,
           Tree(13)),
      Tree(22,
           Tree(18),
           Tree(100)))

そして、その結果は美しく可視化できます。
（はい、これは自分で描きました。）

このコードをRustに移植するのは、少し……大変でした。最初の試みは、特に問題なさそうに見えました。

struct Tree {
  root: i64,
  left: Tree,
  right: Tree,
}

これはPythonの定義をほぼ一対一で移したものです。ところが、rustcはダメだと言います。

error[E0072]: recursive type `Tree` has infinite size
 --> src/main.rs:1:1
  |
1 | struct Tree {
  | ^^^^^^^^^^^ recursive type has infinite size
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Tree` representable

PythonやPHP、Rubyのようなメモリ管理言語から来た私は、これに戸惑いました。しかし、問題自体は簡単に理解できます。コンピューターのメモリ容量には限りがあります。各要素にどれだけのメモリを割り当てるべきかを判断するのは、コンパイラーの仕事です。

今回のケースでは、コンパイラーは次のように推論します。

木とは、i64と2つの木を含む構造体です。その木も、i64と2つの木を含む構造体です。さらにその木も……
ということです。

Tree { i64, Tree, Tree }
Tree { i64, Tree { ... }, Tree { ... } }
// The next expansion won't fit on the page anymore

木がいくつの部分木を持つことになるのかはわからないので、あらかじめ必要なメモリ量を決める方法はありません。わかるのは実行時になってからです。

Rustは、BoxやRc、&のような間接参照を挿入すればよいと教えてくれます。これらはRustにおける異なる「ポインター型」です。どれもメモリ上の場所を指します。つまり、木構造全体のサイズを知る代わりに、木が置かれているメモリ上の場所だけを知ればよいのです。それで木構造を定義するには十分です。これらのポインター型を使えば、手動でメモリを管理せず、安全にこの構造を実現できます。それぞれ異なる保証を提供するので、要件に最も合ったものを選ぶべきです。

• &は、Rustの用語ではborrowと呼ばれます。3つの中では最も一般的です。これはメモリ上のある場所への参照ですが、指しているデータを所有してはいません。そのため、借用のライフタイムは所有者に依存します。したがって、ここではライフタイムパラメーターを追加する必要があります。これを使うのは面倒になることがあります。

  struct Tree<'a> {
    root: i64,
    left: &'a Tree<'a>,
    right: &'a Tree<'a>,
  }

• Boxは、実行時オーバーヘッドがゼロのスマートポインターです。指しているデータを所有し、そのデータをヒープに格納します。スコープを外れると、まず指しているデータをドロップし、その後で自分自身もドロップするため、スマートと呼ばれます。手動でメモリを管理する必要がないのは便利ですね。✨

  struct Tree {
    root: i64,
    left: Box<Tree>,
    right: Box<Tree>,
  }

• Rcも別のスマートポインターです。これは「reference-counting（参照カウント）」の略です。データ構造への参照数を内部で追跡します。参照数が0になると、後始末を行います。同じスレッド内で同じデータを複数の所有者が共有する必要があるなら、Rcを選びます。マルチスレッドの場合は、Arc（アトミック参照カウント）もあります。

  struct Tree {
    root: i64,
    left: Rc<Tree>,
    right: Rc<Tree>,
  }

木を箱に入れる

3つの選択肢はどれも完全に有効です。どれを選ぶべきかは、用途によって決まります。経験則としては、シンプルにしておくことです。私の場合、特別な保証は必要なかったので、Boxを使うことにしました。

部分木をオプションにする

次に直面した問題は、木構造をインスタンス化できなかったことです。左と右の部分木の型はBox<Tree>ですが、どこかの時点では空の部分木が必要になります。

Pythonの例では、データ構造の終端を示すためにNoneを使いました。RustのOption型を使えば、同じことができます。

struct Tree {
  root: i64,
  left: Option<Box<Tree>>,
  right: Option<Box<Tree>>,
}

これで、最初の木を作成できます。

Tree {
    root: 15,
    left: Some(Box::new(Tree {
            root: 12,
            left: None,
            right: Some(Box::new(Tree {
                    root: 13,
                    left: None,
                    right: None,
            })),
    })),
    right: Some(Box::new(Tree {
            root: 22,
            left: Some(Box::new(Tree {
                    root: 18,
                    left: None,
                    right: None,
            })),
            right: Some(Box::new(Tree {
                    root: 100,
                    left: None,
                    right: None,
            })),
    })),
};

見方によっては、冗長とも明示的とも言えるでしょう。Python版と比べると、私の好みでは少しごちゃごちゃしすぎて見えました。

もっとよくできないでしょうか。Chris McDonaldが、次のような表現を考えるのを手伝ってくれました。

Tree::new(15)
  .left(
    Tree::new(12)
      .right(Tree::new(13))
  )
  .right(
    Tree::new(22)
      .left(Tree::new(18))
      .right(Tree::new(100))
  );

こちらのほうが、ずっと目にやさしいと思います。
これを可能にする木の完全な実装は次のとおりです。

#[derive(Default)]
struct Tree {
  root: i64,
  left: Option<Box<Tree>>,
  right: Option<Box<Tree>>,
}

impl Tree {
  fn new(root: i64) -> Tree {
    Tree {
      root: root,
      ..Default::default()
    }
  }

  fn left(mut self, leaf: Tree) -> Self {
    self.left = Some(Box::new(leaf));
    self
  }

  fn right(mut self, leaf: Tree) -> Self {
    self.right = Some(Box::new(leaf));
    self
  }
}

追記：Danny GreinがTwitterで、From<i64> for Treeを実装すれば、次の構文もサポートできると教えてくれました。

root(15)
  .left(
    root(12)
      .right(13)
   )
  .right(
    root(22)
      .left(18)
      .right(100)
  );

なぜPythonではそのまま動いたのか

ここまで読むと、なぜPythonの木の実装はあれほど問題なく動いたのか、不思議に思うかもしれません。理由は、Pythonが実行時に木オブジェクト用のメモリを動的に割り当てるからです。また、すべてをPyObjectでラップしています。これは上で説明したRc、つまり参照カウント方式のスマートポインターに似たものです。

この点で、Rustはより明示的です。必要なものを表現する柔軟性が高い一方で、それをうまく使うには、考えられる選択肢をすべて把握しておく必要もあります。単純な借用で済むなら、スマートポインターは使わないことをおすすめします。

ただし、ライフタイムが邪魔になったり、スレッドセーフなどの追加の保証が必要になったりする場合は、スマートポインターがツールキットに加わる強力な味方になります。スマートポインターについてさらに学ぶには、Rustのドキュメントがよい出発点です。また、木を実行時に変更可能にする必要がある場合に、アロケーターを巧みに使う方法については、「Rustにおける慣用的な木構造とグラフ風構造」も読んでみてください。