How to mutate reference while moving ownership in recursive data struct?

Question

I tried to implement ConsList data structure, where it came from functional paradigm language like Lisp or Haskell. Here some snippet for it:

use ConsList::*;
enum ConsList<T> {
    Empty,
    List(T, Box<ConsList<T>>),
}

impl<T> ConsList<T> {
    fn new() -> ConsList<T> {
        Empty
    }

    // I don't know whether to use & or not at self parameter
    fn insert_first(&mut self, value: T) -> &Self {
        // unkown implementation
    }
    
    fn head(&mut self) -> Option<T> {
        // unkown implementation
    }
}

fn main() {
    let mut list_var: ConsList<i32> = ConsList::new(); // Initiate
    list_var.insert_first(2); // First insert
    list_var.insert_first(1); // Second insert
}

I wanted for insert_first function to behave like this:

1. Create new list with value at first position in new list tuple
2. Move value to the tail of new list
3. Replace owner variable (list_var) with new list

For example, when initiating, we have Empty value for list_var variable. Then at first insert, it will create new value List(2, Empty), where 2 moved from value, and Empty moved from old list before mutation, and we mutate self variable to new list. In other word, we mutate list_var variable. For more in depth, here what I meant step by step at second insert:

1. Move list_var (List(2, Empty)) to parameter self in insert_first method
2. Move 1 to parameter value in insert_first method
3. Create new list with value and self moved to the new one, List(3, List(2, Empty))
4. Mutate self with the new list, so list_var variable will be the new list too

The problem here, we can only either:

• Transfer ownership without reference (we can't mutate list_var)
• Borrowing without being able to move (we can't move old list to new list)

As far as I know, we can't transfer ownership while being able to mutate with reference. There are some reason why this is useful. Method head will return first element of the list and mutate list to tail (I know mutation is not a thing in functional programming, but this will save storage and performance from copying new list). This method need to be able mutate self, move first element to return value, and move ownership of list tail to self.

I tried to use box for indirection, but still I can't move self.list because it's behind a reference

enum ConsListElem<T> {
    Empty,
    List(T, Box<ConsListElem<T>>),
}

pub struct ConstList<T> {
    list: Box<ConsListElem<T>>,
}

impl<T> ConstList<T> {
    pub fn cons(&mut self, value: T) -> &ConstList<T> {
        self.list = Box::new(ConsListElem::List(value, self.list));
        self
    }
}

Answer 1

You can use std::mem::replace to modify something behind mutable reference and return the old value. So inside insert_first you can firstly replace self with Empty variant, and then create new List and assign it to self.

enum ConsList<T> {
    Empty,
    List(T, Box<ConsList<T>>),
}

impl<T> ConsList<T> {
    fn new() -> ConsList<T> {
        Self::Empty
    }

    fn insert_first(&mut self, value: T) -> &mut Self {
        match self {
            Self::Empty => {
                *self = Self::List(value, Box::new(Self::new()))
            }
            Self::List(_, _) => {
                let old = std::mem::replace(self, Self::new());
                *self = Self::List(value, Box::new(old));
            }
        }
        self
    }
    
    fn head(&self) -> Option<&T> {
        match self {
            Self::Empty => None,
            Self::List(head, _) => Some(head),
        }
    }
}

fn main() {
    let mut list_var: ConsList<i32> = ConsList::new(); // Initiate
    assert_eq!(list_var.head(), None);
    list_var.insert_first(2); // First insert
    assert_eq!(list_var.head(), Some(&2));
    list_var.insert_first(1); // Second insert
    assert_eq!(list_var.head(), Some(&1));
}