Rust | 単方向リストを自作する – enum の活用例

基本的なデータ型の一つに、単方向リストがあります。
関数型プログラミングの基本型としてよく利用されるものです。

この記事では、Rust での単方向リストの実装例を紹介します。

なお、実際の開発においては、Rust で関数型プログラミングを記述するためにはイテレータ型を用いるのが適切です。
また、コンテナ型が必要な場合も、標準ライブラリにある Vec や LinkedList を利用するのが良いです。
この記事の実装例は、実用目的ではなく、Rust としての設計サンプルとしての掲載を目的としています。

単方向リストの実装例

List 構造体の定義

まずは構造体を定義します。
構造体と言いつつ、ここでは struct ではなく enum を用いた定義とします。

#[derive(Debug)]
enum List {
    Nil,
    Cons(i32, Box<List>),
}

Rust の enum は、他言語のように定数の列挙というわけではありません。
直和型と呼ばれますが、非対称の構造体の和集合として定義することができます。

Nil と Cons

上記の例では、空であることを示す Nil と、値とリストを結合した Cons の2つの直和を定義しています。
Nil は属性を持ちません。
Cons は、要素の値そのものと、後続リストへの参照を属性としています。

Nil や Cons の名称については、Rust 公式の linked-list サンプルでも用いられているものになります。

Nil はラテン語でゼロを表す単語です。
null と同じような意味で使われることが多いです。

Cons は Constructor の略です。
Nil と合わせて、Lisp 言語などでこの呼称が使われます。

Debug トレイトの組み込み

1行目の derive アトリビュートによって、Debug トレイトを自動組み込みさせています。
これによって、println!("{:?}", list) といった呼び出しで内容を表示させることができます。

メソッドの実装

List に対して、基本的なメソッドを3つ実装します。

impl List {
    fn nil() -> Self {
        Self::Nil
    }

    fn cons(item: i32, list: Self) -> Self {
        Self::Cons(item, Box::new(list))
    }

    fn decons(self) -> (Option<i32>, Self) {
        match self {
            Self::Nil => (None, self),
            Self::Cons(head, tail) => (Some(head), *tail),
        }
    }
}

nil は、空のリストを生成するためのファクトリメソッドです。
cons は、リストに要素を連結することによって、新規リストを生成するためのファクトリメソッドです。
decons は、リストを分解して先頭の要素を取得するためのメソッドです。

List クラスの利用例

以下に、自作した単方向リストの利用例を示します。

fn main() {
    let list = List::nil();
    let list = List::cons(1, list);
    let list = List::cons(2, list);
    let list = List::cons(3, list);

    println!("{:?}", list);
    // Cons(3, Cons(2, Cons(1, Nil)))

    let (item, list) = list.decons();
    println!("{:?}, {:?}", item, list);
    // Some(3), Cons(2, Cons(1, Nil))

    let (item, list) = list.decons();
    println!("{:?}, {:?}", item, list);
    // Some(2), Cons(1, Nil)

    let (item, list) = list.decons();
    println!("{:?}, {:?}", item, list);
    // Some(1), Nil

    let (item, list) = list.decons();
    println!("{:?}, {:?}", item, list);
    // None, Nil
}

まず最初に、 [3, 2, 1] であるリストを構築しています。
単方向リストは一般的に、先頭に要素を追加していきます。（末尾に要素を追加するのは、処理コストが大きいため）

そのあと、decons で要素をひとつずつ取り出していきます。