How to write a proper map function with Rust?

Question

Using the following linked list definition:

enum List<T> {
    Nil,
    Cons(T, ~List<T>)
}

I am trying to write a map function (i.e. applying an operation to every element of the list and returning a new list). I am trying to use the guidelines given in the tutorial and diverse other places (e.g. Rust for Rubyists), so I am trying to use values and borrowed pointers instead of owned pointers when possible. This leads me to the following function definition:

fn map<T1, T2>(f: |T1| -> T2, xs: &List<T1>) -> ~List<T2> { ... }

I think this makes sense; the transformer function works on values and the list parameter is a borrowed pointer. I return a owned pointer because I'll need to cons a value with the return value of a recursive call.

Now, let's look at the body:

fn map<T1, T2>(f: |T1| -> T2, xs: &List<T1>) -> ~List<T2> {
    match xs {
        &Nil => ~Nil,
        &Cons(x, ~ref rest) => ~Cons(f(x), map(f, rest))
    }
}

This was my first try; the ~ref syntax is a bit unintuitive, but I found it in the tutorial. This implementation doesn't compile.

demo.rs:25:15: 25:16 error: cannot bind by-move and by-ref in the same pattern
demo.rs:25         &Cons(x, ~ref rest) => ~Cons(f(x), map(f, rest))
                         ^
demo.rs:25:19: 25:27 note: by-ref binding occurs here
demo.rs:25         &Cons(x, ~ref rest) => ~Cons(f(x), map(f, rest))
                             ^~~~~~~~
error: aborting due to previous error

All right, so apparently when doing pattern matching, the inner patterns must have the same move semantics, no mix and matching. Let's try to add ref before the x pattern:

fn map<T1, T2>(f: |T1| -> T2, xs: &List<T1>) -> ~List<T2> {
    match xs {
        &Nil => ~Nil,
        &Cons(ref x, ~ref rest) => ~Cons(f(x), map(f, rest))
    }
}

demo.rs:25:44: 25:45 error: mismatched types: expected `T1` but found `&T1` (expected type parameter but found &-ptr)
demo.rs:25         &Cons(ref x, ~ref rest) => ~Cons(f(x), map(f, rest))
                                                      ^
error: aborting due to previous error

Error again; the pattern matching is okay, however I don't have the correct type to call my closure. Using the syntax f(*x) is illegal, so I need to change my closure type to take in a borrowed pointer:

fn map<T1, T2>(f: |&T1| -> T2, xs: &List<T1>) -> ~List<T2> {
    match xs {
        &Nil => ~Nil,
        &Cons(ref x, ~ref rest) => ~Cons(f(x), map(f, rest))
    }
}

And finally this version works.

Can anyone tell me if that's what map should look like in Rust?

Answer 1

That's an acceptable map, but I have a few comments.

First, just from the type signature of map() you know that f needs to take &T1 and not T1. This is because taking T1 means it has to move the value into the closure, but it's operating on a borrowed List<T1> and therefore can't move it.

Second, your map doesn't need to return ~List<T2>, it could just return List<T2>, and you could just wrap the recursive call in the ~ pointer yourself. This would look like

fn map<T,U>(f: |&T| -> U, xs: &List<T>) -> List<U> {
    match *xs {
        Nil => Nil,
        Cons(ref x, ~ref rest) => Cons(f(x), ~map(f, rest))
    }
}

Third, the best way to accomplish this isn't to write map() at all, but instead to write iter(), which yields a type that implements Iterator<&T1>. Iterators implicitly support map. Then you would also need to implement FromIterator to allow you to convert the results of the mapping back into a List.

---

Here's an implementation of an iterator and sample usage:

#[deriving(Show)]
pub enum List<T> {
    Nil,
    Cons(T, ~List<T>)
}

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Items<'a, T> {
        Items { list: self }
    }
}

pub struct Items<'a, T> {
    list: &'a List<T>
}

impl<'a, T> Iterator<&'a T> for Items<'a, T> {
    fn next(&mut self) -> Option<&'a T> {
        match *self.list {
            Nil => None,
            Cons(ref x, ~ref rest) => {
                self.list = rest;
                Some(x)
            }
        }
    }
}

impl<A> FromIterator<A> for List<A> {
    fn from_iter<T: Iterator<A>>(mut iterator: T) -> List<A> {
        match iterator.next() {
            None => Nil,
            Some(x) => Cons(x, ~FromIterator::from_iter(iterator))
        }
    }
}

fn main() {
    let x = Cons(1u, ~Cons(2u, ~Cons(3u, ~Nil)));
    println!("{}", x);
    // prints Cons(1, Cons(2, Cons(3, Nil)))
    let y: List<uint> = x.iter().map(|&x| x*2).collect();
    println!("{}", y);
    // prints Cons(2, Cons(4, Cons(6, Nil)))
}