基本

ここまでで、Rust の基本についてはすでに多くを理解しているので、単純なことの多くは改めて実装できます。

コンストラクターについては、また単にコピー＆ペーストできます。

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }
}

push と pop は、もはやあまり意味をなしません。代わりに、ほぼ同じことを提供する prepend と tail を用意できます。

まずは先頭に追加するところから始めましょう。これはリストと要素を受け取り、List を返します。ミュータブルなリストの場合と同じく、新しいノードを作成し、その next 値として古いリストを持たせたいところです。唯一新しい点は、その next 値をどうやって取得するかです。なぜなら、何もミューテートすることは許されていないからです。

私たちの祈りへの答えは Clone トレイトです。Clone はほぼすべての型に実装されており、共有参照だけが与えられた状態で、「これと同じような別のもの」を論理的に独立した形で取得する汎用的な方法を提供します。C++ のコピーコンストラクターのようなものですが、暗黙的に呼び出されることはありません。

特に Rc は、参照カウントをインクリメントする方法として Clone を使います。そのため、Box を移動して部分リストの中に入れるのではなく、古いリストの head を clone するだけです。head に対して match する必要すらありません。Option が、まさに私たちの望むことを行う Clone 実装を提供しているからです。

よし、試してみましょう。

pub fn prepend(&self, elem: T) -> List<T> {
    List { head: Some(Rc::new(Node {
        elem: elem,
        next: self.head.clone(),
    }))}
}

> cargo build

warning: field is never used: `elem`
  --> src/third.rs:10:5
   |
10 |     elem: T,
   |     ^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

warning: field is never used: `next`
  --> src/third.rs:11:5
   |
11 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

わあ、Rust は実際にフィールドを使っているかどうかについて本当に厳格です。これらのフィールドの使用を実際に観測できるコンシューマーが存在しないことまで判断できます！とはいえ、ここまではよさそうです。

tail は、この操作の論理的な逆です。これはリストを受け取り、最初の要素を取り除いたリスト全体を返します。要するに、リスト内の2番目の要素を clone するだけです（存在する場合）。これを試してみましょう。

pub fn tail(&self) -> List<T> {
    List { head: self.head.as_ref().map(|node| node.next.clone()) }
}

cargo build

error[E0308]: mismatched types
  --> src/third.rs:27:22
   |
27 |         List { head: self.head.as_ref().map(|node| node.next.clone()) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::rc::Rc`, found enum `std::option::Option`
   |
   = note: expected type `std::option::Option<std::rc::Rc<_>>`
              found type `std::option::Option<std::option::Option<std::rc::Rc<_>>>`

うーん、やらかしました。map は Y を返すことを期待していますが、ここでは Option<Y> を返しています。ありがたいことに、これもよくある Option のパターンなので、and_then を使えば Option を返せます。

pub fn tail(&self) -> List<T> {
    List { head: self.head.as_ref().and_then(|node| node.next.clone()) }
}

> cargo build

素晴らしいです。

tail ができたので、おそらく head も提供すべきでしょう。これは最初の要素への参照を返します。これはミュータブルなリストの peek そのものです。

pub fn head(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem)
}

> cargo build

いいですね。

これでテストできるだけの機能は揃いました。

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let list = List::new();
        assert_eq!(list.head(), None);

        let list = list.prepend(1).prepend(2).prepend(3);
        assert_eq!(list.head(), Some(&3));

        let list = list.tail();
        assert_eq!(list.head(), Some(&2));

        let list = list.tail();
        assert_eq!(list.head(), Some(&1));

        let list = list.tail();
        assert_eq!(list.head(), None);

        // 空のtailが機能することを確認する
        let list = list.tail();
        assert_eq!(list.head(), None);

    }
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 5 tests
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok

test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured

完璧です！

Iter も、ミュータブルなリストのときと同じです。

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<T> List<T> {
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head.as_deref() }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_deref();
            &node.elem
        })
    }
}

#[test]
fn iter() {
    let list = List::new().prepend(1).prepend(2).prepend(3);

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&3));
    assert_eq!(iter.next(), Some(&2));
    assert_eq!(iter.next(), Some(&1));
}

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 7 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok

test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured

一体誰が動的型付けのほうが簡単だなんて言ったのでしょうか？

（間抜けな連中です）

この型には IntoIter や IterMut を実装できないことに注意してください。要素には共有アクセスしかありません。