Rustで単方向リストを実装する(Enum+Rc版)

概要

Rustの仕様理解のために、単方向リストを実装してみた。
今回は Enum(Tuple) + Rc版になります。

これまでは、作成してみたものは次のものがありますが、Rc<RefCell> 版 に登場する Option に相当する None というか Nullableな値を自前で実装するとどういう工夫が必要かが透けて見えます。

• Rustで単方向リストを実装する(Box版)
• Rustで単方向リストを実装する(Rc版)
• Rustで単方向リストを実装する(unsafe版)

環境

• rustc 1.58.0 (Rust 2021)
• WSL1 (Ubuntu 18.04 LTS)

Enum(Tuple) + Rc版の特徴

• 先頭ノードを指す構造体と各ノードを指す構造体をひとまとめにできる
• Option型相当の処理を部分的に実装しなければならず、面倒な気分になる
  • match構文で値の取り出しが必要で、変数へのアクセスが面倒
• new()などの初期化は、struct と少し書き方が異なる
• 今回は RefCell を使っていないので、置換は Rc に頼っています (通常は素直に RefCell を使ったほうが良いでしょう)

コードの概要

今回は次のメソッドを対象にしています。書いてみた試行錯誤の段階での難易度はこうです。(試行錯誤の過程でコードは短くなっているので、きっと簡単に見えると思います。なお、RcはBoxより組みやすいです。)

なお、難易度は Enum が…というよりは、 Rc<RefCell<_>> でなく Rc<_> としたことに起因します。
コード量の多さは主に Enum の値の参照や取り出しにくさが原因です。

method	難易度
push_front	★ (とても簡単)
push_back	★★★
pop_front	★★
pop_back	★★★★ (とても難しい)

use std::rc::Rc;

pub enum SList<T> {
    Cons(T, Rc<SList<T>>),
    Nil,
}

impl<T> SList<T> {
    pub fn push_back(&mut self, v: T) {}
    pub fn push_front(&mut self, v: T) {}
}

impl<T: Clone> SList<T> {
    pub fn pop_back(&mut self) -> Option<T> { None }
    pub fn pop_front(&mut self) -> Option<T> { None }
}

impl<T> From<T> for SList<T> {
    fn from(v: T) -> Self {}
}

impl<T> Default for SList<T> {
    fn default() -> Self {}
}

初期化

一番簡単です。ここでは Default トレイトと Fromトレイトで実装しています。

impl<T> From<T> for SList<T> {
    fn from(v: T) -> Self {
        SList::Cons(v, Rc::new(SList::Nil))
    }
}

impl<T> Default for SList<T> {
    fn default() -> Self { SList::Nil }
}

push_front()

一番簡単なメソッドです。
Enum 自体は replace で置換するしかないですね。

1. replace で 先頭ノードの中身を吐き出させる
2. 新しい先頭ノードの次ノードにもともとのヘッドノードの内容を付け加える

    pub fn push_front(&mut self, v: T) {
        let head_node: SList<T>;
        head_node = std::mem::replace(self, SList::Nil);

        let _ = std::mem::replace(
            self, SList::Cons(v, Rc::new(head_node))
        );
    }

リファクタリング

SList::new を実装することで Rc::new() の内部構造を隠ぺいできます。
これにより pub enum SList<T> { Cons(T, Box<SList<T>>), Nil } など Rc → Box などに変更したときに、再利用できるコードが増えます。

    pub fn new(v: T, next: SList<T>) -> Self {
        SList::Cons(v, Rc::new(next))
    }

    pub fn push_front(&mut self, v: T) {
        let head_node: SList<T>;
        head_node = std::mem::replace(self, SList::Nil);

        let _ = std::mem::replace(self, SList::new(v, head_node));
    }

push_back()

まず、ループをどう回すかでかなり悩みました。
幸いなことに Rc の場合は Rc::get_mut で辛うじてループを回せることに気づいて、実現できました。

Rc::get_mut は、参照カウント・弱カウントがゼロの場合のみ使えるとても制約の強いものです。Rc<RefCll> 版で多用していた Rc::clone() は今回は使えません。引数の &mut が論理に大きな影響を与えます。RefCell を使ったほうがよほど楽。

