Crust of Rust: Iterators

直播錄影

• 主機資訊
  ​​​​wilson@wilson-HP-Pavilion-Plus-Laptop-14-eh0xxx ~> neofetch --stdout
  ​​​​wilson@wilson-HP-Pavilion-Plus-Laptop-14-eh0xxx 
  ​​​​----------------------------------------------- 
  ​​​​OS: Ubuntu 22.04.3 LTS x86_64 
  ​​​​Host: HP Pavilion Plus Laptop 14-eh0xxx 
  ​​​​Kernel: 6.2.0-39-generic 
  ​​​​Uptime: 1 min 
  ​​​​Packages: 2373 (dpkg), 13 (snap) 
  ​​​​Shell: bash 5.1.16 
  ​​​​Resolution: 3840x2160 
  ​​​​DE: GNOME 42.9 
  ​​​​WM: Mutter 
  ​​​​WM Theme: Adwaita 
  ​​​​Theme: Yaru-dark [GTK2/3] 
  ​​​​Icons: Yaru [GTK2/3] 
  ​​​​Terminal: gnome-terminal 
  ​​​​CPU: 12th Gen Intel i5-12500H (16) @ 4.500GHz 
  ​​​​GPU: Intel Alder Lake-P 
  ​​​​Memory: 2768MiB / 15695MiB
  

• Rust 編譯器版本 ：
  ​​​​wilson@wilson-HP-Pavilion-Plus-Laptop-14-eh0xxx ~/CrustOfRust> rustc --version
  ​​​​rustc 1.70.0 (90c541806 2023-05-31) (built from a source tarball)
  

Introduction

0:00:00

In this third Crust of Rust video, we cover iterators and trait bounds, by re-implementing the "flatten" Iterator method from the standard library. As part of that, we cover some of the weirder trait bounds that are required, including what's needed to extend the implementation to support backwards iteration.

The Iterator trait

0:01:45

Trait std::iter::Iterator

Iterator 在 Rust 是 trait，這個 trait 有兩個主要的東西你必須關注 :

1. associated type Item : 由迭代器產生的 item。
2. next() : 由驅動迭代器的事物呼叫。它會產生 Some(Item) 直到迭代器被耗盡，也就是產生 None 時，迭代器就會終止。

以下為 Iterator 函式庫部分程式碼 :

pub trait Iterator {
    type Item;

