list.rs

use std::rc::Rc;

pub enum List<T> {
    Node { value: T, next: Rc<List<T>> },
    Empty,
}

impl <T> List<T> {
    pub fn empty() -> Self {
        List::Empty
    }

    pub fn new(v: T) -> Rc<Self> {
        Rc::new(List::Node{
            value: v,
            next: Rc::new(List::Empty),
        })
    }

    pub fn is_empty(&self) -> bool {
        match self {
            List::Node{value: _, next: _} => false,
            List::Empty => true,
        }
    }

    /// head gives a reference to the value at the front of this list
    pub fn head(&self) -> Option<&T> {
        match self {
        List::Node{value, next} => Some(value),
        List::Empty => None,
        }
    }

    /// len computs the number of elements visible from this list node
    pub fn len(&self) -> u32 {
        let mut node = self;
        let mut count: u32 = 0;

        loop {
            match node {
                List::Node{value, next} => {
                    count += 1;
                    node = next;
                },
                List::Empty => return count,
            }
        }
    }

    /// pre prepends a value onto a list node. That is, it takes a list node and creates a new list
    /// node that points to it, returning the new list node.
    pub fn pre(self: &Rc<Self>, v: T) -> Rc<Self> {
        Rc::new(List::Node{
            value: v,
            next: Rc::clone(self),
        })
    }
}

main.rs

mod list;
use list::*;

fn dump<T: std::fmt::Display>(l: &List<T>) {
    match l {
        List::Node{value, next} => {
            println!("{}", value);
            dump(next);
        },
        List::Empty => return,
    }
}

fn main() {
    let root = List::pre(&List::new(100), 77);
    let mut a = root.pre(12);
    let mut b = root.pre(18);
    b = List::pre(&b, 7);
    println!("count from root: {}", root.len());
    println!("count from a: {}", a.len());
    println!("count from b: {}", b.len());
    println!("a head: {:?}", a.head());
    println!("dumping a");
    dump(&a);
    println!("dumping b");
    dump(&b);
    println!("dumping root");
    dump(&root);
}