pointers - 如何用 Rust 编写一个合适的 map 函数？

Question

使用下面的链表定义:

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

我正在尝试编写一个映射函数(即对列表的每个元素应用一个操作并返回一个新列表)。我正在尝试使用本教程和其他地方(例如 Rubyist 的 Rust)中给出的指南，因此我正在尝试尽可能使用值和借用的指针而不是拥有的指针。这使我得出以下函数定义:

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

我认为这是有道理的；转换器函数作用于值，列表参数是借用的指针。我返回一个拥有的指针，因为我需要使用递归调用的返回值来构造一个值。

现在，让我们看看正文:

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

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

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

这个版本终于可以用了。

谁能告诉我 map 在 Rust 中是否应该是这样的？

Answer 1

这是一张可以接受的 map ，但我有几点意见。

首先，仅来自 map() 的类型签名你知道f需要服用&T1而不是 T1 .这是因为取 T1意味着它必须将值移动到闭包中，但它是在借来的 List<T1> 上运行的因此无法移动它。

其次，您的 map 不需要返回 ~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> 的类型.迭代器隐式支持映射。然后你还需要实现 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)))
}