    // Required method
    fn next(&mut self) -> Option<Self::Item>;
    ...

開始建置 Rust 專案 :

$ cargo new --lib iterators
$ cd iterators
$ vim src/lib.rs

當你寫了以下的程式碼 :

fn main() 
{
    for x in vec!["a", "b", "c"] {
    }
}

在 Rust 本質上並沒有真正的 for 迴圈，它是個語法糖。Desugaring 前面我們寫的程式之後，實際上它會轉換成以下程式碼 :

fn main() 
{
    let iter = vec!["a", "b", "c"].into_iter();
    while let Some(e) = iter.next() {
        
    }
}

into_iter() 給了我們一個迭代器，無論原本那個東西是什麼，假設那個東西可以被迭代。這時候 for 迴圈就可以改用 while let 迴圈取代，while let 迴圈持續呼叫 next() 函式回傳 Some(xxx)，直到回傳 None 時，迭代器就會停下來。但語法糖轉換後並不完全是這樣，而是演變成一個帶有 break 的迴圈，這裡只是要提供背後到底發生了什麼事情。

The IntoIterator trait

0:04:25

Trait std::iter::IntoIterator

IntoIterator 是獨立的 trait，並不是包在 Iterator trait，但它有點像 Iterator 的 wrapper trait，它可以將任何東西變成迭代器。任何迭代器很明顯地可以變成迭代器，但其他東西也可以變成迭代器，像是 HashMap、HashSet …等等，它們實作的 slices、slices references to slices、mutable references to HashMap，如果你可以擁有他們實作的其中一個東西，你可以得到一個迭代器來迭代它們的一些相關部分，看到下面的例子 :

impl<'a, K, V, S> IntoIterator for &'a mut HashMap<K, V, S>
    type Item = (&'a K, &'a mut V)
    type IntoIter = IterMut<'a, K, V>

只要你每次迭代 mut HashMap，都會拿到包含 immutable 的 key 以及 mutable 的 value 的 tuple 結構，這些東西的可變性設定很有道理，因為當你在迭代的時候你不能去改變 key，因為 key 如果中途改變很有可能就移到其他的位置，但你可以改變 value。IntoIterator 還有 associated type IntoIter，它將會回傳迭代器的型別 : IterMut，它是 HashMap 的子模組，我們這邊不做探討。

Generic traits vs associated types

0:06:24

為什麼 Iterator 會有 associated types Item ? 以下兩個都可以運作，但差別在哪裡 ?

• Associated types
  ​​​​trait Iterator 
  ​​​​{
  ​​​​    type Item;
  ​​​​    fn next(&mut self) -> Option<Self::Item>;
  ​​​​}
  

• Generic traits
  ​​​​trait Iterator<Item> 
  ​​​​{
  ​​​​    fn next(&mut self) -> Option<Item>;
  ​​​​}
  

當你使用 Associated types 的時候，你預期這個 trait 只會實作一個給定的型別。舉例來說 :

1. 當你有一個 hash map，它只會有一個 Iterator 型別 : keys 和 values
2. 當你有一個 vector，它只會有一個 Iterator 型別 : 某種儲存在 vector 內的型別。

如果多個實作對於任何給定類型都有意義的話，則可以用 Generic traits 。例如 :

trait Service<Request>
{
    fn do(&mut self, r: Request);
}

因為你想要伺服器能夠支援多種不同型別，這時候用 Generic traits 就相當的合理，倘若這裡用 Associated types，反而被限制只能支援一種型別。這樣感覺用 Generic traits 對程式設計師很方便，但是如果使用 Associated types 的好處是，型別檢查器的工作會比較簡單，因為它知道現在只有一種型別被選擇，而且當你在編寫 impl blocks 的時候，函式簽章不需要有額外的泛型參數。
如果程式寫的例子是 SomethingIterable，這時候我們會立刻知道你指的是哪一個實作的 Iterator，因為只有一個；但如果是 SomethingService 的話，你必須告訴編譯器你想要哪個 Request 型別的服務。

:warning:
0:10:05
Q : Why do some types have "iter()" (e.g. slice) and others use "into_iter()"?
A : Jon 認為沒有充分的理由用有 iter() 方法 :

fn main()
{
    ["a", "b"].iter() // 給我們 slice 的元素的迭代器
}

實際上，slice 是有實作 into_iter() 方法，不過實際上沒有必要。您不需要完全符合 IntoIterator trait 要求的方法簽章，這在某些情況下使生命週期推理變得更容易。

Q : Couldn't hashmap also have seperate iterators for just keys or just values?
A : 它可以，而且它也有，一個叫做 .keys()，一個叫做 .values()。不過 hash map 本身沒有實作 Iterator，而是實作 IntoIterator。當你跟 hash map 說給我一個迭代器，你只會得到一種答案，因為它並沒有接收任何其它的參數。

Q : So, if using a for loop we don't need to explicitly call my_collection.iter() or are there exceptions?
A : 沒錯。不過要記住下面兩個 for 迴圈有很大的差別 :

fn main()
{
    let vs = vec![1, 2, 3];
    for v in vs {
        // consumes vs, owned v
        // 為什麼 vs 被設計成會 consume 值，因為在 Rust 'explict' 是件好事。
        // 如果你想要 reference，就要告訴編譯器說你要用 reference。
    }
    
    for v in vs.iter() {
        // borrow vs, & to v
    }
    /* 如果你不想要寫 .iter() 你也可以用以下的方法來達到 borrow 的目的*/
    for v in &vs {
        // equivalent to vs.iter()
    }
}

Provided Iterator methods

0:13:37

標準函式庫只要該函式有 {...} 表示已經有預設的實作了，像是 count() 的話，就是實際走訪所有元素，但你也可以替換它們的實作，例如 ，Vector 就是直接回傳它的 size，而不用實際走訪整個 Vector 來提升效率。

Iterator::flatten

0:14:42

函式簽章如下，它要求 Item 要實作 IntoIterator trait :

fn flatten(self) -> Flatten<Self> ⓘ
   where Self: Sized,
         Self::Item: IntoIterator { ... }

觀察 flatten 方法 :

let data = vec![vec![1, 2, 3, 4], vec![5, 6]];
let flattened = data.into_iter().flatten().collect::<Vec<u8>>();
assert_eq!(flattened, &[1, 2, 3, 4, 5, 6]);

1. 存取外部迭代器的第 n 個元素
2. 呼叫 into_iter() 將外部迭代器的第 n 個元素轉成迭代器
3. 轉完之後接著走訪內部迭代器的全部元素
4. n++
5. 如果走訪完外部迭代器的元素即終止，否則回到步驟 1

Q : does it flatten infinitely?
A : 只要外部迭代器的元素還有，就會一直繼續下去。

Q : Does these nested iterator need to have the same item type?
A : 是的。這本來就是迭代器要求的，外部迭代器的元素之間都會是相同型別，所以內部迭代器之間也自然而然跟著是相同型別。

:bulb: flatten 的遞迴深度只會有一層，而不是你有很多層它就會遞迴到最底層。

開始實作 flatten 功能 :

pub fn flatten<I>(iter: I) -> Flatten<I>
{
    Flatten::new(iter)
}

pub struct Flatten<T>
{
    outer : I,
}

impl<I> Flatten<I> 
{
    fn new(iter: I) -> Self 
    {
        Flatten { outer : iter }
    }
}

Associated items of generics in bounds

0:20:07

繼續實作 flatten 功能, 要將部份的 I 換成 O :

...
pub struct Flatten<O>
{
-   outer : I,
+   outer : O, // O : Outer
}

-impl<I> Flatten<I> 
+impl<O> Flatten<O> 
{
-   fn new(iter: I) -> Self
+   fn new(iter: O) -> Self 
    {
        Flatten { outer : iter }
    }
}

並且為 Flatten 實作 Iterator 原型:

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
    // 關鍵，讓 Rust 知道 Line 12 的 O::Item::Item 是什麼。
    // 原本應該寫成 : 
    //     <O as Iterator>::Item: IntoIterator
    //     不過因為 O 只有一個 trait bound - (Line 3) O: Iterator，
    //     這個 bound 給了我們 O 的 associated type，
    //     所以我們可以直接寫成 O::Item
{
    type Item = <O::Item as IntoIterator>::Item; 
    // 我們實際上不知道 Item 是什麼
    // 我們要 yield 的不是 O 擁有的元素，而是 Item 擁有的元素
    fn next(&mut self) -> Option<Self::Item>
    {
        None
    }
}

Why must O as Trait be bracketed?

0:23:10

Q : Why <O::Item as IntoIterator> required?
A : Jon 不知道為什麼編譯器會認為是引發奇異的錯誤，Jon 猜測這可能是斷詞歧異，因為 AAA::BBB::CCC 可能是路徑 :

:bulb: If a type has multiple associated types by the same name, such as if the trait that provides the associated type is itself generic (and therefore there are many implementations), you can disambiguate with the syntax <Type as Trait>::AssocType. Using this, you can write bounds not only for the outer iterator type but also for the item type of that outer iterator.

1. 歧義性：
   在某些情況下，I::Item::Item 可能會導致歧義。如果 I::Item 實現了多個 trait，而這些 trait 都有一個名為 Item 的關聯類型，Rust 編譯器就無法確定您指的是哪個 Item。
   明確性：
2. <I::Item as Container<i32>>::Item 明確指出我們要使用的是 Container<i32> trait 中定義的 Item 關聯類型。這種寫法消除了任何可能的歧義。

範例程式碼

trait AnotherTrait {
    type Item;
}

impl<T> AnotherTrait for Box<T> {
    type Item = String;
}

fn process_containers<I>(iter: I)
where
    I: Iterator,
    I::Item: Container<i32> + AnotherTrait,
    <I::Item as Container<i32>>::Item: std::fmt::Display,
    // 如果我們使用 I::Item::Item，編譯器將不知道我們指的是哪個 Item
{
    for container in iter {
        println!("Container value: {}", container.get());
    }
}

目前程式碼

pub fn flatten<I>(iter: I) -> Flatten<I>
{
    Flatten::new(iter)
}

pub struct Flatten<O>
{
    outer : O,
}

impl<O> Flatten<O> 
{
    fn new(iter: O) -> Self 
    {
        Flatten { outer : iter }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = O::Item::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        None
    }
}

測試出現以下錯誤 :

$ cargo check
    Checking iterators v0.1.0 (/home/wilson/CrustOfRust/iterators)
error[E0223]: ambiguous associated type
  --> src/lib.rs:24:17
   |
24 |     type Item = O::Item::Item; 
   |                 ^^^^^^^^^^^^^ help: use the fully-qualified path: <<O as Iterator>::Item as IntoIterator>::Item

Flattening more than two levels

0:24:28

可以，再宣告一層即可，大概是這樣：

...
impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
    <O::Item as IntoIterator>::Item: IntoIterator,
{
    type Item = ...; 
    fn next(&mut self) -> Option<Self::Item>
    {
        None
    }
}

要注意到，這樣你要 flatten 的東西必須有三層，兩層現在反而是不能接受的。

First attempt at Flatten::next

0:25:24

回到兩層的實作，接著繼續實作 next()：

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        // self.outer.next() 
        //     看似正確，實際上是錯的，因為現在這個回傳值是 O::Item 的型別
        //     而不是 O::Item::Item。根本原因是，我們根本還沒開始 nest。
        self.outer.next().and_then(|inner| inner.into_iter().next())
    }
}

:bulb: and_then 是用來解決巢狀型式的方法。

再實作兩個 test case :

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
        // assert_eq!(flatten(std::iter::empty::<()>()).count(), 0);
        //     empty 回傳沒有 items 的迭代器。
        //     因為沒有 item 可以讓編譯器推論迭代器的 item 的型別什麼，
        //     所以你要告訴編譯器迭代器的 item 的型別是什麼，
        //     接著嘗試用  <()>，不過因為 `()`，並沒有實作 IntoIterator, 
        //     所以用 `Vec<()>` 來替代。
        
        // 0:33:16 聊天室提供的可行方法，不過很難閱讀
        //     std::iter::empty::<std::iter::empty::<()>>
        
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }
}

:pencil2: std::iter::empty::<Vec<()>>() 解析
std::iter::empty 是 Rust 標準函式庫的函式，其定義如下:

pub const fn empty<T>() -> Empty<T> {
    Empty(marker::PhantomData)
}

所以我們可以知道 <Vec()> 是泛型的參數，而第二個 () 則是呼叫該函式。

:warning: empty 與 <Vec<()>>() 之間的 :: 若省略會出現以下錯誤 :

error: comparison operators cannot be chained
  --> src\lib.rs:38:44
   |
38 |         assert_eq!(flatten(std::iter::empty<Vec<()>>()).count(), 0);
   |                                            ^   ^
   |
help: use `::<...>` instead of `<...>` to specify lifetime, type, or const arguments
   |
38 |         assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);

什麼時候要加 ::，什麼時候不用加 :: ?

