最近、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一つと二つの木を含む構造体である。その木のそれぞれは、i64一つと二つの木を含む構造体である。そのそれぞれは…
だいたい想像がつくでしょう。

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（参照カウント）」の略で、内部でデータ構造への参照数を数えています。参照数がゼロになった時点で自動的に後片付けをします。同一スレッド内で同じデータに複数の所有者が必要な場合はRcを選んでください。マルチスレッド用にはArc（atomic reference count）もあります。

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

木をBoxに入れる

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のドキュメントはスマートポインタについてさらに学ぶための良い出発点です。また、実行時に木を可変にする必要がある場合のアロケータの巧妙な使い方については、「Idiomatic tree and graph-like structures in Rust」も読んでみてください。