Heterogenous persistent list in 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.