Heterogenous persistent list in Rust

Question

I have implemented a basic, but seemingly working, persistent (as in immutable), heterogenous list type in Rust.

Here's the code:

#[derive(Debug)]
pub enum ConsCell<'a> {
    Char(char),
    Number(u64),
    String(&'a str),
}

pub struct PersistentList<'a, T: 'a> {
    first: Option<&'a T>,
    rest: Option<&'a PersistentList<'a, T>>,
    count: u64,
}

impl<'a, T> PersistentList<'a, T> {
    pub fn new() -> PersistentList<'a, T> {
        PersistentList {
            first: None,
            rest: None,
            count: 0,
        }
    }

    pub fn first(&self) -> &T {
        self.first.unwrap()
    }

    pub fn next(&self) -> Option<&PersistentList<T>> {
        if self.count == 1 {
            return None;
        }

        self.rest
    }

    pub fn cons(&'a self, x: &'a T) -> PersistentList<'a, T> {
        PersistentList {
            first: Some(x),
            rest: Some(&self),
            count: self.count + 1
        }
    }

    pub fn count(&self) -> u64 {
        self.count
    }
}

This can be used like so:

fn main() {
    let list = PersistentList::new();
    let cell = &ConsCell::Number(42);
    let list = list.cons(cell);
    let cell = &ConsCell::String(&"foo");
    let list = list.cons(cell);
    match list.first() {
        ConsCell::Char(c) => println!("{}", c),
        ConsCell::Number(n) => println!("{}", n),
        ConsCell::String(s) => println!("{}", s),
    }
}

The ergonomics of this are not fantastic, however it does seem to work. Is there a more idiomatic way of doing something similar with Rust?

Answer 1

I asked about this in the Rust beginner's IRC channel and someone helpfully pointed out that another approach might be to use trait objects and Box.

By way of illustration:

use std::fmt::Display;

pub trait Item: Display {}

impl Item for String {}
impl Item for bool {}
impl Item for char {}
impl Item for f64 {}
impl Item for u64 {}

pub struct PersistentList<T = Box<Item>> {
    first: Option<T>,
    rest: Option<Box<PersistentList<T>>>,
    count: usize,
}

impl<T> PersistentList<T> {
    pub fn new() -> PersistentList<T> {
        PersistentList {
            first: None,
            rest: None,
            count: 0,
        }
    }

    pub fn first(&self) -> Option<&T> {
        self.first.as_ref()
    }

    pub fn next(self) -> Option<Box<PersistentList<T>>> {
        self.rest
    }

    pub fn cons(self, item: T) -> PersistentList<T> {
        let count = &self.count + 1;
        PersistentList {
            first: Some(item),
            rest: Some(Box::new(self)),
            count,
        }
    }

    pub fn count(&self) -> usize {
        self.count
    }
}

The advantage here is that we can simply implement Item for any given type and our collection will be capable of handling it. Here's a Playground link.

Now I think it's only fair to leave this question open for a while: I'm new to Rust and still learning and I'm unsure of the best practices and idioms--that said, this seems to be a pretty decent approach.