Heterogenous persistent list in Rust 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&lt;'a&gt; {
    Char(char),
    Number(u64),
    String(&amp;'a str),
}

pub struct PersistentList&lt;'a, T: 'a&gt; {
    first: Option&lt;&amp;'a T&gt;,
    rest: Option&lt;&amp;'a PersistentList&lt;'a, T&gt;&gt;,
    count: u64,
}

impl&lt;'a, T&gt; PersistentList&lt;'a, T&gt; {
    pub fn new() -&gt; PersistentList&lt;'a, T&gt; {
        PersistentList {
            first: None,
            rest: None,
            count: 0,
        }
    }

    pub fn first(&amp;self) -&gt; &amp;T {
        self.first.unwrap()
    }

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

        self.rest
    }

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

    pub fn count(&amp;self) -&gt; u64 {
        self.count
    }
}


This can be used like so:

fn main() {
    let list = PersistentList::new();
    let cell = &amp;ConsCell::Number(42);
    let list = list.cons(cell);
    let cell = &amp;ConsCell::String(&amp;"foo");
    let list = list.cons(cell);
    match list.first() {
        ConsCell::Char(c) =&gt; println!("{}", c),
        ConsCell::Number(n) =&gt; println!("{}", n),
        ConsCell::String(s) =&gt; 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?
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&lt;T = Box&lt;Item&gt;&gt; {
    first: Option&lt;T&gt;,
    rest: Option&lt;Box&lt;PersistentList&lt;T&gt;&gt;&gt;,
    count: usize,
}

impl&lt;T&gt; PersistentList&lt;T&gt; {
    pub fn new() -&gt; PersistentList&lt;T&gt; {
        PersistentList {
            first: None,
            rest: None,
            count: 0,
        }
    }

    pub fn first(&amp;self) -&gt; Option&lt;&amp;T&gt; {
        self.first.as_ref()
    }

    pub fn next(self) -&gt; Option&lt;Box&lt;PersistentList&lt;T&gt;&gt;&gt; {
        self.rest
    }

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

    pub fn count(&amp;self) -&gt; 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.