• 最初のmatchブロックは、どのメソッドでも大抵必要になります。self が SList::Nil かそれ以外なのかを判別することから始まります
  Enum版の興味深いところはここですね。自分自身が Nil という状態を作れます。
• 後半のループは Rc::get_mut() で &mut Rc<_> を得て制御しています。
  • Slist::Nil のルートを break して外だししようとしたら、書き込みで借用している関係でコンパイルはできませんでした (これ以外の書き方が難しいという意味でかなり巧妙なコードです)

    pub fn push_back(&mut self, v: T) {
        let mut cur_rc_ref = match self {
            SList::Nil => {
                let _ = std::mem::replace(
                    self, SList::Cons(v, Rc::new(SList::Nil)) 
                );
                return;
            },
            SList::Cons(_, next_rc_ref) => next_rc_ref,
        };

        while let Some(node_ref) = Rc::get_mut(cur_rc_ref) {
            cur_rc_ref = match node_ref {
                SList::Cons(_, next_rc_ref) => next_rc_ref,
                SList::Nil => {
                    *node_ref = SList::Cons(v, Rc::new(SList::Nil));
                    return;
                },
            };
        }
    }

追記: リファクタリング

RefCellを使っていない関係で、更新手段が乏しく Rc::get_mut() に頼るため、Boxのような占有状態の制御となり、このケースにおいてはRcをループ変数とするメリットがありません。ループ変数を &mut Rc<SList<T>> から &mut SList<T> とするほうが都合が良いです。

こうすることで、 self とループ変数の型が一緒になるので、先頭部分とそれ以降の処理を別々とする必要がなくなります。あと、実は Rc::get_mut は next の変数に対して適用すればよく、書き直したコードは次のようになります。

    pub fn push_back(&mut self, v: T) {
        let mut cur_rc_ref_mut = self;

        while let SList::Cons(_, next_rc_ref_mut) = cur_rc_ref_mut {
            cur_rc_ref_mut = Rc::get_mut(next_rc_ref_mut).unwrap();
        }

        let _ = std::mem::replace(cur_rc_ref_mut, SList::from(v));
    }

pop_front()

今回は Clone を必要としてます。replaceをうまく使えば不要にできるかもしれません。

