如何在 Rust 中实现一个通用的链表映射函数？

Question

我正在用 Rust 咬牙切齿，我正在尝试实现一个通用类型的链表。到目前为止，我的cons和len函数都可以工作，但是map我无法弄清楚有什么问题。

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

错误

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[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]`

我的特殊问题是

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

如果我注释掉该行，则输出的前两行是正确的。我不确定我的map电话有什么问题

---

更新

aochagavia 帮助我理解了函数引用问题和第一个所有权问题（显然是许多问题！） - 我在使用我们使用的相同技术时遇到了问题len，map并出现了新错误

我更新的map功能看起来像这样

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

我现在正在尝试这个

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

新的错误是这个

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

Answer 1

错误消息很大，因为它发生在宏内，但如果添加此消息：let y = map(f, xs);您会得到更短（并且稍微更准确）的错误消息：

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]`

也就是说，您是按值而不是按引用传递闭包！使用map(&f, xs)（注意＆符号）应该可以解决该错误。然而，所有权还存在另一个问题（见下文）。

所有权问题

该len函数的类型签名是fn len<A> (xs: List<A>) -> i32。这意味着它将获得列表的所有权以便计算其长度。然而，这不是您想要的，因为它会阻止您之后使用该列表！因此，您会从编译器中得到错误。

解决这个问题的明智方法是借钱len而xs不是消费。像这样：

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

最后，您需要通过如下调用来修改函数main以反映此更改：（注意＆符号，您可以将其视为借用运算符）。lenlen(&xs)

制作地图也借xs

正如 naomik 在评论中指出的那样，map似乎也是借用而不是xs消费的候选者。一个可能的实现是：

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

与原始版本的主要区别在于，闭包现在采用 an&A而不是 an A（请参阅 参考资料Fn(&A) -> B）。这是很自然的，因为不可能消耗借用中包含的值（这意味着借用机制完全被破坏）。

主要你需要map这样调用：

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

请注意，f现在借用其参数而不是使用它，正如 的类型签名所要求的那样map。

闭包的一些额外背景

Rust 中的闭包有点特殊。您可以使用良好的语法来构造它们，但最终它们只是碰巧实现Fn,FnMut或FnOnce特征的结构。

如果您想按值传递它们（而不是像在代码中那样通过引用传递），则可以使用以下类型签名使映射函数成为通用函数：

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

这也为您提供了静态调度。如果您想了解更多信息，您可能应该阅读特征对象和静态/动态调度。