Typed linked lists in Rust

dynamic.rs

use std::fmt::Display;

// Our stack-allocated, typed, linked list
struct TypedLinkedList<E, R> where E: MyTrait, R: Traverse {
    value: E,
    rest: R,
}


// Denotes the end of the list
struct Empty;

impl<E: MyTrait, R: Traverse> TypedLinkedList<E, R> {
    fn new(v: E) -> TypedLinkedList<E, Empty> {
        TypedLinkedList {
            value: v,
            rest: Empty
        }
    }
    // Note how the type-parameters 'shift along'
    fn add<N>(self, v: N) -> TypedLinkedList<N, TypedLinkedList<E, R>>
        where N: MyTrait
    {
        TypedLinkedList {
            value: v,
            rest: self
        }
    }
}

// Now it takes a closure
trait Traverse: {
    fn traverse<T, F: Fn(T, &MyTrait) -> T>(self, acc: T, func: F) -> T;
}


// Do 'nothing'
impl Traverse for Empty {
    fn traverse<T, F: Fn(T, &MyTrait) -> T>(self, acc: T, _func: F) -> T {
        acc
    }
}

// Increment the accumulator and pass onward
impl<E: MyTrait, R: Traverse> Traverse for TypedLinkedList<E, R> {
    fn traverse<T, F: Fn(T, &MyTrait) -> T>(self, acc: T, func: F) -> T {
        let acc = func(acc, &self.value);
        self.rest.traverse(acc, func)
    }
}

trait MyTrait : Display { fn numberify(&self) -> f64; }
impl MyTrait for i32 { fn numberify(&self) -> f64 { *self as f64 } }
impl MyTrait for f64 { fn numberify(&self) -> f64 { *self } }
impl MyTrait for &'static str { fn numberify(&self) -> f64 { self.len() as f64 } }

fn main() {
    let list = TypedLinkedList::<_, Empty>::new(1i32)
        .add(2.0)
        .add("hello")
        .add(100)     // Just add as many lines as you like...
        .add(3.141592)  
        .add("just keep going")
        .add(10000);  
    let x = list.traverse(0f64,|acc, v| acc + v.numberify());
    println!("Numberified: {}", x);
}

simple.rs

#![feature(core_intrinsics)]

use std::fmt::Display;

// Our stack-allocated, typed, linked list
struct TypedLinkedList<E, R> where E: MyTrait, R: Traverse {
    value: E,
    rest: R,
}


// Denotes the end of the list
struct Empty;

impl<E: MyTrait, R: Traverse> TypedLinkedList<E, R> {
    fn new(v: E) -> TypedLinkedList<E, Empty> {
        TypedLinkedList {
            value: v,
            rest: Empty
        }
    }
    // Note how the type-parameters 'shift along'
    fn add<N>(self, v: N) -> TypedLinkedList<N, TypedLinkedList<E, R>>
        where N: MyTrait
    {
        TypedLinkedList {
            value: v,
            rest: self
        }
    }
}

// Trait that allows us to walk the list
trait Traverse: {
    fn traverse(self);
}

// End of list - do nothing
impl Traverse for Empty {
    fn traverse(self) {}
}

// Print some info, then call recursively
impl<E: MyTrait, R: Traverse> Traverse for TypedLinkedList<E, R> {
    fn traverse(self) {
        print!("List size: {:2}, ", std::mem::size_of::<Self>());
        print!("Elem size: {:2}, ", std::mem::size_of::<E>());
        print_type_of(&self.value);
        println!("Value: {}", self.value);
        self.rest.traverse()
    }
}

fn print_type_of<T>(_: &T) -> () {
    // Note: feature requires nightly
    let type_name = unsafe { std::intrinsics::type_name::<T>() };
    print!("Type: {:15}", type_name);
}

trait MyTrait : Display {}
// Implement MyTrait on any types you want to put in the list
impl MyTrait for i32 {}
impl MyTrait for f64 {}
impl MyTrait for &'static str {}

fn main() {
    let list = TypedLinkedList::<_, Empty>::new(1i32)
        .add(2.0)
        .add("hello")
        .add(100)     // Just add as many lines as you like...
        .add(3.141592)  
        .add("just keep going")
        .add(10000);  
    list.traverse();
}

static.rs

use std::fmt::Display;

// TypedLinkedList signature has changed to constrain the type bound
// on 'Traverse' to equal the 'Output' associated type
// on E (in our example, f64)
struct TypedLinkedList<E, R> where E: MyTrait, R: Traverse<<E as MyFunc>::Output> {
    value: E,
    rest: R,
}

// Denotes the end of the list
struct Empty;

impl<E: MyTrait, R: Traverse<<E as MyFunc>::Output>> TypedLinkedList<E, R> {
    fn new(v: E) -> TypedLinkedList<E, Empty> {
        TypedLinkedList {
            value: v,
            rest: Empty
        }
    }
    // Note how the type-parameters 'shift along'
    fn add<N>(self, v: N) -> TypedLinkedList<N, TypedLinkedList<E, R>>
        where N: MyTrait
    {
        TypedLinkedList {
            value: v,
            rest: self
        }
    }
}

// Create a new trait to hold the accumulate function
trait MyFunc {
    type Output;
    fn accumulate(&self, x: Self::Output) -> Self::Output;
}

// Implement for all 'MyTrait', constraining the Output to f64
impl<T: MyTrait> MyFunc for T {
    type Output = f64;
    fn accumulate(&self, x: f64) -> f64 {
        x + self.numberify()
    }
}

// Traverse trait now has a type parameter
trait Traverse<T>: {
    fn traverse(self, acc: T) -> T;
}

// Still does nothing
impl<T> Traverse<T> for Empty {
    fn traverse(self, acc: T)-> T {
        acc
    }
}

// The traverse function now uses the 'accumulate' method on 'MyTrait'
impl<E: MyTrait, R> Traverse<<E as MyFunc>::Output> for TypedLinkedList<E, R>
    where E: MyTrait, R: Traverse<<E as MyFunc>::Output>
{
    fn traverse(self, acc: <E as MyFunc>::Output) -> <E as MyFunc>::Output {
        let acc = self.value.accumulate(acc);
        self.rest.traverse(acc)
    }
}


trait MyTrait : Display { fn numberify(&self) -> f64; }
impl MyTrait for i32 { fn numberify(&self) -> f64 { *self as f64 } }
impl MyTrait for f64 { fn numberify(&self) -> f64 { *self } }
impl MyTrait for &'static str { fn numberify(&self) -> f64 { self.len() as f64 } }

fn main() {
    let list = TypedLinkedList::<_, Empty>::new(1i32)
        .add(2.0)
        .add("hello")
        .add(100)     // Just add as many lines as you like...
        .add(3.141592)  
        .add("just keep going")
        .add(10000);  
    let x = list.traverse(0f64);
    println!("Numberified: {}", x);
}