How to implement a generic linked list map function in Rust?

Question

I am cutting my teeth with Rust and I'm trying to implement a generically-typed linked list. So far my cons and len functions work but there is something wrong with map that I cannot figure out.

use std::fmt;

#[derive(Debug)]
enum List<A> {
    Empty,
    Cons(A, Box<List<A>>),
}

fn cons<A>(x: A, xs: List<A>) -> List<A> {
    return List::Cons(x, Box::new(xs));
}

fn len<A>(xs: List<A>) -> i32 {
    match xs {
        List::Empty => 0,
        List::Cons(_, xs) => 1 + len(*xs),
    }
}

fn map<A, B>(f: &Fn(A) -> B, xs: List<A>) -> List<B> {
    match xs {
        List::Empty => List::Empty,
        List::Cons(x, xs) => cons(f(x), map(f, *xs)),
    }
}

fn main() {
    let xs = cons(1, cons(2, cons(3, List::Empty)));
    println!("{:?}", xs);
    println!("{:?}", len(xs));
    let f = |x: i32| x * x;
    println!("{:?})", map(f, xs));
}

Error

error[E0308]: mismatched types
  --> src/main.rs:32:27
   |
32 |     println!("{:?})", map(f, xs));
   |                           ^ expected reference, found closure
   |
   = note: expected type `&std::ops::Fn(_) -> _`
              found type `[closure@src/main.rs:31:13: 31:27]`

Expected Output

Cons(1, Cons(2, Cons(3, Empty)))
3
Cons(1, Cons(4, Cons(9, Empty)))

My particular problem is with

println!("{:?})", map(f, xs));

If I comment that line out, the first two lines of output are correct. I'm not sure what's wrong with my map call

---

Update

aochagavia helped me understand the function reference issue and the first ownership issue (of many, apparently!) - I'm having trouble using the same technique we used in len in map and getting a new error

My updated map function looks like this

fn map<A, B>(f: &Fn(A) -> B, xs: &List<A>) -> List<B> {
    match *xs {
        List::Empty => List::Empty,
        List::Cons(x, ref xs) => cons(f(x), map(f, xs)),
    }
}

I'm now trying this

let f = |x: i32| x * x;
let ys = map(&f, &xs);
let zs = map(&f, &xs);
println!("{:?})", ys);
println!("{:?})", zs);

The new error is this

error[E0009]: cannot bind by-move and by-ref in the same pattern
  --> src/main.rs:23:20
   |
23 |         List::Cons(x, ref xs) => cons(f(x), map(f, xs)),
   |                    ^  ------ both by-ref and by-move used
   |                    |
   |                    by-move pattern here

Answer 1

The error message is big because it happens within a macro, but if you add this: let y = map(f, xs); you get a shorter (and slightly more accurate) one:

error[E0308]: mismatched types
  --> <anon>:32:15
   |
32 |   let y = map(f, xs);
   |               ^ expected reference, found closure
   |
   = note: expected type `&std::ops::Fn(_) -> _`
              found type `[closure@<anon>:31:11: 31:25]`

That is, you are passing the closure by value instead of by reference! Using map(&f, xs) (note the ampersand) should solve the error. However, there is another issue with ownership (see below).

The ownership issue

The type signature of the len function is fn len<A> (xs: List<A>) -> i32. That means that it will take ownership of the list in order to calculate its length. This is however not what you want, since it would prevent you from using the list afterwards! Hence the error you get from the compiler.

The sensible way to solve this is to let len borrow xs instead of consuming it. Like this:

fn len<A>(xs: &List<A>) -> i32 {
    match *xs {
        List::Empty => 0,
        List::Cons(_, ref xs) => 1 + len(xs),
    }
}

Finally, you will need to modify your main function to reflect this change by calling len like this: len(&xs) (note the ampersand, which you can think of as the borrow operator).

Making map borrow xs as well

As naomik pointed out in the comments, map seems to be a candidate as well for borrowing xs instead of consuming it. A possible implementation would be:

fn map<A, B>(f: &Fn(&A) -> B, xs: &List<A>) -> List<B> {
    match *xs {
        List::Empty => List::Empty,
        List::Cons(ref x, ref xs) => cons(f(x), map(f, xs)),
    }
}

The main difference with the original version is that the closure now takes an &A instead of an A (see Fn(&A) -> B). This is natural, since it is impossible to consume a value that is contained in a borrow (it would mean the borrow mechanism is utterly broken).

In main you would need to call map like this:

let f = |x: &i32| (*x) * (*x);
map(&f, &xs);

Note that f now borrows its parameter instead of consuming it, as is required by the type signature of map.

Some extra background in closures

Closures are a bit special in Rust. You can construct them with a nice syntax, but in the end they are just structs that happen to implement the Fn, FnMut or FnOnce traits.

In case you want to pass them by value (and not by reference, as you do in your code), you can make the map function generic by using the following type signature:

fn map<F, A, B> (f: F, xs: List<A>) -> List<B>
    where F: Fn(A) -> B
{

This also gives you static dispatch. If you want to know more about that you should probably read on trait objects and static/dynamic dispatch.