如何用Rust编写合适的map函数？

Question

使用以下链接列表定义:

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

我正在尝试编写一个map函数(即将操作应用于列表的每个元素并返回一个新列表).我正在尝试使用教程中提供的指南和其他不同的地方(例如Rust for Rubyists),所以我试图在可能的情况下使用值和借用指针而不是拥有指针.这引出了以下函数定义:

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

我认为这是有道理的; 变换器函数对值起作用,list参数是借用的指针.我返回一个拥有的指针,因为我需要使用递归调用的返回值来构造一个值.

现在,让我们来看看身体:

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))
    }
}

这是我的第一次尝试; 该~ref语法是有点不直观,但我发现它的教程.此实现不编译.

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

好吧,显然在进行模式匹配时,内部模式必须具有相同的移动语义,没有混合和匹配.让我们尝试ref在x模式之前添加:

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

再次出错; 模式匹配是可以的,但是我没有正确的类型来调用我的闭包.使用语法f(*x)是非法的,所以我需要更改我的闭包类型以接受借用的指针:

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))
    }
}

最后这个版本有效.

任何人都可以告诉我,这是什么地图应该在Rust看起来像？

Answer 1

这是一张可以接受的地图,但我有一些评论.

首先,只是从map()你知道f需要采取的类型签名&T1而不是T1.这是因为获取T1意味着它必须将值移动到闭包中,但它是在借用的情况下运行List<T1>,因此无法移动它.

其次,你的地图不需要返回~List<T2>,它可以只返回List<T2>,你可以~自己将递归调用包装在指针中.这看起来像

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))
    }
}

第三,实现这一目标的最好方法是不写map(),而是写iter(),这会产生一种实现的类型Iterator<&T1>.迭代器隐式支持map.然后你还需要实现FromIterator允许你将映射的结果转换回来List.

这是迭代器和示例用法的实现:

#[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)))
}