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?

• Zeta: Why doesn't your PersistentList own any value?
• maxcountryman: @Zeta I was having difficulty with owned values--I'm very new to Rust and I'm sure there is a better way of handling that shortcoming.
• Zeta: Just to be sure: you're also interested in a review that shows how to be able to move PersistentLists around, without being limited to the lifetime of their surroundings, right? Or rather: did you take inspiration from another programming language/implementation?
• maxcountryman: I think that's right. In an ideal implementation you'd be able to add elements of virtually any type and pass the list around as you saw fit. So what I'm after is an immutable, heterogenous linked-list.

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.