反復子の反復子からデカルト積を生成する関数を作成するにはどうすればよいですか？私はHaskellではリストのリストの直積を作成したい場合は

Question

、私はこれを行うことができます。

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

かさえ、この：

sequence xss 

を私は、効率的なイテレータを実装しようとしていますそれは錆で同じことを行うだろうが、私は私の試みと間違っているかわからないんだけど：

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(); 
    |           ^^^^^^^ 

最初のエラーは、（少なくとも概念的には）私にEmpty<T>がIterator<Item = T>ですので錆にもfoldとなまけ消費イテレータを作成することができないという感じを与えているが、私は、私は願っています違う。

Answer 1

リストに作用するように設計されたアルゴリズムをイテレータで動作するアルゴリズムに転置しようとしているため、アプローチが失敗する最初の理由があります。リストは機能的なアプローチに適しています。イテレータは状態を持っているため、そうではありません。 next(&mut self)関数は、同じ引数で呼び出されるたびに同じ値を返しませんが、next(x:xs)関数は呼び出します。このため、クローンのイテレータが初期状態を保存して、そのセットの次の反復のために回復するという理由があります。

エラーメッセージの背後にある2つ目の理由は、あなたがRustのタイプシステムと戦っているということです。イテレータ関数（fold、flat_mapなど）に対するすべての呼び出しの結果値は、特性オブジェクトではなく「具体的な型」です。例えばiterator.fold(init, fn)の結果のタイプはinitのタイプです。そのため、foldにstd::iter::Empty<T>を返さないラムダを渡すとコンパイラが不平を言うのです。

しかし、それは悪化します。 std::iter::Empty<T>を特質オブジェクトに強制するか、キャストすることが想像できます。ああ、オブジェクトの安全が必要です。一言で言えば、"A good intuition is “except in special circumstances, if your trait’s method uses Self, it is not object-safe."です。しかしイテレータの主な方法はnext(&mut self)です。