haskell - 如何检查 BST 是否有效？

Question

根据 BST 的定义并使用 BST 的通用折叠版本，如何检查 BST 是否有效？

data(Ord a, Show a, Read  a) => BST a = Void | Node {
    val :: a,
    left, right :: BST a
} deriving (Eq,  Ord,  Read, Show)


fold :: (Read a, Show a, Ord a) => (a -> b -> b ->  b) -> b -> BST a -> b
fold _ z Void         = z
fold f z (Node x l r) = f x (fold f z l) (fold f z r)

想法是检查节点值是否大于左子树中的所有值并且小于其右子树中的所有值。这必须是True对于树中的所有节点。一个函数bstList只需输出 BST 中的(有序)值列表即可。

当然，这样的事情是行不通的:

--isBST :: (Read a, Show a, Ord a) => BST a -> Bool
isBST t = fold (\x l r -> all (<x) (bstList l) && all (>x) (bstList r)) (True) t

因为，例如，将折叠函数应用于节点 19最终all (<19) (bstList True) && all (>19) (bstList True) .

Answer 1

您的问题似乎是您丢失了信息，因为您的函数在检查左右子树时仅返回 bool 值。因此将其更改为还返回子树的最小值和最大值。(这可能也更有效，因为您不需要使用bslist来检查所有元素不再)

当然，创建一个包装函数以在完成后忽略这些“辅助”值。