Rust example List

Question

I have a class like:

#[derive(Clone,PartialEq,Debug)]
pub enum List<T> {
    Nil,
    Cons(T,Box<List<T>>)
}

Now suppose the Lists are created like the following:

let x = 
            List::Cons(0,
                Box::new(List::Cons(1,
                Box::new(List::Cons(2,
                Box::new(List::Cons(3,
                Box::new(List::Nil))))))));

Now I want to create a map function that applies f to each element in the List type but I have a problem because I do not know how to traverse through this data type.

pub fn map<T,U,F:Fn(&T)->U>(f:F,l:& List<T>) -> List<U> {
    let mut myList = List::Nil;
    if let List::Nil = l {
        return List::Nil;
    } 
    //Want to apply F to each element of l and than 
    // append it to myList but do not know how.
    return myList;
}

So something like:

let x = 
            List::Cons(0,
                Box::new(List::Cons(1,
                Box::new(List::Cons(2,
                Box::new(List::Cons(3,
                Box::new(List::Nil))))))));
map(|val| val+1,&x)

Should result in

List::Cons(1,
                Box::new(List::Cons(2,
                Box::new(List::Cons(3,
                Box::new(List::Cons(4,
                Box::new(List::Nil))))))));

Can someone help me solve this?

Answer 1

You can use this iterative approach:

#[derive(Clone,PartialEq,Debug)]
pub enum List<T: Clone + PartialEq + std::fmt::Debug> {
    Nil,
    Cons(T,Box<List<T>>)
}

pub fn map<T,U,F:Fn(&T)->U>(f:F,mut l:&List<T>) -> List<U>
where
    T: Clone + PartialEq + std::fmt::Debug,
    U: Clone + PartialEq + std::fmt::Debug,
{
    let mut my_list = List::Nil;
    let mut current = &mut my_list;
    while let List::Cons(ref v, ref next) = l {
        *current = List::Cons(f(v), Box::new(List::Nil));
        current = match current {
            List::Cons(_, ref mut next) => next,
            _ => unreachable!(),
        };
        l = next;
    }
     my_list
}

---

Or go with this totaly overengineered approach using the traits Iterator and FromIterator

pub struct Iter<'a, T>
where
    T: Clone + PartialEq + std::fmt::Debug + 'a,
{
    list: &'a List<T>,
}

impl<'a, T> Iterator for Iter<'a, T>
where
    T: Clone + PartialEq + std::fmt::Debug + 'a,
{
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> {
        match self.list {
            List::Nil => None,
            List::Cons(ref v, ref rest) => {
                self.list = rest;
                Some(v)
            }
        }
    }
}

impl<T> List<T>
where
    T: Clone + PartialEq + std::fmt::Debug,
{
    pub fn iter(&self) -> Iter<'_, T> {
        Iter{ list: self }
    }
}

impl<A> FromIterator<A> for List<A>
where
    A: Clone + PartialEq + std::fmt::Debug,
{
    fn from_iter<T>(vals: T) -> List<A>
    where
        T: IntoIterator<Item = A>,
    {
        let mut head = List::Nil;
        let mut current = &mut head;
        for v in vals {
            *current = List::Cons(v, Box::new(List::Nil));
            current = match current {
                List::Cons(_, ref mut next) => next,
                _ => unreachable!(),
            };
        }
        head
    }
}

pub fn map<T,U,F:Fn(&T)->U>(f:F,mut l:&List<T>) -> List<U>
where
    T: Clone + PartialEq + std::fmt::Debug,
    U: Clone + PartialEq + std::fmt::Debug,
{
    l.iter().map(f).collect()
}

Yes I had way too much fun implementing this.

Answer 2

If you have a recursive struct, by far the easier way to work with it is by using recursive functions. They may be slow and you risk a stack overflow, but they are easy to write:

pub fn map<T, U, F: Fn(&T) -> U>(f: F, l: &List<T>) -> List<U> {
    match l {
        List::Nil => List::Nil,
        List::Cons(h, s) => List::Cons(f(h), Box::new(map(f, s)))
    }
}

It probably can be done using a loop, but I don't think it is worth the effort.