樹鏽摺疊

Question

我試圖實施tree fold生鏽。我的first attempt編譯並按預期運行。

pub enum Tree<T> { 
    Leaf, 
    Node(Box<Tree<T>>, T, Box<Tree<T>>) 
} 

impl<T, U: Copy> Tree<T> { 
    fn fold(self, f: |l: U, x: T, r: U| -> U, acc: U) -> U { 
     match self { 
      Leaf => acc, 
      Node(box l, x, box r) => { 
       let l = l.fold(|l,x,r| {f(l,x,r)}, acc); 
       let r = r.fold(|l,x,r| {f(l,x,r)}, acc); 
       f(l, x, r) 
      } 
     } 
    } 
} 

fn main() { 
    let tl = Node(box Leaf, 1i, box Leaf); 
    let tr = Node(box Leaf, 2i, box Leaf); 
    let t = Node(box tl, 3i, box tr); 

    println!("size(t) == {}", t.fold(|l,_,r|{l + 1i + r}, 0)) 
} 

然而，當我嘗試的size的implementation搬進impl塊，使它的方法：

pub enum Tree<T> { 
    Leaf, 
    Node(Box<Tree<T>>, T, Box<Tree<T>>) 
} 

impl<T, U: Copy> Tree<T> { 
    fn fold(self, f: |l: U, x: T, r: U| -> U, acc: U) -> U { 
     match self { 
      Leaf => acc, 
      Node(box l, x, box r) => { 
       let l = l.fold(|l,x,r| {f(l,x,r)}, acc); 
       let r = r.fold(|l,x,r| {f(l,x,r)}, acc); 
       f(l, x, r) 
      } 
     } 
    } 

    fn size(self) -> uint { 
     self.fold(|l, _, r| {l + 1u + r}, 0u) 
    } 
} 

fn main() { 
    let tl = Node(box Leaf, 1i, box Leaf); 
    let tr = Node(box Leaf, 2i, box Leaf); 
    let t = Node(box tl, 3i, box tr); 

    println!("size(t) == {}", t.size()) 
} 

我得到了鏽圍欄下面的錯誤。

<anon>:28:31: 28:39 error: cannot determine a type for this expression: unconstrained type 
<anon>:28  println!("size(t) == {}", t.size()) 
            ^~~~~~~~ 
note: in expansion of format_args! 
<std macros>:2:23: 2:77 note: expansion site 
<std macros>:1:1: 3:2 note: in expansion of println! 
<anon>:28:5: 29:2 note: expansion site 
error: aborting due to previous error 
playpen: application terminated with error code 101 
Program ended. 

我希望有人能闡明什麼，我做錯了，如何解決它的一些情況。

Answer 1

你的兩件事情有着至關重要的區別。

在第一，你有這樣的：

t.fold(|l,x,r|{l + x + r}, 0) 

在第二，你有這樣的（顯示爲self改爲t）：

t.fold(|l, x, r| {l + 1 + r}, 0) 

看到區別？ l + 1 + r不是l + x + r。

（此後，所有的情況下都成爲l + 1 + r，尺寸，而不是l + x + r，對於總和。）

你做了之後，你會碰到的問題，因爲uint不int。你需要整理你的T和U。基本上，你想要l,x,r和0都是相同類型，早期的T。這需要T進一步的限制：

• 它必須是Copy，以滿足U。

• 您必須添加T至T並獲得T。這是std::num::Add<T, T>。

• 您必須能夠得到類型爲T的零。這是std::num::Zero性狀和Zero::zero()方法。

• 您必須能夠獲得一個T類型。這是std::num::One特徵和One::one()方法。

雖然我們在這，U也許應該是在fold功能明確，而不是impl塊一個通用的，雖然二者都行。

最後，我們結束了這個functioning code：

use std::num::Zero; 

pub enum Tree<T> { 
    Leaf, 
    Node(Box<Tree<T>>, T, Box<Tree<T>>) 
} 

impl<T> Tree<T> { 
    fn fold<U: Copy>(self, f: |l: U, x: T, r: U| -> U, acc: U) -> U { 
     match self { 
      Leaf => acc, 
      Node(box l, x, box r) => { 
       let l = l.fold(|l, x, r| f(l, x, r), acc); 
       let r = r.fold(|l, x, r| f(l, x, r), acc); 
       f(l, x, r) 
      } 
     } 
    } 
} 

impl<T: Copy + Add<T, T> + Zero + One> Tree<T> { 
    fn size(self) -> T { 
     self.fold(|l: T, _: T, r: T| l + One::one() + r, Zero::zero()) 
    } 
} 

fn main() { 
    let tl = Node(box Leaf, 1i, box Leaf); 
    let tr = Node(box Leaf, 2i, box Leaf); 
    let t = Node(box tl, 3i, box tr); 

    println!("size(t) == {}", t.size()) 
} 

（注意周圍封閉的內容的大括號怎麼都沒有必要了。）