1. 當函式需要傳入值，而這個傳入的值有定義是泛型，就不用加 ::
   範例

   ​​​​fn largest<T>(list: &[T]) -> &T {
   ​​​​    let mut largest = &list[0];
   
   ​​​​    for item in list {
   ​​​​        if item > largest {
   ​​​​            largest = item;
   ​​​​        }
   ​​​​    }
   
   ​​​​    largest
   ​​​​}
   
   ​​​​fn main() {
   ​​​​    let number_list = vec![34, 50, 25, 100, 65];
   
   ​​​​    let result = largest(&number_list);
   ​​​​    println!("The largest number is {}", result);
   
   ​​​​    let char_list = vec!['y', 'm', 'a', 'q'];
   
   ​​​​    let result = largest(&char_list);
   ​​​​    println!("The largest char is {}", result);
   ​​​​}
   

2. 當函式沒有傳入值，就要加 :: 來呼叫函式。empty 用法即是這種例子。

Q : Would it be possible to write a macro that accepts n nested levels?
A : 程序式巨集是你的選項。

Q : Alternately, instead of doing this explicitly to one-level-deep, could we not write fn flatten() to all itself recursively?
A : 可以，flat_map 是個好選項。

完整程式碼

pub fn flatten<I>(iter: I) -> Flatten<I>
{
    Flatten::new(iter)
}

pub struct Flatten<O>
{
    outer : O,
}

impl<O> Flatten<O> 
{
    fn new(iter: O) -> Self 
    {
        Flatten { outer : iter }
    }
}
impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        self.outer.next().and_then(|inner| inner.into_iter().next())
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }
}

$ cargo test
...
running 2 tests
test tests::empty ... ok
test tests::one ... ok
...

Two elements in inner iterator

0:29:59

再加一個 test case 並測試 :

#[cfg(test)]
mod tests
{
    use super::*;
    ...
    #[test]
    fn two() // 測試失敗，左邊的結果只得到 1
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }
}

測試失敗，左邊的結果只得到 1。
為了驗證到底哪裡出了問題，再加一個 test case :

Two elements in outer iterator

0:31:05

再加一個 test case 並測試：

#[cfg(test)]
mod tests
{
    use super::*;
    ...
    #[test]
    fn two_wide()
    {
        // 外部的迭代器有兩個元素，內部的迭代器有一個元素
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]].into_iter()).count(), 2);
    }
}

這次測試成功了，表示外部迭代器的走訪應該是沒問題的，問題應該出在內部的迭代器現在只能迭代一次。

為了確認外部迭代器是正確的，再加一個 test case :

#[cfg(test)]
mod tests
{
    use super::*;
    ...
    #[test]
    fn empty_wide() // 測試成功
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]].into_iter()).count(), 0);
    }
}

完整程式碼

pub fn flatten<I>(iter: I) -> Flatten<I>
{
    Flatten::new(iter)
}

pub struct Flatten<O>
{
    outer : O,
}

impl<O> Flatten<O> 
{
    fn new(iter: O) -> Self 
    {
        Flatten { outer : iter }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        self.outer.next().and_then(|inner| inner.into_iter().next())
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn empty_wide()
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]].into_iter()).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }

    #[test]
    fn two() // 測試失敗，左邊的結果只得到 1
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }

    #[test]
    fn two_wide()
    {
        // 外部的迭代器有兩個元素，內部的迭代器有一個元素
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]].into_iter()).count(), 2);
    }
}

測試結果如下:

$ cargo test
...
running 5 tests
test tests::empty ... ok
test tests::one ... ok
test tests::two ... FAILED
test tests::two_wide ... ok
test tests::empty_wide ... ok
...

Simplifying with ?

0:33:29

將程式碼實作的更有可讀性 :

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        let inner_item = self.outer.next()?;
        // inner_item : 由 outer 迭代器產生
        let mut inner_iter = inner_item.into_iter();
        inner_iter.next()
        // 這裡只能還是只能產生一個 inner_item，
        // 我們應該要保存資訊，下次呼叫 flatten 的時候，
        // 才可以繼續從 inner_iter 的第 n 個位置繼續下去。
    }
}

Storing the inner iterator

0:35:05

我們有 struct 可以記錄 inner_iter 的位置 :

pub struct Flatten<O>
where 
    O: Iterator,
{
    outer : O,
    // 寫成 Option 是因為我們可能還沒有 inner 值
    inner : Option<O::Item>,
}

並為 impl block 加上 bound，以及先給 inner 初值 :

impl<O> Flatten<O> 
where 
    O: Iterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            inner : None 
        }
    }
}

flatten 函式也要加上 bound :

pub fn flatten<I>(iter: I) -> Flatten<I>
where 
    I: Iterator,
{
    Flatten::new(iter)
}

我們現在的目標是，如果 inner 迭代器還沒走訪完，我們希望能繼續走訪下去，等到迭代器被耗盡之後，outer 迭代器再接著往下一個元素前進 :

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        // 備註 1.
        if let Some(ref mut inner_iter) = self.inner {
            // Line 18 是錯誤的
            // 備註 2.
            // 不能這樣寫，因為內部迭代器是 IntoIterator，
            // 所以如果你還沒將它轉成迭代器之前是不能呼叫 next。
            // 目前的 inner 是 Vec<Option::Item>，
            // 你不能直接對 Vector 呼叫 next。
            if let Some(i) = inner_iter.next() {
                // inner 迭代器若還沒被耗盡，繼續產生值
                return Some(i);
            }
            self.inner = None;
        }
        
        let inner_item = self.outer.next()?;
        // inner_item : 由 outer 迭代器產生
        let mut inner_iter = inner_item.into_iter();
        inner_iter.next()
    }
}

:pencil2: 備註

1. 說明錯誤原因
   • 合法
     ​​​​​​​​fn main() {
     ​​​​​​​​    let mut a = vec![1,2,3];
     ​​​​​​​​    let mut b = a.iter();
     ​​​​​​​​    b.next();
     ​​​​​​​​}
     

   • 不合法
     ​​​​​​​​fn main() {
     ​​​​​​​​    let mut a = vec![1,2,3];
     ​​​​​​​​    a.next();
     ​​​​​​​​}
     

2. Some(ref mut x) = Option(y) 參照這裡

回到 struct 修好備註 1 的問題 :

pub fn flatten<I>(iter: I) -> Flatten<I>
where 
    I: Iterator,
+   I::Item: IntoIterator,
{
    Flatten::new(iter)
}


pub struct Flatten<O>
where 
    O: Iterator,
+   O::Item: Iterator,
{
    outer : O,
-   inner : Option<O::Item>,
+   inner : Option<<O::Item as IntoIterator>::IntoIter>,
+   // 開始有點不好閱讀，要弄清楚我們要的型態是什麼才能達到我們的目的
+   // IntoIter 是 IntoIterator 的成員
}

目前程式碼

pub fn flatten<I>(iter: I) -> Flatten<I>
where 
    I: Iterator,
    I::Item: IntoIterator,
{
    Flatten::new(iter)
}

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    outer : O,
    inner : Option<<O::Item as IntoIterator>::IntoIter>,
}

impl<O> Flatten<O> 
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            inner : None 
        }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        if let Some(ref mut inner_iter) = self.inner {
            if let Some(i) = inner_iter.next() {
                return Some(i);
            }
            self.inner = None;
        }
        
        let inner_item = self.outer.next()?;
        let mut inner_iter = inner_item.into_iter();
        inner_iter.next()
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn empty_wide()
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]].into_iter()).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }

    #[test]
    fn two()
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }

    #[test]
    fn two_wide()
    {
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]].into_iter()).count(), 2);
    }
}

Trait bound syntax

0:39:10

到這裡才知道到 bound 的用途是透過限制型態來保證函式內部相關值一定會有那個方法可已用。

