檢查兩個n-ary樹在Haskell中是否相等

我想在Haskell中實現一個簡單的布爾函數來檢查兩個n元樹是否相等。檢查兩個n-ary樹在Haskell中是否相等

我的代碼是：

-- This is the n-ary tree definition. 
-- (I know "Leaf a" is not necessary but I prefer to write it for clarity) 
data Tree a = Leaf a | Node a [Tree a] 
    deriving (Show) 

-- This is a simple tree used for test purposes 
t :: Tree Int 
t = Node 3 [Node 5 [Leaf 11, Leaf 13, Leaf 15], Leaf 7, Leaf 9] 

treeEquals :: Eq a => Tree a -> Tree a -> Bool 
treeEquals (Leaf n1) (Leaf n2) = n1 == n2 
treeEquals (Node n1 xs1) (Node n2 xs2) = n1 == n2 && and(zipWith (treeEquals) xs1 xs2) 
treeEquals _ _ = False

我的問題是，如果我做的測試，如：

treeEquals t t 
treeEquals t (Leaf 3) 
treeEquals t (Node 3 [Leaf 7])

返回正確的錯誤，因爲樹是不相等的，但如果我嘗試測試如：

treeEquals t (Node 3 [])

它不起作用，因爲它返回true，因爲樹是等於的。

你知道我在做什麼錯嗎？

來源

2012-12-13 JohnQ

有沒有更好的方法來實現這個方法，而不使用zipWith避免兩個列表遍歷？ – JohnQ

以這種方式使用'Leaf'實際上會導致冗餘表示：'Node x []'vs'Leaf x'。冗餘表示通常只應用於一個很好的理由（例如，如果它們允許某些操作更快）。在這種情況下，只需放下'Leaf'構造函數似乎是最好的行爲。或者，您可以將'Node'構造函數更改爲'Node a（Tree a）[Tree a]'，但爲什麼要麻煩？ – dfeuer

的zipWith之前添加另一個& &和檢查列表的長度是相同的。

來源

2012-12-13 18:46:13

這樣做意味着可能有兩個列表遍歷 - 最好不要首先使用zipWith。 –

@達爾文，謝謝你的回答。我沒有想到，它非常簡單！ – JohnQ

爲什麼你不只是派生Eq並使用==？

您當前的代碼的問題是zipWith。它一到達較短列表的末尾就會停止，因此zipWith treeEquals foo []總是返回[]（不管foo是什麼）。

下面是一個（未經測試），另一種解決方案：

treeEquals :: Eq a => Tree a -> Tree a -> Bool 
treeEquals (Leaf n1) (Leaf n2) = n1 == n2 
treeEquals (Node n1 xs1) (Node n2 xs2) = n1 == n2 && listTreeEquals xs1 xs2 
    where 
    listTreeEquals [] [] = True 
    listTreeEquals (x1 : xs1) (x2 : xs2) = treeEquals x1 x2 && listTreeEquals xs1 xs2 
    listTreeEquals _ _ = False 
treeEquals _ _ = False

來源

2012-12-13 18:44:23 melpomene

謝謝你的回答。是的，我明白了問題所在。不幸的是，我必須實施我自己的方法，因爲我必須自己鍛鍊自己參加考試。我試圖實現所有可能的事情，他們可以問我，所以我不能只使用==。 – JohnQ

@JohnQ這裏關於'（==）'的很酷的事情是，即使你不派生它，但是你自己實現它，你可以定義'（Node n1 xs1）==（Node n2 xs2）= n1 == n2 && xs1 == xs2' [加上其他情況下的方程，'葉/葉'和'_/_']。然後'xs1 == xs2'使用通用的'實例Eq a => Eq [a]'來做正確的事情。對於你的'treeEquals'，你可以簡單地使用'treeEquals =（==）';） –

檢查兩個n-ary樹在Haskell中是否相等

回答

相關問題