0

我试图在 Haskell 中实现一个简单的布尔函数来检查两个 n 元树是否相等。

我的代码是：

-- 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])

它正确返回false，因为树不相等，但是如果我尝试进行以下测试：

treeEquals t (Node 3 [])

它不起作用，因为它在树相等时返回 true。

你知道我做错了什么吗？

4

2 回答 2

3

你为什么不直接派生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-13T18:44:23.970 回答
1

在 zipWith 之前添加另一个 && 并检查列表的长度是否相同。

于 2012-12-13T18:46:13.987 回答