Final Code

Five sections, one persistent stack with shared tails and an iterative Drop. Using Arc rather than Rc so the result is thread-safe by default; flip the import to std::rc::Rc if you only need single-threaded performance.

1. 01
   The complete persistent list. Read it next to Chapter 1's stack — same skeleton, different ownership story.

   use std::sync::Arc;
   
   pub struct List<T> {
       head: Link<T>,
   }
   
   type Link<T> = Option<Arc<Node<T>>>;
   
   struct Node<T> {
       elem: T,
       next: Link<T>,
   }
   
   impl<T> List<T> {
       pub fn new() -> Self {
           List { head: None }
       }
   
       pub fn prepend(&self, elem: T) -> List<T> {
           List {
               head: Some(Arc::new(Node {
                   elem,
                   next: self.head.clone(),
               })),
           }
       }
   
       pub fn tail(&self) -> List<T> {
           List {
               head: self.head.as_ref().and_then(|node| node.next.clone()),
           }
       }
   
       pub fn head(&self) -> Option<&T> {
           self.head.as_ref().map(|node| &node.elem)
       }
   }
   
   impl<T> Drop for List<T> {
       fn drop(&mut self) {
           let mut head = self.head.take();
           while let Some(node) = head {
               if let Ok(mut node) = Arc::try_unwrap(node) {
                   head = node.next.take();
               } else {
                   break;
               }
           }
       }
   }
   
   #[cfg(test)]
   mod tests {
       use super::*;
   
       #[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 of empty is empty.
           let list = list.tail();
           assert_eq!(list.head(), None);
       }
   }