• 最初の match は先頭の次ノードを指す Rcの参照を返却します
• 後半
  • Rc::get_mut()で replaceの要求する&mut` を指定できるので、self の参照をなくしています
  • その次に head 自体をもともとの次ノードで置換します
  • 最後の replace の復帰値に先頭ノードの値も入っているのですが、match 構文を使わないと value が取り出せないので、最初の match 構文中で value の取り出しをしています。

impl<T: Clone> SList<T> {
    pub fn pop_front(&mut self) -> Option<T> {
        let some_value: Option<T>;

        let head_rc_ref: &mut Rc<_> = match self {
            SList::Nil => return None,
            SList::Cons(v_ref, head_rc_ref) => {
                some_value = Some(v_ref.clone());
                head_rc_ref
            },
        };

        let head_node: SList<T>;
        head_node = std::mem::replace(
            Rc::get_mut(head_rc_ref).unwrap(), SList::Nil
        );
        let _ = std::mem::replace(self, head_node);
        some_value
    }
}

pop_back()

難しすぎて挫折しそうになったものです。
初期のコードから1/3ぐらいにスリム化しています。相当巧妙だと思います。

単方向リストにて素朴な実装をすると、prev ポインターと next ポインターを用いて、next が NULL終端の時に prev->next のポインターを書き換える操作をします。同じことをしようとすると、今回は mut で排他的に操作しているのでコンパイルすらできません。
そのため、ポインターの先読みをして一つ前の prev ノードの判定を行います。
この判定自体を排他的に行ってしまうと、あとの replace のときに借用で怒られるので、メソッドチェーンで1行で収まるように判定を加えています。何気に関数を使わず match や if でその場でロジックを書くと比較的はまります。

そのため、次の方針を取ると良いことが分かってきます。

• cur, next と複数ポインターを扱うのを諦める
• ループ変数は prev (一つ前のNull終端のポインター)を用いる
• while let は借用の影響範囲が大きいので loop を使い局所的に借用する

そのほか、雑多な話

• loop では復帰値を渡せるので、ループは変数の所有権を渡してやることで、コードの可読性を高められる
• unwrap_or
  別に使わなくても良いのですが、これを使うことで if ブロックを1行にかけました。
  next_ref() で None が流れて来たときに None -> false の変換ができます。正常時は Some(true) -> true です。
• Rc::get_mut(prev_rc_ref)?.next_ref_mut()? は unwrap できないときに retrun してくれるのでコードを短くするのに役立ちました

impl<T: Clone> SList<T> {
    pub fn pop_back(&mut self) -> Option<T> {
        let get_value = |n: SList<T>| {
            match n {
                SList::Nil => None,
                SList::Cons(v_ref, _) => Some(v_ref.clone()),
            }
        };
        let mut prev_rc_ref = match self {
            SList::Nil => return None,
            SList::Cons(_v_ref, next_rc_ref) => {
                if next_rc_ref.is_nil() {
                    // SList(x) -> SList(Nil)
                    // v
                    // SList(Nil)
                    return get_value(
                        std::mem::replace(self, SList::Nil)
                    );
                }
                next_rc_ref
            }
        };

        let tail_prev_rc_ref = loop {
            let is_prev_tail: bool = prev_rc_ref.next_ref().map(
                |next_ref| next_ref.is_nil()
            ).unwrap_or(false);
            if is_prev_tail { break prev_rc_ref }

            prev_rc_ref = Rc::get_mut(prev_rc_ref)?.next_ref_mut()?;
        };

        let tail_node: SList<T> = std::mem::replace(
            Rc::get_mut(tail_prev_rc_ref).unwrap(), SList::Nil
        );
        return get_value(tail_node)
    }
}

impl<T> SList<T> {
    fn is_nil(&self) -> bool {
        match self {
            SList::Nil => true,
            _ => false,
        }
    }

    fn next_ref(&self) -> Option<&Rc<SList<T>>> {
        match self {
            SList::Nil => None,
            SList::Cons(_, next_rc_ref) => {
                Some(next_rc_ref)
            },
        }
    }

    fn next_ref_mut(&mut self) -> Option<&mut Rc<SList<T>>> {
        match self {
            SList::Nil => None,
            SList::Cons(_, next_rc_ref) => {
                Some(next_rc_ref)
            },
        }
    }
}

コード全体

use std::fmt::{Debug, Formatter, Result};
use std::rc::Rc;

pub enum SList<T> {
    Cons(T, Rc<SList<T>>),
    Nil,
}

impl<T> SList<T> {
    pub fn new(v: T, next: SList<T>) -> Self {
        SList::Cons(v, Rc::new(next))
    }

    fn is_nil(&self) -> bool {
        matches!(self, SList::Nil)
    }

    fn next_ref(&self) -> Option<&Rc<SList<T>>> {
        match self {
            SList::Nil => None,
            SList::Cons(_, next_rc_ref) => {
                Some(next_rc_ref)
            },
        }
    }

    fn next_ref_mut(&mut self) -> Option<&mut Rc<SList<T>>> {
        match self {
            SList::Nil => None,
            SList::Cons(_, next_rc_ref) => {
                Some(next_rc_ref)
            },
        }
    }

    /// # Examples
    ///
    /// ```
    /// use slist_rc_enum::SList;
    /// let mut list: SList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// list.push_back(3);
    /// assert_eq!(
    ///     format!("{:?}", &list).as_str(),
    ///     "SList(1) -> SList(2) -> SList(3) -> SList(Nil)"
    /// );
    /// ```
    pub fn push_back(&mut self, v: T) {
        let mut cur_slist_ref_mut = self;

        while let SList::Cons(_, next_rc_ref_mut) = cur_slist_ref_mut {
            // &mut SList<T> <- &mut Rc<SList<T>>
            cur_slist_ref_mut = Rc::get_mut(next_rc_ref_mut).unwrap();
        }

        let _ = std::mem::replace(cur_slist_ref_mut, SList::from(v));
    }

    /// # Examples
    ///
    /// ```
    /// use slist_rc_enum::SList;
    /// let mut list: SList<u8> = Default::default();
    /// list.push_front(1);
    /// list.push_front(2);
    /// list.push_front(3);
    /// assert_eq!(
    ///     format!("{:?}", &list).as_str(),
    ///     "SList(3) -> SList(2) -> SList(1) -> SList(Nil)"
    /// );
    /// ```
    pub fn push_front(&mut self, v: T) {
        let head_node: SList<T>;
        head_node = std::mem::replace(self, SList::Nil);

        let _ = std::mem::replace(self, SList::new(v, head_node));
    }

    /// # Examples
    ///
    /// ```
    /// use slist_rc_enum::SList;
    /// let mut list: SList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.pop_back(), Some(2));
    /// assert_eq!(list.pop_back(), Some(1));
    /// assert_eq!(list.pop_back(), None);
    /// ```
    pub fn pop_back(&mut self) -> Option<T> {
        let get_value = |n: SList<T>| {
            match n {
                SList::Nil => None,
                SList::Cons(v_ref, _) => Some(v_ref),
            }
        };
        let mut prev_rc_ref = match self {
            SList::Nil => return None,
            SList::Cons(_v_ref, next_rc_ref) => {
                if next_rc_ref.is_nil() {
                    // SList(x) -> SList(Nil)
                    // v
                    // SList(Nil)
                    return get_value(
                        std::mem::replace(self, SList::Nil)
                    );
                }
                next_rc_ref
            }
        };

        let tail_prev_rc_ref = loop {
            let is_prev_tail: bool = prev_rc_ref.next_ref().map(
                |next_ref| next_ref.is_nil()
            ).unwrap_or(false);
            if is_prev_tail { break prev_rc_ref }

            prev_rc_ref = Rc::get_mut(prev_rc_ref)?.next_ref_mut()?;
        };

        let tail_node: SList<T> = std::mem::replace(
            Rc::get_mut(tail_prev_rc_ref).unwrap(), SList::Nil
        );
        get_value(tail_node)
    }

    /// # Examples
    ///
    /// ```
    /// use slist_rc_enum::SList;
    /// let mut list: SList<u8> = Default::default();
    /// list.push_back(1);
    /// list.push_back(2);
    /// assert_eq!(list.pop_front(), Some(1));
    /// assert_eq!(list.pop_front(), Some(2));
    /// assert_eq!(list.pop_front(), None);
    /// ```
    pub fn pop_front(&mut self) -> Option<T> {
        let head_rc_ref = self.next_ref_mut()?;

        let head_node: SList<T>;
        head_node = std::mem::replace(
            Rc::get_mut(head_rc_ref).unwrap(), SList::Nil
        );
        let head_node_old = std::mem::replace(self, head_node);
        match head_node_old {
            SList::Nil => None,
            SList::Cons(v_ref, _) => Some(v_ref)
        }
    }
}

