在 Haskell 中测试两棵树是否相等和二叉搜索树

Question

我有点坚持为二叉搜索树实现一个 Eq 实例。我想检查两棵树中的值是否相同，但我真的不知道如何正确地做到这一点。由于两个二叉搜索树的结构可能不同，我不能直接比较节点。我的想法是将它们转换成一个列表，对列表进行排序并比较它们，但这看起来很复杂，我想知道是否有另一种方法可以做到这一点。这是我到目前为止得到的：

data BB a = L | K a (BB a) (BB a) deriving (Show)

instance Eq BB where
  not (isBinarySearchTree t1 && isBinarySearchTree t2) = False
  inOrder t1 == inOrder t2 = True

Answer 1

接受的答案在我看来是错误的，因为你说你想根据树的概念内容而不是它们的确切结构进行比较。也就是说，您希望满足以下条件：

K 1 L (K 2 L L) == K 2 (K 1 L L) L

具有相同两个元素的两个 BST，排序正确但结构不同。在结构上比较它们，如 severij 的回答，产生 False，但你希望它是 True.

那么，如何不按结构比较而是按内容比较呢？好吧，任何两个具有相同项目集的 BST 都将具有相同的中序遍历。所以，你可以完全按照你在问题中所说的那样做：将它们转换为列表，然后比较列表。但是您不必对它们进行排序：因为它们是 BST，所以您可以保证可以按相同的顺序遍历它们。将它们转换为列表并不是非常昂贵，所以不用担心：懒惰和流融合使得它的成本与手动编写遍历的成本大致相同。

如果你的树类型有一个 Foldable 实例，这会容易得多，无论如何，这对树来说是一件好事。定义Foldable，只需要定义foldr，很简单：

import Prelude hiding (foldr)
import Data.Foldable (Foldable, foldr, toList)

instance Foldable BB where
  foldr f init L = init
  foldr f init (K x left right) = foldr f (f x (foldr f init right)) left

然后你可以根据toList定义Eq:

instance Eq (BB a) where
  x == y = toList x == toList y

之后，根据需要，

*Main> (K 1 L (K 2 L L)) == (K 2 (K 1 L L) L)
True

但这是相当多的工作，不是吗？在写这个答案时，我多次弄错 foldr 的定义。事实证明，有一种方法可以避免必须自己编写：DeriveFoldable 语言扩展让 GHC 可以像派生 Show 一样轻松地为您派生 Foldable。但是由于它按顺序折叠数据类型中的字段，因此您必须对其进行一些更改，以便左子树出现在根节点之前：

{-# LANGUAGE DeriveFoldable #-}

import Prelude hiding (foldr)
import Data.Foldable (Foldable, foldr, toList)

data BB a = L | K (BB a) a (BB a) deriving (Show, Foldable)

instance Eq (BB a) where
  x == y = toList x == toList y

事实上，我们仍然有期望的相等性属性（尽管我们必须以不同的方式编写节点，因为我们更改了字段顺序）：

*Main> (K L 1 (K L 2 L)) == (K (K L 1 L) 2 L)
True

还有最后一项改进：如果导入 Data.Function.on，Eq 定义也可以更简单。不用手写，用 on 你可以简单地说 "to compare two trees for equality, convert each to a list and compare those lists for equality"。完整保留树定义和其他导入，我们终于获得了所需功能的非常简洁的定义，所有实际工作都由已编写的库函数完成：

{-# LANGUAGE DeriveFoldable #-}

import Prelude hiding (foldr)
import Data.Foldable (Foldable, foldr, toList)
import Data.Function (on)

data BB a = L | K (BB a) a (BB a) deriving (Show, Foldable)

instance Eq a => Eq (BB a) where
  (==) = (==) `on` toList

在 Haskell 中测试两棵树是否相等和二叉搜索树

Test if two trees are equal and binary search trees in Haskell

tree

haskell

equality

binary-search-tree