Finishing corrected next

0:40:07

到現在還沒完成，我們還沒實作完成 flatten 函式，接著繼續修改

• 幾乎完成的版本，仍有錯誤 :
  ​​​​impl<O> Iterator for Flatten<O>
  ​​​​where
  ​​​​    O: Iterator, 
  ​​​​    O::Item: IntoIterator,
  ​​​​{
  ​​​​    type Item = <O::Item as IntoIterator>::Item; 
  ​​​​    fn next(&mut self) -> Option<Self::Item>
  ​​​​    {
  ​​​​        if let Some(ref mut inner_iter) = self.inner {
  ​​​​            if let Some(i) = inner_iter.next() {
  ​​​​                return Some(i);
  ​​​​            }
  ​​​​            self.inner = None;
  ​​​​        }
  
  ​​​​        // 若內部迭代器耗盡，接著要取外部迭代器的下一個元素
  ​​​​        // `?` 是說如果沒有值了就返回，
  ​​​​        //     有的話將值回傳，並將該值轉成迭代器
  ​​​​        let next_inner_iter = self.outer.next()?.into_iter();
  ​​​​        // 把它保存起來
  ​​​​        self.inner = Some(next_inner_iter);
  ​​​​        // 這樣還是不行，因為 ineer 迭代器若是空的，呼叫 next 會炸開。
  ​​​​        self.inner.as_mut().unwrap().next();
  ​​​​    }
  ​​​​}
  

• 正確實作版本 :
  ​​​​impl<O> Iterator for Flatten<O>
  ​​​​where
  ​​​​    O: Iterator, 
  ​​​​    O::Item: IntoIterator,
  ​​​​{
  ​​​​    type Item = <O::Item as IntoIterator>::Item; 
  ​​​​    fn next(&mut self) -> Option<Self::Item>
  ​​​​    {
  ​​​​        // 用迴圈的方法
  ​​​​        // 不用擔心無窮迴圈，這裡的目的只是要當內部迭代器耗盡，
  ​​​​        // 將外部迭代器繼續往下一個值移動，並再取內部迭代器的值就回傳了。
  ​​​​        loop {
  ​​​​            if let Some(ref mut inner_iter) = self.inner {
  ​​​​                if let Some(i) = inner_iter.next() {
  ​​​​                    return Some(i);
  ​​​​                }
  ​​​​                self.inner = None;
  ​​​​            }
  
  ​​​​            let next_inner_iter = self.outer.next()?.into_iter();
  ​​​​            self.inner = Some(next_inner_iter);
  ​​​​        }
  ​​​​    }
  ​​​​}
  

Q : do you normally include bounds on the struct definition as well, or just the impl block?
A : 通常只加在 impl block，但這裡比較特別的原因是我們的 struct 也要有 bound 才能確保可以呼叫函式。

經歷了一些語法疼痛之後，終於實作完了。

目前程式碼

pub fn flatten<I>(iter: I) -> Flatten<I>
where 
    I: Iterator,
    I::Item: IntoIterator,
{
    Flatten::new(iter)
}

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator
{
    outer : O,
    inner : Option<<O::Item as IntoIterator>::IntoIter>,
}

impl<O> Flatten<O> 
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            inner : None 
        }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut inner_iter) = self.inner {
                if let Some(i) = inner_iter.next() {
                    return Some(i);
                }
                self.inner = None;
            }

            let next_inner_iter = self.outer.next()?.into_iter();
            self.inner = Some(next_inner_iter);
        }
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn empty_wide()
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]].into_iter()).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }

    #[test]
    fn two()
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }

    #[test]
    fn two_wide()
    {
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]].into_iter()).count(), 2);
    }
}

Ergonomics with IntoIterator

0:42:50

將 into_iter 移到 flatten 函式內部，並做一些微調，可以精簡 test case :

-pub fn flatten<I>(iter: I) -> Flatten<I>
+pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where
-   I: Iterator,
+   I: IntoIterator,
    I::Item: IntoIterator,
{
-   Flatten::new(iter)
+   Flatten::new(iter.into_iter())
}
...
    #[test]
    fn empty_wide()
    {
-       assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]].into_iter()).count(), 0);
+       assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
    }
    ...
    fn two_wide()
    {
-       assert_eq!(flatten(vec![vec!["a"], vec!["b"]].into_iter()).count(), 2);
+       assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
    }
...

目前程式碼

pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where 
    I: IntoIterator,
    I::Item: IntoIterator,
{
    Flatten::new(iter.into_iter())
}

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator
{
    outer : O,
    inner : Option<<O::Item as IntoIterator>::IntoIter>,
}

impl<O> Flatten<O> 
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            inner : None 
        }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut inner_iter) = self.inner {
                if let Some(i) = inner_iter.next() {
                    return Some(i);
                }
                self.inner = None;
            }

            let next_inner_iter = self.outer.next()?.into_iter();
            self.inner = Some(next_inner_iter);
        }
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn empty_wide()
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }

    #[test]
    fn two()
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }

    #[test]
    fn two_wide()
    {
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
    }
}

Q : would while let Some(inner) = self.inner work here?

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        while let Some(inner) = self.inner {
            if let Some(i) = inner_iter.next() {
                return Some(i);
            }
            self.inner = None;
        }

        let next_inner_iter = self.outer.next()?.into_iter();
        self.inner = Some(next_inner_iter);
    }
}

A : 不行，next() 函式第一次被呼叫，我們必須要確保 Line 17, 18 被執行。

DoubleEndedIterator

0:44:15

Trait std::iter::DoubleEndedIterator

DoubleEndedIterator 讓你可以從左邊迭代到右邊。看到從標準函式庫看到它有一個方法，可以讓你從右邊迭代到左邊 :

fn next_back(&mut self) -> Option<Self::Item>;

First draft of DEI implementation

0:46:10

開始實作，新增程式碼 :

impl<O> DoubleEndedIterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    // 我們這裡可以直接引用 Self::Item，不用定義 type Item，
    // 因為 DoubleEndedIterator 是 Iterator 的擴展，
    // 可以實作成 DoubleEndedIterator 的型態，它本身就有實作 Iterator 了，
    // 當然就可以取的到 Self 的 Item。
    fn next_back(&mut self) ->Option<Self::Item> {
        None
    }
}

將 Flatten 的 Iterator 的程式碼直接貼到 Flatten 的 DoubleEndedIterator :

impl<O> DoubleEndedIterator for Flatten<O>
where
    // 加一個 bound
    O: Iterator + DoubleEndedIterator,
    O::Item: IntoIterator,
    // 新增全新的 bound
    <O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{ 
    fn next_back(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut inner_iter) = self.inner {
                if let Some(i) = inner_iter.next_back() {
                    return Some(i);
                }
                self.inner = None;
            }

            let next_inner_iter = self.outer.next_back()?.into_iter();
            self.inner = Some(next_inner_iter);
        }
    }
}

可以看到，光是要處理兩層的 flatten，bound 就要寫得這麼麻煩了，更多層的話，可想而知會更不好寫。

Q : what's the difference between + and , in trait bounds?
A : , 是新規則，+ 是該規則有多個 bound。

Testing double-ended iteration

0:50:57

新增 test case 來驗證剛剛實作的正不正確 :

    #[test]
    fn reverse()
    {
        assert_eq!(
            flatten(std::iter::once(vec!["a", "b"]))
                .rev()
                .collect::<Vec<_>>(),
            vec!["b", "a"]
        );
    }
    
    fn reverse_wide()
    {
        assert_eq!(
              flatten(vec![vec!["a"], vec!["b"]])
                  .rev()
                  .collect::<Vec<_>>(), 
              vec!["b", "a"]
        );
    }

:bulb: rev()

