Trying to get cons-list working

I'm trying to implement a lisp style cons-list. I've created these two types for holding the data.

    #[derive(Debug)]
    enum List<T>{
        Cons(T, Box<List<T>>),
        None
    }

    #[derive(Debug)]
    pub struct ConsList<T> {
        member: List<T>
    }

Now a list can be initialized like this:

let first_list = List::Cons(
    1,
    Box::new(List::Cons(2, Box::new(List::Cons(3, Box::new(List::None))))),
);

I have a method called append to add new items to the list. It looks like this:

impl<T> ConsList<T> {
    pub fn new_list() -> ConsList<T> {
        ConsList { member: List::None }
    }

    pub fn append(&mut self, item: T) {
        if self.member.is_empty_list(){
            self.member = List::Cons(item, Box::new(List::None));
        } else{
            let mut tail = last_cons_pair(&mut self.member.).unwrap();
            if let List::Cons(_, mut cdr) = *tail {
                *cdr = Box::new(List:Cons(item , Box::new(List::None)));
            }
        }
    }
}

The idea is to make the last_cons_pair() function return a mutable reference to the last List<T> whose tail points to List::None. Now using this reference remove the Box referencing List::None and add a new nested box containing the new element and the terminating List::None.

What my last_cons_pair() function looks like(Doesn't compile):

pub fn last_cons_pair<T>(list: &mut List<T>) -> Option<&mut List<T>> {
    match *list {
        List::None => None,
        List::Cons(_, tail) => match *tail {
            List::None => Some(list),
            List::Cons(_, cdr) => last_cons_pair(&mut *cdr),
        },
    }
}

The problem is I can't get the function last_cons_pair() to compile. I've spent couple of hours trying to figure it out and is now completely disappointed by my inability to solve something this trivial.
So now I'm thinking maybe what I'm trying to do is not idiomatic rust? So can you guys please help me to solve this problem? What would be the idiomatic way to get last_cons_pair() to work?

Can't help with the specifics, but are you aware of Introduction - Learning Rust With Entirely Too Many Linked Lists?

4 Likes

Thank you so much, Exactly what I was looking for. The official Rust book just covers the absolute trivial stuff when it comes to code/snippets related to smart pointers.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.