반복자의 반복자로부터 카티 전 곱을 생성하는 함수를 만드는 방법은 무엇입니까? 나는 하스켈에서리스트의리스트의 직교 제품을 만들려면

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) 함수는 반환합니다. 이것이 implementation found in itertools 반복자 반복자 인 이유입니다. 초기 상태를 저장하고 세트를 통해 다음 반복을 위해 복구합니다.

오류 메시지 뒤에있는 두 번째 이유는 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.". 그러나 iterators의 주요 방법은 next(&mut self)입니다.