haskell - Haskell で 2 つの n 分木が等しいかどうかを確認する

Question

Haskell で単純なブール関数を実装して、2 つの 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を返すため、機能しません。

私が間違っていることを知っていますか？

Answer 1

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

Answer 2

zipWith の前に別の && を追加し、リストの長さが同じかどうかを確認します。