計算Haskell中樹中的元素

基本上我做了一個多態樹數據類型，我需要一種計算給定樹中元素數量的方法。下面是我的樹數據類型聲明：計算Haskell中樹中的元素

data Tree a = Empty 
| Leaf a 
| Node (Tree a) a (Tree a) 
deriving (Eq, Ord, Show)

所以我可以定義INTS的樹是這樣的：

t :: Tree Int 
t = Node (Leaf 5) 7 (Node (Leaf 2) 3 (Leaf 7))

不過，我需要一個函數來計算在其中的一個元素的數量名單。我定義這個遞歸函數，但我得到的錯誤「推斷的類型不是一般不夠」：

size :: Tree a -> Int 
size Empty = 0 
size (Leaf n) = 1 
size (Node x y z) = size x + size y + size z

有東西在這裏我不應該這樣做？

來源

2010-02-07 benwad

我認爲，當你寫

size (Node x y z) = size x + size y + size z

這應該只是

size (Node x y z) = size x + size z + 1

因爲y是沒有樹，但只存儲元素，它只是一個錯字。

或者使它更加清晰

size (Node left elem right) = size left + size right + 1

從技術上講，你出現錯誤，因爲這個詞size y也纔有意義，如果y又是一棵樹的大小可以計算。因此，該條款的類型將被推斷爲Tree (Tree a) -> Int，即與實際的Tree a -> Int,相比不是通用的足夠的。

來源

2010-02-07 17:21:32 Dario

難道不是'size x + 1 + size z'？由於他在計算元素，每個節點都包含一個元素。 – BaroqueBobcat 2010-02-07 17:26:14

@BaroqueBobcat：Argh ... Yep;） – Dario 2010-02-07 17:31:14

實際上，所寫的'size'類型將是無限類型'Tree（Tree（Tree ...））） - > Int'。在這些情況下，一個好的方法是始終忽略違規類型簽名，讓編譯器告訴你它認爲應該是什麼類型。在這種情況下，GHC告訴我，它試圖構建一個無限類型... – yatima2975 2010-02-07 18:05:13

看看你最後一句：看看左邊，在Node x y z，什麼是y的類型？ size y有意義嗎？

來源

2010-02-07 17:21:08 MtnViewMark

計算Haskell中樹中的元素

回答

相關問題