fn rev(self) -> Rev<Self>
where
    Self: Sized + DoubleEndedIterator,

Reverses an iterator’s direction.

Usually, iterators iterate from left to right. After using rev(), an iterator will instead iterate from right to left.

This is only possible if the iterator has an end, so rev() only works on DoubleEndedIterators.

目前程式碼

pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where 
    I: IntoIterator,
    I::Item: IntoIterator,
{
    Flatten::new(iter.into_iter())
}

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator
{
    outer : O,
    inner : Option<<O::Item as IntoIterator>::IntoIter>,
}

impl<O> Flatten<O> 
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            inner : None 
        }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut inner_iter) = self.inner {
                if let Some(i) = inner_iter.next() {
                    return Some(i);
                }
                self.inner = None;
            }

            let next_inner_iter = self.outer.next()?.into_iter();
            self.inner = Some(next_inner_iter);
        }
    }
}

impl<O> DoubleEndedIterator for Flatten<O>
where
    O: Iterator + DoubleEndedIterator,
    O::Item: IntoIterator,
    <O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{ 
    fn next_back(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut inner_iter) = self.inner {
                if let Some(i) = inner_iter.next_back() {
                    return Some(i);
                }
                self.inner = None;
            }

            let next_inner_iter = self.outer.next_back()?.into_iter();
            self.inner = Some(next_inner_iter);
        }
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn empty_wide()
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }

    #[test]
    fn two()
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }

    #[test]
    fn two_wide()
    {
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
    }

    #[test]
    fn reverse()
    {
        assert_eq!(
            flatten(std::iter::once(vec!["a", "b"]))
                .rev()
                .collect::<Vec<_>>(),
            vec!["b", "a"]
        );
    }

    #[test]
    fn reverse_wide()
    {
        assert_eq!(
              flatten(vec![vec!["a"], vec!["b"]])
                  .rev()
                  .collect::<Vec<_>>(), 
              vec!["b", "a"]
        );
    }
}

測試順利通過 :

$ cargo test
...
running 7 tests
test tests::empty ... ok
test tests::empty_wide ... ok
test tests::one ... ok
test tests::reverse ... ok
test tests::reverse_wide ... ok
test tests::two ... ok
test tests::two_wide ... ok
...

Iterating from both ends in parallel

0:53:58

但還是有問題，新增一個更複雜的 test case :

    #[test]
    fn both_ends()
    {
        let mut iter = flatten(vec![vec!["a", "b"], vec!["c", "d"]]);
        assert_eq!(iter.next(), Some("a"));
        assert_eq!(iter.next_back(), Some("d"));
        assert_eq!(iter.next(), Some("b"));
        assert_eq!(iter.next_back(), Some("c"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
    }

目前程式碼

pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where 
    I: IntoIterator,
    I::Item: IntoIterator,
{
    Flatten::new(iter.into_iter())
}

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator
{
    outer : O,
    inner : Option<<O::Item as IntoIterator>::IntoIter>,
}

impl<O> Flatten<O> 
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            inner : None 
        }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut inner_iter) = self.inner {
                if let Some(i) = inner_iter.next() {
                    return Some(i);
                }
                self.inner = None;
            }

            let next_inner_iter = self.outer.next()?.into_iter();
            self.inner = Some(next_inner_iter);
        }
    }
}

impl<O> DoubleEndedIterator for Flatten<O>
where
    O: Iterator + DoubleEndedIterator,
    O::Item: IntoIterator,
    <O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{ 
    fn next_back(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut inner_iter) = self.inner {
                if let Some(i) = inner_iter.next_back() {
                    return Some(i);
                }
                self.inner = None;
            }

            let next_inner_iter = self.outer.next_back()?.into_iter();
            self.inner = Some(next_inner_iter);
        }
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn empty_wide()
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }

    #[test]
    fn two()
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }

    #[test]
    fn two_wide()
    {
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
    }

    #[test]
    fn reverse()
    {
        assert_eq!(
            flatten(std::iter::once(vec!["a", "b"]))
                .rev()
                .collect::<Vec<_>>(),
            vec!["b", "a"]
        );
    }

    #[test]
    fn reverse_wide()
    {
          assert_eq!(
              flatten(vec![vec!["a"], vec!["b"]])
                  .rev()
                  .collect::<Vec<_>>(), 
              vec!["b", "a"]
        );
    }

    #[test]
    fn both_ends()
    {
        let mut iter = flatten(vec![vec!["a", "b"], vec!["c", "d"]]);
        assert_eq!(iter.next(), Some("a"));
        assert_eq!(iter.next_back(), Some("d"));
        assert_eq!(iter.next(), Some("b"));
        assert_eq!(iter.next_back(), Some("c"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
    }
}

新增的那個 test case 並未通過測試 :

$ cargo test
...
running 8 tests
test tests::empty ... ok
test tests::empty_wide ... ok
test tests::both_ends ... FAILED
test tests::one ... ok
test tests::reverse ... ok
test tests::two ... ok
test tests::two_wide ... ok
test tests::reverse_wide ... ok

failures:

---- tests::both_ends stdout ----
thread 'tests::both_ends' panicked at 'assertion failed: `(left == right)`
  left: `Some("b")`,
 right: `Some("d")`', src\lib.rs:134:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
...

因為外部迭代器的第一個元素的尚未耗盡，所以即使反轉了迭代方向還是會在第一個元素裡面走訪，下圖為圖解 :

將 test case 的元素稍微改一下，驗證猜想 :

    fn both_ends()
    {
        let mut iter = flatten(vec![vec!["a1", "a2", "a3"], vec!["b1", "b2", "b3"]]);
        assert_eq!(iter.next(), Some("a1"));
        assert_eq!(iter.next_back(), Some("b3"));
        assert_eq!(iter.next(), Some("a2"));
        assert_eq!(iter.next_back(), Some("b2"));
        assert_eq!(iter.next(), Some("a3"));
        assert_eq!(iter.next_back(), Some("b1"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
    }

出現了以下錯誤 :

$ cargo test
...
running 8 tests
test tests::both_ends ... FAILED
test tests::empty ... ok
test tests::empty_wide ... ok
test tests::one ... ok
test tests::reverse ... ok
test tests::reverse_wide ... ok
test tests::two ... ok
test tests::two_wide ... ok

failures:

---- tests::both_ends stdout ----
thread 'tests::both_ends' panicked at 'assertion failed: `(left == right)`
  left: `Some("a3")`,
 right: `Some("b3")`', src\lib.rs:134:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
...

證明前面圖解的推論是正確的。歸根究柢就是因為我們的 struct 的 inner 只能記錄單邊的游標所導致的，再多引入一個游標看看 :

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator 
    // bound 不用要求是 DoubleEndedIterator，
    // 因為 inner 迭代器的型別不管是妳從右到左或左到右走訪，
    // 它們的型態都會是一樣的。
{
    outer : O,
    front_iter : Option<<O::Item as IntoIterator>::IntoIter>, // 重命名變數
    back_iter : Option<<O::Item as IntoIterator>::IntoIter>,  // 新游標
}

接著修改 Flatten 的 impl block :

impl<O> Flatten<O> 
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            front_iter : None,
            back_iter : None, 
        }
    }
}

並且修改 next 的邏輯 :

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut front_iter) = self.front_iter {
                if let Some(i) = front_iter.next() {
                    return Some(i);
                }
                self.front_iter = None;
            }

            if let Some(next_inner) = self.outer.next() {
                self.front_iter = Some(next_inner.into_iter());
            } else {
                // 即 GIF 顯示我們想要處理的 case
                // as_mut : 我們只想要以 reference 的型式使用它
                return self.back_iter.as_mut()?.next();
            }
        }
    }
}

next_back 依樣畫葫蘆 :

