Minimal list definition in Rust

Question

As a purely pedagogical exercise, I've been trying to use Rust's (very expressive) type system to define the bare minimum one might expect from an ordinary list type.

While there's likely a higher-level argument here about mutable vs immutable lists, and how lists should be implemented in Rust, please note that this is purely an educational exercise.

One thing I've encountered, is that Rust lends itself to quite some verbosity with respect to the number of different logical blocks of code one might need in order to comply with prevailing conventions. I'm unsure as to whether this is actually true of Rust itself, or due to my own misunderstandings about Rust as a language and as an ecosystem.

---

list.rs:

use std::fmt::Debug;
use std::ops::{Index, IndexMut};

pub trait List<T: Sized + Clone + Eq + Debug>:
    Eq + Index<usize> + IndexMut<usize> + IntoIterator + Debug
{
    type Error;

    fn insert(&mut self, pos: usize, elem: T) -> Result<(), Self::Error>;
    fn remove(&mut self, pos: usize) -> Result<T, Self::Error>;
    fn length(&self) -> usize;
    fn contains(&self, elem: T) -> bool;
}

veclist.rs:

#![allow(clippy::unit_arg)]
use std::cmp::Ordering;
use std::fmt::Debug;
use std::ops::{Index, IndexMut};

use crate::list::List;

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct VecList<T: Clone + Debug + Eq> {
    pub elems: Vec<T>,
}

impl<T: Clone + Debug + Eq> List<T> for VecList<T> {
    type Error = String;

    fn insert(&mut self, pos: usize, elem: T) -> Result<(), Self::Error> {
        match pos.cmp(&self.elems.len()) {
            Ordering::Less => Ok(self.elems.insert(pos, elem)),
            Ordering::Equal => Ok(self.elems.push(elem)),
            Ordering::Greater => Err("Out of bounds".to_string()),
        }
    }

    fn remove(&mut self, pos: usize) -> Result<T, Self::Error> {
        match pos.cmp(&self.elems.len()) {
            Ordering::Less => Ok(self.elems.remove(pos)),
            _ => Err("Out of bounds".to_string()),
        }
    }

    fn length(&self) -> usize {
        self.elems.len()
    }

    fn contains(&self, elem: T) -> bool {
        self.iter().any(|x| x == elem)
    }
}

impl<T: Clone + Debug + Eq> VecList<T> {
    pub fn iter(&self) -> VecListIterator<T> {
        self.into_iter()
    }
}

impl<T: Clone + Debug + Eq> Index<usize> for VecList<T> {
    type Output = T;

    fn index(&self, pos: usize) -> &Self::Output {
        &self.elems[pos]
    }
}

impl<T: Clone + Debug + Eq> IndexMut<usize> for VecList<T> {
    fn index_mut(&mut self, pos: usize) -> &mut Self::Output {
        &mut self.elems[pos]
    }
}

pub struct VecListIterator<T: Clone + Debug + Eq> {
    pos: usize,
    list: VecList<T>,
}

impl<T: Clone + Debug + Eq> Iterator for VecListIterator<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.pos < self.list.length() {
            self.pos += 1;
            Some(self.list[self.pos - 1].clone())
        } else {
            None
        }
    }
}

impl<T: Clone + Debug + Eq> IntoIterator for VecList<T> {
    type Item = T;
    type IntoIter = VecListIterator<T>;

    fn into_iter(self) -> Self::IntoIter {
        VecListIterator { pos: 0, list: self }
    }
}

impl<T: Clone + Debug + Eq> IntoIterator for &VecList<T> {
    type Item = T;
    type IntoIter = VecListIterator<T>;

    fn into_iter(self) -> Self::IntoIter {
        VecListIterator {
            pos: 0,
            list: self.clone(),
        }
    }
}

impl<T: Clone + Debug + Eq> IntoIterator for &mut VecList<T> {
    type Item = T;
    type IntoIter = VecListIterator<T>;

    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

---

1. Is the definition of the list type, List<T>, sensible?
2. Is the implementation of the list type, VecList<T>, sensible?
3. Are there any defects in the codebase itself?

Answer 1

Don't force unnecessary bounds on your trait

You're requiring many bounds on your trait that simply aren't necessary. For example, it's nice to have the Debug trait so you can easily print out debug information, but you're currently having that as a requirement in order to implement your trait List. So try to reduce the trait bounds to just what's necessary and let the actual implementation decide on what trait they want to implement.

Your List trait actually doesn't need any trait bounds. It could be just:

pub trait List<T>: Eq + Index<usize> + IndexMut<usize> + IntoIterator

Logically, methods like contains will probably need to implement the trait Eq, but they don't have to. If someone came up with a perfect hash function, then it would be quite annoying to still require all types to be comparable. Times when you need to add the trait are when you want to create default implementations that requires it.

Your iterators are not correct

Neither your immutable nor mutable iterator iterates over your actual data! Your immutable iterator is cloning the whole list and gives immutable references to your copied list. While semantically correct, it's very wasteful in respect to both memory and speed. Your mutable iterator calls iter which in turn calls into_iter for &VecList which then copies your vector. This is wasteful as well but is also semantically wrong. Modifying the values will not change the original list. A simple test confirms this:

#[test]
fn modify_values() {
    let mut x = VecList { elems: vec![1, 2, 3] };
    
    for mut i in &mut x {
        i += 1;
    }
    
    assert_eq!(x.elems, vec![2, 3, 4]);
}

Gives:

thread 'modify_values' panicked at 'assertion failed: `(left == right)`
  left: `[1, 2, 3]`,
 right: `[2, 3, 4]`', src/lib.rs:127:5

Implementing an immutable iterator is quite easy:

pub struct ImmutableVecListIterator<'a, T: Eq + Clone> {
    pos: usize,
    list: &'a VecList<T>,
}

