haskell二叉樹函數

Question

我必須在haskell中編寫一個函數來檢查兩個二叉樹是否是彼此的鏡像。這是我迄今爲止，但我不知道如果真正& & areMirrorImages l1 r2 & & areMirrorImages r1 l2是正確的方式來做到這一點。我試圖邏輯與真正的遞歸調用areMirrorImages函數的結果。

-- Tests whether two BinaryTrees are mirror images of one another 
areMirrorImages :: (Eq (BinaryTree a), Eq a) => BinaryTree a -> BinaryTree a -> Bool 
areMirrorImages Empty Empty = True 
areMirrorImages _ Empty = False 
areMirrorImages Empty _  = False 
areMirrorImages (Node x1 left1 right1) (Node x2 left2 right2) = 
    if (x1 == x2 && left1 == right2 && right1 == left2) 
then True && (areMirrorImages left1 right2) && (areMirrorImages right1 left2) 
else False 

這是錯誤我得到當我試圖編譯：

A2.hs:2:0: 
    Non-type variables, or repeated type variables, 
     in the constraint: Eq (BinaryTree a) 
    (Use -fglasgow-exts to permit this) 
    In the type signature: 
     areMirrorImages :: (Eq (BinaryTree a), Eq a) => 
         BinaryTree a -> BinaryTree a -> Bool 

我似乎無法找出什麼是錯的

Answer 1

也許你需要的唯一的限制是公式一，若二叉樹有一個方程的派生實例。派生實例會看起來像：

instance Eq a => Eq (BinaryTree a) where 
    ... 

因此，知道a可以平等將使哈斯克爾弄清楚，你BinaryTree a值可以比較相等進行比較。

你的邏輯看起來好像對我來說可能是錯的。例如，除非均爲left1 == right2和areMirrorImages left1 right2爲真，否則您的函數將返回False。除非left1和right2是對稱的，假設正確實現了areMirrorImages，否則這兩者不能同時存在。

Answer 2

需要Eq (BinaryTree a)意味着你需要比較（測試Eq性）兩棵樹。您不需要這樣做，因爲您正在測試以查看樹木是否是彼此的鏡像，而不是如果它們是平等的。

什麼時候樹木相互鏡像？當鍵是相同的，並且相反的分支是彼此的鏡像時。

的關鍵是一樣的：x1 == x2

對面分支鏡像：areMirrorImages left1 right2 && areMirrorImages right1 left2

翻譯成哈斯克爾：

areMirrorImages (Node x1 left1 right1) (Node x2 left2 right2) = 
    x1 == x2 && areMirrorImages left1 right2 && areMirrorImages right1 left2 

哈斯克爾允許你編寫簡潔，明瞭的代碼。沒有必要使用if then else。

Answer 3

你有正確的想法。我把你的版本修剪了一下，它似乎工作得很好：

data BinaryTree a = Empty | Node a (BinaryTree a) (BinaryTree a) 
        deriving(Show, Eq) 

areMirrorImages :: (Eq a) => BinaryTree a -> BinaryTree a -> Bool 
areMirrorImages (Node x1 left1 right1) (Node x2 left2 right2) 
    | x1 == x2 = areMirrorImages left1 right2 && 
        areMirrorImages right1 left2 
    | otherwise = False 
areMirrorImages Empty Empty = True 
areMirrorImages _ _ = False 

那麼我改變了什麼？

類型簽名 - 最後，你才真正需要調用樹的元素==，所以只有a需要是Eq一個實例。 （儘管我在數據聲明中推導了Eq）

條件 - 就像我說的，最後你只需要測試特定的元素是否相等。檢查left1 == right2 && right1 == left2是否合適，因爲他們的不應該等於，這些分支應該是彼此的鏡像。

守衛而不是如果 - 我認爲守衛比ifs更漂亮。

該模式匹配 - 這是一個小清潔（imho），只是最後一個全面的假。

我一直在努力學習QuickCheck最近，所以我也抽出了這段代碼來證明areMirrorImages的作品。

instance (Arbitrary a) => Arbitrary (BinaryTree a) where 
    arbitrary = fromList `fmap` arbitrary 

fromList :: [a] -> BinaryTree a 
fromList []  = Empty 
fromList (x:xs) = Node x (fromList lhalf) (fromList rhalf) 
    where (lhalf, rhalf) = splitAt (length xs `div` 2) xs 

mirror :: BinaryTree a -> BinaryTree a 
mirror Empty = Empty 
mirror (Node x l r) = Node x (mirror r) (mirror l) 

prop_mirror tree = areMirrorImages tree (mirror tree) 

我的Arbitrary爲BinaryTree不是最好的;它只會使近乎平衡的樹木。但我覺得這很不錯。另請注意，prop_mirror僅適用於areMirrorImages應返回True時的測試;它不會暴露潛在的誤報（儘管我確信沒有）。

*Main> quickCheck prop_mirror 
+++ OK, passed 100 tests.