impl<O> DoubleEndedIterator for Flatten<O>
where
    O: Iterator + DoubleEndedIterator,
    O::Item: IntoIterator,
    <O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{ 
    fn next_back(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut back_iter) = self.back_iter {
                if let Some(i) = back_iter.next_back() {
                    return Some(i);
                }
                self.back_iter = None;
            }

            if let Some(next_back_inner) = self.outer.next_back() {
                self.back_iter = Some(next_back_inner.into_iter());
            } else {
                // 即 GIF 顯示我們想要處理的 case，只是迭代方向相反而已
                return self.front_iter.as_mut()?.next_back();
            }
        }
    }
}

目前程式碼

pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where 
    I: IntoIterator,
    I::Item: IntoIterator,
{
    Flatten::new(iter.into_iter())
}

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator
{
    outer : O,
    front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
    back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}

impl<O> Flatten<O> 
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            front_iter : None,
            back_iter : None, 
        }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut front_iter) = self.front_iter {
                if let Some(i) = front_iter.next() {
                    return Some(i);
                }
                self.front_iter = None;
            }

            if let Some(next_inner) = self.outer.next() {
                self.front_iter = Some(next_inner.into_iter());
            } else {
                return self.back_iter.as_mut()?.next();
            }
        }
    }
}

impl<O> DoubleEndedIterator for Flatten<O>
where
    O: Iterator + DoubleEndedIterator,
    O::Item: IntoIterator,
    <O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{ 
    fn next_back(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut back_iter) = self.back_iter {
                if let Some(i) = back_iter.next_back() {
                    return Some(i);
                }
                self.back_iter = None;
            }

            if let Some(next_back_inner) = self.outer.next_back() {
                self.back_iter = Some(next_back_inner.into_iter());
            } else {
                return self.front_iter.as_mut()?.next_back();
            }
        }
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn empty_wide()
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }

    #[test]
    fn two()
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }

    #[test]
    fn two_wide()
    {
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
    }

    #[test]
    fn reverse()
    {
        assert_eq!(
            flatten(std::iter::once(vec!["a", "b"]))
                .rev()
                .collect::<Vec<_>>(),
            vec!["b", "a"]
        );
    }

    #[test]
    fn reverse_wide()
    {
          assert_eq!(
              flatten(vec![vec!["a"], vec!["b"]])
                  .rev()
                  .collect::<Vec<_>>(), 
              vec!["b", "a"]
        );
    }

    #[test]
    fn both_ends()
    {
        let mut iter = flatten(vec![vec!["a1", "a2", "a3"], vec!["b1", "b2", "b3"]]);
        assert_eq!(iter.next(), Some("a1"));
        assert_eq!(iter.next_back(), Some("b3"));
        assert_eq!(iter.next(), Some("a2"));
        assert_eq!(iter.next_back(), Some("b2"));
        assert_eq!(iter.next(), Some("a3"));
        assert_eq!(iter.next_back(), Some("b1"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
    }
}

修改完畢之後，順利通過所有測試了 :

$ cargo test
...
running 8 tests
test tests::both_ends ... ok
test tests::empty_wide ... ok
test tests::reverse_wide ... ok
test tests::two_wide ... ok
test tests::one ... ok
test tests::empty ... ok
test tests::two ... ok
test tests::reverse ... ok
...

Q : the inner refs are being reset with each direction, so it gets "lost" what the new ends would be.
A : 沒錯。

The cost of two cursors

1:04:02

:warning: 1:04:02
Q : is there a way to implement it in such a way that you don't have to pay the cost of two cursors when the iterator is only used in one way?
A : 有的，但這裡不講。不過你可能需要 specialization 才能讓這個技巧發揮作用，但想法是你要添加第二個泛型參數到 flatten，有些型別有實作 walk back。如果它沒有實作 walk back，你可以給它 zero slice 型別，這樣或許就能做到再沒有兩個游標情況下仍可以從兩端走訪。

Q : Why store back_iter even for types that aren't DoubleEndedIterator?
A : 原因如下 :

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator
{
    outer : O,
    // 補充說明 : 
    //     1. front_iter 和 back_iter 是被分配到 stack，成本低廉
    //     2. 當它們兩個被用完之後，值會自動被卸除。
    front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
    // 我們沒辦法在這裡說 :
    //     #[cfg(not_if_O: !DoubleEndedIterator)]
    back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
    // 這不僅僅是定義兩個不同的 flat 結構的問題，
    // 因為那樣它們將是不同的類型。
}

Iterators are like Futures

1:06:28

Q : This whole process gives me major future vibes. The whole stacking iters on iters.
A : 是的。

Calling next and next_back concurrently

1:07:14

Q : Can you call next and next_back concurrently?
A : 不行，可以看到函式簽章 :

fn next(&mut self) -> Option<Self::Item>
fn next_back(&mut self) -> Option<Self::Item>

兩者的傳入參數都必須要是 exclusive 的，所以你不能同時呼叫 next 和 next_back。

ref in patterns

1:07:55

Q : why do you need to use "ref mut" in Some(ref mut back_iter)?
A :

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        loop {
            // 說明開始
            self.front_iter: Option<T>
            // 這裡的 t 是擁有 T 的值，而不是它的參考，
            // 這樣會把 self.front_iter 的值移動到左邊的 
            // 回頭看函式簽章，我們現在有的是 mutable 參考
            // 所以我們是不能去耗用它並獲得 T 的所有權。
            if let Some(t: T) = self.front_iter {
                
            }
            // 說明結束
            ...
        }
    }
}

但我們可以做以下更換 :

// 原本，Jon 比較喜歡這種，我也是。
// if let Some(ref mut front_iter) = self.front_iter {
// 這樣也可以
if let Some(front_iter) = self.front_iter.as_mut() {

Why not flatten first, then iterate

1:09:33

Q : what if instead of "live" walking you'll "flatten" entire data into flatten structure and then iter() over it from both ends?
A : 這樣你就需要記憶體配置，而我們的實作是，即便元素是無限的，我們的方法也仍可以運作，因為我們只配置了指標，並且去移動它而已，例如下面的 test case :

    #[test]
    fn inf()
    {
        let mut iter = flatten((0..).map(|i| 0..i));
        // outer => inner
        // 0 => 0..0 => empty
        // 1 => 0..1 => [0]
        // 2 => 0..2 => [0, 1]
        assert_eq!(iter.next(), Some(0));
        assert_eq!(iter.next(), Some(0));
        assert_eq!(iter.next(), Some(1));
        // ... 
        // 無限呼叫 next 都 ok，因為過程不涉及額外的記憶體配置。
    }

可以通過 inf 測試 :

$ cargo test
...
running 9 tests
test tests::both_ends ... ok
test tests::two ... ok
test tests::one ... ok
test tests::empty ... ok
test tests::inf ... ok
test tests::two_wide ... ok
test tests::reverse ... ok
test tests::empty_wide ... ok
test tests::reverse_wide ... ok
...

目前程式碼

pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where 
    I: IntoIterator,
    I::Item: IntoIterator,
{
    Flatten::new(iter.into_iter())
}

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator
{
    outer : O,
    front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
    back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}

impl<O> Flatten<O> 
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            front_iter : None,
            back_iter : None, 
        }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut front_iter) = self.front_iter {
                if let Some(i) = front_iter.next() {
                    return Some(i);
                }
                self.front_iter = None;
            }

            if let Some(next_inner) = self.outer.next() {
                self.front_iter = Some(next_inner.into_iter());
            } else {
                return self.back_iter.as_mut()?.next();
            }
        }
    }
}

