Wie erstellt man eine Funktion, die einen kartesischen Produkt-Iterator von einem Iterator von Iteratoren erzeugt?

Question

Wenn ich ein kartesisches Produkt aus einer Liste von Listen in Haskell erstellen möchten, kann ich dies tun:

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

oder sogar unter:

sequence xss 

Ich versuche, eine effiziente Iterator zu implementieren das würde das gleiche tun in Rust, aber ich bin nicht sicher, was mit meinem Versuch, falsch ist:

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)

Erzeugt diese Fehler:

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

Der erste Fehler mir das Gefühl schenkt, dass Rust kann nicht einmal eine träge verbraucht Iterator mit fold schaffen, weil Empty<T> ein Iterator<Item = T> ist (zumindest vom Konzept her), aber ich hoffe, ich bin falsch.

Answer 1

Der erste Grund dafür, dass Ihr Ansatz scheitern muss, ist, dass Sie versuchen, einen Algorithmus, der für die Bearbeitung von Listen entwickelt wurde, in einen Algorithmus umzusetzen, der an Iteratoren arbeitet. Listen sind für einen funktionalen Ansatz geeignet, Iteratoren nicht, weil sie einen Zustand haben. Die Funktion next(&mut self) gibt nicht jedes Mal denselben Wert zurück, wenn sie mit demselben Argument aufgerufen wird, während eine next(x:xs)-Funktion dies tut. Dies ist der Grund, warum die implementation found in itertools Iteratoren klont: ihren Ausgangszustand zu speichern und ihn für die nächste Iteration über den Satz wiederherzustellen.

Der zweite Grund, der hinter den Fehlermeldungen, ist, dass Sie gegen Rust's Typsystem kämpfen. Die Ergebniswerte aller Aufrufe von Iteratorfunktionen (fold, flat_map usw.) sind keine Merkmalsobjekte, sondern 'konkrete Typen'. Zum Beispiel iterator.fold(init, fn) ist der Ergebnistyp init 's Typ. Deshalb beschwert sich der Compiler, wenn Sie fold ein Lambda übergeben, das keine std::iter::Empty<T> zurückgibt.

Aber es wird schlimmer. Du könntest dir vorstellen, das std::iter::Empty<T> in ein Merkmalsobjekt zu zwingen oder zu werfen. Leider ist Objektsicherheit erforderlich. Um es auf den Punkt zu bringen, "A good intuition is “except in special circumstances, if your trait’s method uses Self, it is not object-safe.". Die Hauptmethode der Iteratoren ist jedoch next(&mut self).