Sibainu Relax Room

愛犬の柴犬とともに過ごす部屋

RUST 列挙型連結リスト

こんなことを理解できないなんて！先が思いやられるわと思っている柴犬です。

また、この連結リストの作成方法は応用範囲が広そうで、今後役に立ちそうなテクニックと考え投稿します。

概要

RUST の列挙型について調べるために、RUSTの次の公式サイトを読みました。

3.2.3. テストケース: 連結リスト
https://doc.rust-jp.rs/rust-by-example-ja/custom_types/enum/testcase_linked_list.html

ここ中で書かれているコードが理解できず、さらにRUSTの列挙型の理解もなかなか難しく、ここ数日考えていました。

ここに至り自分なりの考えがまとまりましたので投稿します。

3.2.3. テストケース: 連結リスト

下のコードは、3.2.3. テストケース: 連結リストに記載されているコードから、先入観を除くためコメントを消去したものです。

copy

use crate::List::*;

enum List {
    Cons(u32, Box<List>),
    Nil,
}

impl List {
    fn new() -> List {
        Nil
    }

    fn prepend(self, elem: u32) -> List {
        Cons(elem, Box::new(self))
    }

    fn len(&self) -> u32 {
        match *self {
            Cons(_, ref tail) => 1 + tail.len(),
            Nil => 0
        }
    }

    fn stringify(&self) -> String {
        match *self {
            Cons(head, ref tail) => {
                format!("{} {}", head, tail.stringify())
            },
            Nil => {
                format!("Nil")
            },
        }
    }
}

fn main() {
    let mut list = List::new();
    list = list.prepend(1);
    list = list.prepend(2);
    list = list.prepend(3);

    println!("linked list has length: {}", list.len());
    println!("{}", list.stringify());
}

自分の理解

以下は、自分の理解をまとめたものです。

最初、len() をリストの len() に惑わされ tail をリストと誤解したので、この誤解から脱却するのにかなりの時間を費やさせられました。

何度も読み返しここで理解したことは、tail.len() は単に列挙子のメソッドを実行しているだけだということです。

そして、列挙体 List のメッソド fn len と fn stringify は再帰をして、再帰の終了条件は Nil であることです。

    fn len(&self) -> u32 {
        match *self {
            // 実行するごとに 1 を加算
            // `tail.len()` === `List::len(&tail)`
            Cons(_, ref tail) => 1 + tail.len(),
            // 終了条件 0 を加算
            Nil => 0
        }
    }

    fn stringify(&self) -> String {
        match *self {
            // 実行するごとに head（elem）を書き出す
            Cons(head, ref tail) => {
                // `tail.stringify()` === `List::stringify(&tail)`
                format!("{} {}", head, tail.stringify())
            },
            // 終了条件 Nil を書き出して終了
            Nil => {
                format!("Nil")
            },
        }
    }

list は列挙子 Nil、Cons を順に格納して、最終的に List型 Cons(3, X2) であることを理解しました。

    // list は List型 Nil を格納しました。
    let mut list = List::new();

    // X0 は List型 Nil をヒープ領域に作成したアドレス
    // アドレスX0を格納する List型 Cons(1, X0) をlist に格納します。
    list = list.prepend(1);

    // X1 は List型 Cons(1, X0) をヒープ領域に作成したアドレス
    // アドレスX1を格納する List型 Cons(2, X1) をlist に格納します。
    list = list.prepend(2);

    // X2 は List型 Cons(2, X1) をヒープ領域に作成したアドレス
    // アドレスX2を格納する List型 Cons(3, X2) をlist に格納します。
    list = list.prepend(3);

list は Cons(3, X2) で再帰的に Cons(2, X1)、 Cons(1, X0)、 Nil と遡っていき、Nil でストップします。

println!("linked list has length: {}", list.len());
println!("{}", list.stringify());

List を Rist に置き換えてみた

リストの呪縛から逃れるために、List の名称を変えることにします。

トップの use 句を除いて次のように List を Rist に置き換えてみました。

use crate::List::*;

enum Rist {
    Cons(u32, Box<Rist>),
    Nil,
}

impl Rist {
    fn new() -> Rist {
        Nil
    }

    fn prepend(self, elem: u32) -> Rist {
        Cons(elem, Box::new(self))
    }

    fn len(&self) -> u32 {
        match *self {
            Cons(_, ref tail) => 1 + tail.len(),
            Nil => 0
        }
    }

    fn stringify(&self) -> String {
        match *self {
            Cons(head, ref tail) => {
                format!("{} {}", head, tail.stringify())
            },
            Nil => {
                format!("Nil")
            },
        }
    }
}

fn main() {
    let mut list = Rist::new();
    list = list.prepend(1);
    list = list.prepend(2);
    list = list.prepend(3);

    println!("linked list has length: {}", list.len());
    println!("{}", list.stringify());
}

エラー発生

上のコードを実行してみましたところ、次のとおりエラーになりました。

use crate::Rist::Cons;

とインフォメーションがあるので、トップも Rist に変えてみました。

use crate::List::*;
　　　　　　 ↓
use crate::Rist::*;

無事実行できました。

疑問

ここで分からないことがまた発生しました。それは、 use crate::Rist（use crate::List） は何者かということです。

これは、今後の課題とします。

全コード

最後に、実行できた全コードです。

copy

use crate::Rist::*;

enum Rist {
    Cons(u32, Box<Rist>),
    Nil,
}

impl Rist {
    fn new() -> Rist {
        Nil
    }

    fn prepend(self, elem: u32) -> Rist {
        Cons(elem, Box::new(self))
    }

    fn len(&self) -> u32 {
        match *self {
            Cons(_, ref tail) => 1 + tail.len(),
            Nil => 0
        }
    }

    fn stringify(&self) -> String {
        match *self {
            Cons(head, ref tail) => {
                format!("{} {}", head, tail.stringify())
            },
            Nil => {
                format!("Nil")
            },
        }
    }
}

fn main() {
    let mut list = Rist::new();
    list = list.prepend(1);
    list = list.prepend(2);
    list = list.prepend(3);

    println!("linked list has length: {}", list.len());
    println!("{}", list.stringify());
}