impl<'a, T: Eq + Clone> Iterator for ImmutableVecListIterator<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.pos < self.list.length() {
            self.pos += 1;
            Some(&self.list[self.pos - 1])
        } else {
            None
        }
    }
}


impl<'a, T: Eq + Clone> IntoIterator for &'a VecList<T> {
    type Item = &'a T;
    type IntoIter = ImmutableVecListIterator<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        ImmutableVecListIterator {
            pos: 0,
            list: self,
        }
    }
}

Note that you probably need 3 different iterators: 1 that owns VecList, 1 that borrows VecList, and one that mutably borrows VecList.

Implementing the other one's are harder. The mutable iterator requires unsafe code. What you can do is to rely on already existing implementations, like the one that already exists on Vec.

impl<'a, T: Eq + Clone> IntoIterator for &'a mut VecList<T> {
    type Item = &'a mut T;
    type IntoIter = std::slice::IterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.elems.iter_mut()  // Use the `Vec`'s mutable iterator.
    }
}

Always write tests!

As shown in the example above, it's quite easy to verify if you've done something correctly by writing simple tests. It also helps other to understand your code better as it both documents how to use our code and what the expected result should be.

An example

Here's an simple example on some of the improvements that can be made, but more could be made to improve soundness, like for example specifying that IntoIterator on the List trait should return T with IntoIterator<Item=T>, among others.

use std::ops::{Index, IndexMut};
use std::cmp::Ordering;


pub trait List<T>: 
    Eq + Index<usize> + IndexMut<usize> + IntoIterator
{
    type Error;

    fn insert(&mut self, pos: usize, elem: T) -> Result<(), Self::Error>;
    fn remove(&mut self, pos: usize) -> Result<T, Self::Error>;
    fn length(&self) -> usize;
    fn contains(&self, elem: T) -> bool;
}


#[derive(Clone, Eq, PartialEq)]
pub struct VecList<T: Eq + Clone> {
    pub elems: Vec<T>,
}


impl<T: Eq + Clone> List<T> for VecList<T> {
    type Error = String;

    fn insert(&mut self, pos: usize, elem: T) -> Result<(), Self::Error> {
        match pos.cmp(&self.elems.len()) {
            Ordering::Less    => Ok(self.elems.insert(pos, elem)),
            Ordering::Equal   => Ok(self.elems.push(elem)),
            Ordering::Greater => Err("Out of bounds".to_string()),
        }
    }

    fn remove(&mut self, pos: usize) -> Result<T, Self::Error> {
        match pos.cmp(&self.elems.len()) {
            Ordering::Less => Ok(self.elems.remove(pos)),
            _ => Err("Out of bounds".to_string()),
        }
    }

    fn length(&self) -> usize {
        self.elems.len()
    }

    fn contains(&self, elem: T) -> bool {
        self.iter().any(|x| *x == elem)
    }
}


impl<T: Eq + Clone> VecList<T> {
    pub fn iter(&self) -> RefVecListIterator<T> {
        self.into_iter()
    }
}


impl<T: Eq + Clone> Index<usize> for VecList<T> {
    type Output = T;

    fn index(&self, pos: usize) -> &Self::Output {
        &self.elems[pos]
    }
}

impl<T: Eq + Clone> IndexMut<usize> for VecList<T> {
    fn index_mut(&mut self, pos: usize) -> &mut Self::Output {
        &mut self.elems[pos]
    }
}


pub struct VecListIterator<T: Eq + Clone> {
    pos: usize,
    list: VecList<T>,
}

impl<T: Eq + Clone> Iterator for VecListIterator<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.pos < self.list.length() {
            self.pos += 1;
            Some(self.list[self.pos - 1].clone())
        } else {
            None
        }
    }
}

impl<T: Eq + Clone> IntoIterator for VecList<T> {
    type Item = T;
    type IntoIter = VecListIterator<T>;

    fn into_iter(self) -> Self::IntoIter {
        VecListIterator { pos: 0, list: self }
    }
}


pub struct RefVecListIterator<'a, T: Eq + Clone> {
    pos: usize,
    list: &'a VecList<T>,
}

impl<'a, T: Eq + Clone> Iterator for RefVecListIterator<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.pos < self.list.length() {
            self.pos += 1;
            Some(&self.list[self.pos - 1])
        } else {
            None
        }
    }
}


impl<'a, T: Eq + Clone> IntoIterator for &'a VecList<T> {
    type Item = &'a T;
    type IntoIter = RefVecListIterator<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        RefVecListIterator {
            pos: 0,
            list: self,
        }
    }
}

impl<'a, T: Eq + Clone> IntoIterator for &'a mut VecList<T> {
    type Item = &'a mut T;
    type IntoIter = std::slice::IterMut<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
        self.elems.iter_mut()
    }
}



#[test]
fn modify_values() {
    let mut x = VecList { elems: vec![1, 2, 3] };
    
    for i in &mut x {
        *i += 1;
    }
    
    assert_eq!(x.elems, vec![2, 3, 4]);
}

Rust Playground

TL;DR

• Is the definition of the list type, List, sensible?

You should reduce the amount of trait bounds.

• Is the implementation of the list type, VecList, sensible?

Your iterators are not, and once again, you should reduce the amount of trait bounds. Also, it's usually standard practice to add constructors like new or with the Default trait. Just some way to create an instance from a function.

• Are there any defects in the codebase itself?

See above.

And to answer your implicit question: yes, Rust is very verbose if you want to implement everything yourself. This is however greatly reduced if you utilize already existing solutions, like just providing a wrapper over Vec's iterators instead of writing your own, use macros, or use other people's crates.