функция двоичного дерева haskell

Question

Мне нужно написать функцию в haskell, которая проверяет, являются ли два двоичных дерева зеркальным отображением друг друга. Это то, что я имею до сих пор, но я не знаю, является ли True && 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

Требование Eq (BinaryTree a) означает, что вам нужно сравнить (проверить на Eq реальность) два дерева.Вам не нужно этого делать, потому что вы проверяете, являются ли деревья зеркалами друг друга, а не равны ли они.

Когда деревья являются зеркалами друг друга?Когда ключ одинаков и когда противоположные ветви являются зеркальными изображениями друг друга.

Ключ одинаков: x1 == x2

Противоположными ветвями являются зеркальные изображения: areMirrorImages left1 right2 && areMirrorImages right1 left2

Переведите это на Haskell:

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

Haskell позволяет писать краткий, простой код.Нет необходимости использовать if then else.

Answer 2

Вероятно, единственное ограничение, которое вам нужно, - это уравнение, если BinaryTree имеет производный экземпляр уравнения.Этот производный экземпляр будет выглядеть примерно так:

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

Следовательно, знание того, что a можно сравнить на равенство, позволит Haskell выяснить, что ваши значения BinaryTree a можно сравнить на равенство.

Ваша логика также выглядит так, как будто это неправильно для меня.Ваша функция вернет False, если, например, и left1 == right2, и areMirrorImages left1 right2 не имеют значение True.Оба не могут быть истинными, если left1 и right2 не симметричны, при условии правильной реализации areMirrorImages.

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, поскольку они не должны быть равны , эти ветви должны быть зеркалами друг друга.

Охранник вместо if - я думаю, что охранники красивее, чем ifs.

Шаблон соответствует - Немного чище (imho), чтобы в конце просто было всеобщее False.

В последнее время я пытался изучить 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.