如何创建一个函数，可以从迭代器的迭代器中创建笛卡尔积迭代器？（涉及IT技术）

Question

如果我想在Haskell中创建一个列表的笛卡尔积，可以这样做：

product [] = [[]]
product (xs:xss) = concatMap (\k -> map (k:) (product1 xss)) xs

甚至是这个：

或者这个：

sequence xss

我正在尝试实现一个高效的迭代器，以在Rust中执行相同的操作，但我不确定我的尝试有什么问题：

use std::iter::{empty, once};

fn product<T, I, V>(xss: I) -> Box<Iterator<Item = Iterator<Item = T>>>
where
    T: Clone,
    V: IntoIterator<Item = T>,
    I: IntoIterator<Item = V>,
{
    Box::new(xss.into_iter().fold(once(empty()), |acc, xs| {
        xs.into_iter().flat_map(|x| acc.map(|ys| ys.chain(once(x))))
    }))
}

fn main() {
    let data = vec![[1, 2, 3], [10, 20, 30], [100, 200, 300]];
    let it: Vec<Vec<u32>> = product(data).collect();
    println!("{:?}", it);
}

(playground)

产生以下错误：

这些错误是：

error[E0308]: mismatched types
  --> src/main.rs:10:9
   |
10 |         xs.into_iter().flat_map(|x| acc.map(|ys| ys.chain(once(x))))
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::iter::Once`, found struct `std::iter::FlatMap`
   |
   = note: expected type `std::iter::Once<std::iter::Empty<T>>`
              found type `std::iter::FlatMap<<V as std::iter::IntoIterator>::IntoIter, std::iter::Map<std::iter::Once<std::iter::Empty<T>>, [closure@src/main.rs:10:45: 10:67 x:_]>, [closure@src/main.rs:10:33: 10:68 acc:_]>`

error[E0271]: type mismatch resolving `<std::iter::Once<std::iter::Empty<T>> as std::iter::Iterator>::Item == std::iter::Iterator<Item=T>`
  --> src/main.rs:9:5
   |
9  | /     Box::new(xss.into_iter().fold(once(empty()), |acc, xs| {
10 | |         xs.into_iter().flat_map(|x| acc.map(|ys| ys.chain(once(x))))
11 | |     }))
   | |_______^ expected struct `std::iter::Empty`, found trait std::iter::Iterator
   |
   = note: expected type `std::iter::Empty<T>`
              found type `std::iter::Iterator<Item=T>`
   = note: required for the cast to the object type `std::iter::Iterator<Item=std::iter::Iterator<Item=T>>`

error[E0277]: the trait bound `[{integer}; 3]: std::iter::Iterator` is not satisfied
  --> src/main.rs:16:29
   |
16 |     let it: Vec<Vec<u32>> = product(data).collect();
   |                             ^^^^^^^ `[{integer}; 3]` is not an iterator; maybe try calling `.iter()` or a similar method
   |
   = help: the trait `std::iter::Iterator` is not implemented for `[{integer}; 3]`
   = note: required because of the requirements on the impl of `std::iter::IntoIterator` for `[{integer}; 3]`
   = note: required by `product`

error: the `collect` method cannot be invoked on a trait object
  --> src/main.rs:16:43
   |
16 |     let it: Vec<Vec<u32>> = product(data).collect();
   |                                           ^^^^^^^

第一个错误让我感觉Rust甚至不能使用fold创建一个惰性消耗的迭代器，因为Empty<T>是一个Iterator<Item = T>（至少在概念上是这样），但我希望我是错的。

- user1685095

---

盒式迭代器并不能替代惰性求值的 Haskell 变量，因为它无法被倒回或克隆，因此这种直接翻译是行不通的。将列表表示为一系列盒式“链”也不是很高效。 - red75prime

你现在用 Rust 写代码，但是思考方式却像 Haskell，这样做可能会出现问题。看一下这个链接里的内容，它展示了 Rust 的一个实现方式：http://killercup.github.io/vibrant-rs/itertools/struct.Product.html - papagaga

@user1685095，你需要实现函数式语言在底层隐藏的所有机制。我尝试了一下。 - red75prime

代码不够快。这可以预料到，因为它只是一个功能程序的简单翻译。 - red75prime

我在 Reddit 上发布了这个问题的链接，并获得了非常有趣的回答：https://www.reddit.com/r/rust/comments/bdlna5/is_there_a_good_rust_translation_of_these_2_lines/ - lovasoa

Answer 1

你的方法注定会失败的第一个原因是，你试图将一个设计用于列表的算法转换为适用于迭代器的算法。列表适合于函数式方法，而迭代器不适合，因为它们具有状态。 next(&mut self) 函数每次使用相同的参数调用时都不会返回相同的值，而 next(x:xs) 函数会返回相同的值。这就是 在itertools中找到的实现 克隆迭代器的原因：为了保存它们的初始状态并在下一次迭代集合时恢复它们。

第二个原因，也是错误消息背后的原因，是你正在与 Rust 的类型系统作斗争。所有对迭代器函数（fold、flat_map 等）的调用的结果值都不是特征对象，而是“具体类型”。例如，iterator.fold(init, fn) 的结果类型是 init 的类型。这就是为什么当你向 fold 传递一个不返回 std::iter::Empty<T> 的 lambda 时，编译器会抱怨的原因。

但情况变得更糟。你可以想象将那个 std::iter::Empty<T> 强制转换为 trait 对象。可惜，需要满足对象安全性。简言之，"一个很好的直觉是“除非在特殊情况下，如果您的 trait 方法使用 Self，则它不是对象安全的”。 但迭代器的主要方法是 next(&mut self)。

- papagaga

---

这里不涉及对象安全性 - 从iter :: empty创建特质对象是可以的。那个“直觉”指的是除了self之外的参数。 - Shepmaster

“你试图将一个设计用于列表的算法转换为适用于迭代器的算法”：这并不完全正确... Haskell 列表更接近于可克隆的迭代器，而不是 Rust 中的 Vec。此处呈现的算法仅依赖于从迭代器中获取下一个元素并对其进行克隆。使这个两行 Haskell 程序在 Rust 中难以实现的是 Haskell 的惰性特性。 - lovasoa

Answer 2

就算价值不高，Itertools板条箱实现了一个可行的笛卡尔积函数：

use itertools::Itertools;

let it = (0..2).cartesian_product("αβ".chars());
itertools::assert_equal(it, vec![(0, 'α'), (0, 'β'), (1, 'α'), (1, 'β')]);

- Andrew Bowers

---

这仅适用于2个迭代器，而不是任意数量的迭代器。 - Solomon Ucko