Haskell에서 두 개의 n-ary 트리가 같은지 확인하십시오.

Question

두 개의 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]) 

를이 나무가 동일하지 않기 때문에 제대로 false를 반환하지만 테스트를 시도하는 경우

treeEquals t (Node 3 []) 

트리가 동일하므로 true를 반환하기 때문에 작동하지 않습니다.

내가 뭘 잘못하고 있는지 알아?

Answer 1

가 zipWith 전에 다른 & &를 추가하고 목록의 길이가 같은 경우 확인.

Answer 2

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