impl<T> From<T> for SList<T> {
    fn from(v: T) -> Self { SList::new(v, SList::Nil) }
}

impl<T> Default for SList<T> {
    fn default() -> Self { SList::Nil }
}

impl<T: Debug> Debug for SList<T> {
    fn fmt(&self, f: &mut Formatter<'_>) -> Result {
        if let SList::Cons(v, n) = self {
            write!(f, "SList({v:?}) -> {n:?}")
        } else {
            write!(f, "SList(Nil)")
        }
    }
}

# [cfg(test)]
mod tests;

まとめ

全体的にコード量は増えますが、値を取り出す関数を追加していくと主要な論理は Struct と同等かそれより短くなります。

• Enum は構造体に None 相当を組み込めることは利点となる (ただし大きい構造体の埋め込みは注意)
• Option型はで済むならそっちを使ったほうが良い
  • Option型にあるようなメソッドを自作をする手間は増えるため
  • Option型には非常に多くの機能があって便利だということに気づく
• Struct でなく Enum を使うと値の取り出しに if let / while let / match 構文が必要
  • if let / while let / match では可変借用などの影響が及ぶこともあり、悩ましい状況に遭遇しやすくなる (mut用メソッドと Imutable用メソッドを使い分ける必要に駆られる)
• 今回は、おそらく Rc<RefCell<_>> としていたなら苦労が少なかったはず
  どこかのサンプルが Rc だったのでそれに従って、どこまでできるのかを試す意図もあった