impl<O> DoubleEndedIterator for Flatten<O>
where
    O: Iterator + DoubleEndedIterator,
    O::Item: IntoIterator,
    <O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{ 
    fn next_back(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut back_iter) = self.back_iter {
                if let Some(i) = back_iter.next_back() {
                    return Some(i);
                }
                self.back_iter = None;
            }

            if let Some(next_back_inner) = self.outer.next_back() {
                self.back_iter = Some(next_back_inner.into_iter());
            } else {
                return self.front_iter.as_mut()?.next_back();
            }
        }
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn empty_wide()
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }

    #[test]
    fn two()
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }

    #[test]
    fn two_wide()
    {
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
    }

    #[test]
    fn reverse()
    {
        assert_eq!(
            flatten(std::iter::once(vec!["a", "b"]))
                .rev()
                .collect::<Vec<_>>(),
            vec!["b", "a"]
        );
    }

    #[test]
    fn reverse_wide()
    {
          assert_eq!(
              flatten(vec![vec!["a"], vec!["b"]])
                  .rev()
                  .collect::<Vec<_>>(), 
              vec!["b", "a"]
        );
    }

    #[test]
    fn both_ends()
    {
        let mut iter = flatten(vec![vec!["a1", "a2", "a3"], vec!["b1", "b2", "b3"]]);
        assert_eq!(iter.next(), Some("a1"));
        assert_eq!(iter.next_back(), Some("b3"));
        assert_eq!(iter.next(), Some("a2"));
        assert_eq!(iter.next_back(), Some("b2"));
        assert_eq!(iter.next(), Some("a3"));
        assert_eq!(iter.next_back(), Some("b1"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
    }

    #[test]
    fn inf()
    {
        let mut iter = flatten((0..).map(|i| 0..i));
        assert_eq!(iter.next(), Some(0));
        assert_eq!(iter.next(), Some(0));
        assert_eq!(iter.next(), Some(1));
    }
}

More ref in patterns

1:12:51

Q : ref mut should be inferred by the compiler now i believe
A : 並不是全部，這裡的用法就是例子。

當你有個模式，編譯器很聰明，它不會移動值，而是 mutably 借用 :

// Jon 還是最喜歡這種表達方式
// if let Some(ref mut front_iter) = self.front_iter {
// 可行方法
if let Some(front_iter) = &mut self.front_iter {

Q : then next_back() makes no sense… as next one will be rubbish if outer gets new item
A : 是的，我們的 inf test case 是不能呼叫 next_back 的，如果你常是呼叫，編譯器會回報以下的錯誤訊息給你 :

$ cargo test
...
error[E0599]: the method `next_back` exists for struct `Flatten<Map<RangeFrom<{integer}>, [[e-mail]:157:42]>>`, but its trait bounds were not satisfied
   --> src\lib.rs:161:25
...

Deeper flattening

1:14:09

Q : Does this code work for arbitrary nested iterators? I see it addresses two levels with outer and inner. how would it work for a third level?
A : 前面就有說到了，並不行。你還需要額外在 stcut 添加額外的 front_front_iter， front_back_iter, back_front_iter, back_back_iter，你需要追蹤你正在走訪的游標樹。

你可以 flatten 你之前 flatten 的結果，或許可能比起實作支援多層的 flatten 還要是繼一點，新增一個 test case :

    #[test]
    fn deep()
    {
        // 這樣你就可以取到第三層的值了
        assert_eq!(flatten(flatten(vec![vec![vec![0, 1]]])).count(), 2);
    }

通過測試 :

$ cargo test
...
running 10 tests
test tests::deep ... ok
test tests::both_ends ... ok
test tests::empty ... ok
test tests::empty_wide ... ok
test tests::inf ... ok
test tests::one ... ok
test tests::reverse ... ok
test tests::reverse_wide ... ok
test tests::two ... ok
test tests::two_wide ... ok
...

pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where 
    I: IntoIterator,
    I::Item: IntoIterator,
{
    Flatten::new(iter.into_iter())
}

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator
{
    outer : O,
    front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
    back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}

impl<O> Flatten<O> 
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            front_iter : None,
            back_iter : None, 
        }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut front_iter) = self.front_iter {
                if let Some(i) = front_iter.next() {
                    return Some(i);
                }
                self.front_iter = None;
            }

            if let Some(next_inner) = self.outer.next() {
                self.front_iter = Some(next_inner.into_iter());
            } else {
                return self.back_iter.as_mut()?.next();
            }
        }
    }
}

impl<O> DoubleEndedIterator for Flatten<O>
where
    O: Iterator + DoubleEndedIterator,
    O::Item: IntoIterator,
    <O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{ 
    fn next_back(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut back_iter) = self.back_iter {
                if let Some(i) = back_iter.next_back() {
                    return Some(i);
                }
                self.back_iter = None;
            }

            if let Some(next_back_inner) = self.outer.next_back() {
                self.back_iter = Some(next_back_inner.into_iter());
            } else {
                return self.front_iter.as_mut()?.next_back();
            }
        }
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn empty_wide()
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }

    #[test]
    fn two()
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }

    #[test]
    fn two_wide()
    {
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
    }

    #[test]
    fn reverse()
    {
        assert_eq!(
            flatten(std::iter::once(vec!["a", "b"]))
                .rev()
                .collect::<Vec<_>>(),
            vec!["b", "a"]
        );
    }

    #[test]
    fn reverse_wide()
    {
          assert_eq!(
              flatten(vec![vec!["a"], vec!["b"]])
                  .rev()
                  .collect::<Vec<_>>(), 
              vec!["b", "a"]
        );
    }

    #[test]
    fn both_ends()
    {
        let mut iter = flatten(vec![vec!["a1", "a2", "a3"], vec!["b1", "b2", "b3"]]);
        assert_eq!(iter.next(), Some("a1"));
        assert_eq!(iter.next_back(), Some("b3"));
        assert_eq!(iter.next(), Some("a2"));
        assert_eq!(iter.next_back(), Some("b2"));
        assert_eq!(iter.next(), Some("a3"));
        assert_eq!(iter.next_back(), Some("b1"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
    }

    #[test]
    fn inf()
    {
        let mut iter = flatten((0..).map(|i| 0..i));
        assert_eq!(iter.next(), Some(0));
        assert_eq!(iter.next(), Some(0));
        assert_eq!(iter.next(), Some(1));
    }

    #[test]
    fn deep()
    {
        assert_eq!(flatten(flatten(vec![vec![vec![0, 1]]])).count(), 2);
    }
}

Q : could you nest calls of flatten if it detects more than two levels?
A : 並不行，因為 flatten 是在編譯時期就被執行，所以你必須在呼叫 flatten 的時候就給它一個型別，這都發生在編譯時期。我們沒辦法在執行階段去檢查到底有幾層。

FlatMap

1:17:00

Struct std::iter::FlatMap

FlatMap 映射的是外部迭代器，而不是內部迭代器，FlatMap 的結構長得像這樣 :

pub struct Flatten<O, F, I> // 新增 F 跟 I
where 
    O: Iterator,
    F: FnMut(O::Item) -> I,
    I: IntoIterator,
    O::Item: IntoIterator
{
    outer : O,
    front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
    back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}

如果你想驗證本主題的概念是否都掌握了，你可以自己試著實作 FlatMap 看看。

Ergonomics through extension traits

1:18:19

現在我們想要做的是，是改變呼叫的方式 (flatten(...) -> .flatten())，因為原本的 freestanding function 有點惱人。，你原本就可以這樣呼叫了，因為迭代器就有實作了，但是呼叫的時候就不是用到我們實作的那個 flatten 了。現在想像一下迭代器本身沒有實作 flatten，我們可以用 extension trait :

pub trait IteratorExt: Iterator {
    fn our_flatten(self) -> Flatten<Self> 
    where 
        Self::Item: IntoIterator;
}
// 任何型別只要有實作 Iterator，將會獲得 IteratorExt trait
impl<T> IteratorExt for T
where 
    T: Iterator
{
    fn our_flatten(self) -> Flatten<Self> 
    where 
        Self::Item: IntoIterator
    {
        flatten(self)
    }
}

新增 test case 來驗證是否可以用 .flatten() 方式呼叫我們的 flatten :

    #[test]
    fn ext()
    {
        assert_eq!(flatten([vec![vec![0, 1]]]).our_flatten().count(), 2);
    }

嘗試編譯看看，得到了以下錯誤 :

error[E0277]: the size for values of type `Self` cannot be known at compilation time
  --> src\lib.rs:2:29
   |
2  |     fn our_flatten(self) -> Flatten<Self> 
   |                             ^^^^^^^^^^^^^ doesn't have a size known at compile-time

Sized in traits

1:21:19

編譯不過的原因如下 :

// 拿到 O 的型別
pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator
{
    // 把這個 O 儲存到這個結構體的 outer 成員
    // 你可以這麼做的前提是，你必須知道 O 的大小是什麼
    // 如果 O 的型別是 trait 的名稱，trait 本身是沒有大小的，
    // 所以不能將 O 的值存到 outer 成員。
    // O 必須是 `Sized`，`Size` 是 Rust 用來表達型別已知大小的 trait。
    outer : O,
    front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
    back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}

回到編譯器的錯誤訊息就清楚知道 Flatten<Self> 要有 Sized 才可以，因為 Self 不是 Sized，所以要多加一個 bound :

pub trait IteratorExt: Iterator {
    fn our_flatten(self) -> Flatten<Self> 
    where 
        Self: Sized, // 加在這裡
        Self::Item: IntoIterator;
}
    ...
    #[test]
    fn ext()
    {
        // 還要多呼叫 into_iter()
        // 變成 Iterator 才可以獲得 IteratorExt trait
        assert_eq!(flatten([vec![vec![0, 1]]]).into_iter().our_flatten().count(), 2); 
    } 

:question: 為什麼我的編譯器版本不用 into_iter() 也可以編譯的過 ?

目前程式碼

pub trait IteratorExt: Iterator {
    fn our_flatten(self) -> Flatten<Self> 
    where 
        Self: Sized,
        Self::Item: IntoIterator;
}

impl<T> IteratorExt for T
where 
    T: Iterator
{
    fn our_flatten(self) -> Flatten<Self> 
    where 
        Self::Item: IntoIterator
    {
        flatten(self)
    }
}

pub fn flatten<I>(iter: I) -> Flatten<I::IntoIter>
where 
    I: IntoIterator,
    I::Item: IntoIterator,
{
    Flatten::new(iter.into_iter())
}

pub struct Flatten<O>
where 
    O: Iterator,
    O::Item: IntoIterator
{
    outer : O,
    front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
    back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}

impl<O> Flatten<O> 
where 
    O: Iterator,
    O::Item: IntoIterator,
{
    fn new(iter: O) -> Self 
    {
        Flatten { 
            outer : iter, 
            front_iter : None,
            back_iter : None, 
        }
    }
}

impl<O> Iterator for Flatten<O>
where
    O: Iterator, 
    O::Item: IntoIterator,
{
    type Item = <O::Item as IntoIterator>::Item; 
    fn next(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut front_iter) = self.front_iter {
                if let Some(i) = front_iter.next() {
                    return Some(i);
                }
                self.front_iter = None;
            }

            if let Some(next_inner) = self.outer.next() {
                self.front_iter = Some(next_inner.into_iter());
            } else {
                return self.back_iter.as_mut()?.next();
            }
        }
    }
}

impl<O> DoubleEndedIterator for Flatten<O>
where
    O: Iterator + DoubleEndedIterator,
    O::Item: IntoIterator,
    <O::Item as IntoIterator>::IntoIter: DoubleEndedIterator,
{ 
    fn next_back(&mut self) -> Option<Self::Item>
    {
        loop {
            if let Some(ref mut back_iter) = self.back_iter {
                if let Some(i) = back_iter.next_back() {
                    return Some(i);
                }
                self.back_iter = None;
            }

            if let Some(next_back_inner) = self.outer.next_back() {
                self.back_iter = Some(next_back_inner.into_iter());
            } else {
                return self.front_iter.as_mut()?.next_back();
            }
        }
    }
}

#[cfg(test)]
mod tests
{
    use super::*;
    #[test]
    fn empty() 
    {
        assert_eq!(flatten(std::iter::empty::<Vec<()>>()).count(), 0);
    }

    #[test]
    fn empty_wide()
    {
        assert_eq!(flatten(vec![Vec::<()>::new(), vec![], vec![]]).count(), 0);
    }

    #[test]
    fn one()
    {
        assert_eq!(flatten(std::iter::once(vec!["a"])).count(), 1);
    }

    #[test]
    fn two()
    {
        assert_eq!(flatten(std::iter::once(vec!["a", "b"])).count(), 2);
    }

    #[test]
    fn two_wide()
    {
        assert_eq!(flatten(vec![vec!["a"], vec!["b"]]).count(), 2);
    }

    #[test]
    fn reverse()
    {
        assert_eq!(
            flatten(std::iter::once(vec!["a", "b"]))
                .rev()
                .collect::<Vec<_>>(),
            vec!["b", "a"]
        );
    }

    #[test]
    fn reverse_wide()
    {
          assert_eq!(
              flatten(vec![vec!["a"], vec!["b"]])
                  .rev()
                  .collect::<Vec<_>>(), 
              vec!["b", "a"]
        );
    }

    #[test]
    fn both_ends()
    {
        let mut iter = flatten(vec![vec!["a1", "a2", "a3"], vec!["b1", "b2", "b3"]]);
        assert_eq!(iter.next(), Some("a1"));
        assert_eq!(iter.next_back(), Some("b3"));
        assert_eq!(iter.next(), Some("a2"));
        assert_eq!(iter.next_back(), Some("b2"));
        assert_eq!(iter.next(), Some("a3"));
        assert_eq!(iter.next_back(), Some("b1"));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next_back(), None);
    }

    #[test]
    fn inf()
    {
        let mut iter = flatten((0..).map(|i| 0..i));
        assert_eq!(iter.next(), Some(0));
        assert_eq!(iter.next(), Some(0));
        assert_eq!(iter.next(), Some(1));
    }

    #[test]
    fn deep()
    {
        assert_eq!(flatten(flatten(vec![vec![vec![0, 1]]])).count(), 2);
    }

    #[test]
    fn ext()
    {
        assert_eq!(flatten([vec![vec![0, 1]]]).into_iter().our_flatten().count(), 2);
    }
}

Q : So you could implement flatten as outer.flat_map(|inner| inner)
A : 是的。

Q : why not implement monad laws? it would be a lot less confusing
A : 本次是要探討迭代器的觀念。

Q : why do I sometimes see a ?Sized
A : 請看下面程式碼說明 :

pub struct Flatten<O: ?Sized> // 因為是 Box<O>，所以可以不用知道大小
where 
    O: Iterator,
    O::Item: IntoIterator
{
    outer : Box<O>, // 存到 Box，即便編譯器不知道東西大小也可以存
    front_iter : Option<<O::Item as IntoIterator>::IntoIter>,
    back_iter : Option<<O::Item as IntoIterator>::IntoIter>,
}

Q : could you put the bounds into the trait IteratorExt instead of the function our_flatten? Or is that not good?
A : 可以，如下 :

-pub trait IteratorExt: Iterator {
+pub trait IteratorExt: Iterator + Sized {
    fn our_flatten(self) -> Flatten<Self> 
    where 
-       Self: Sized,
        Self::Item: IntoIterator;
}