我的isElement函数(二叉树)出了什么问题？

Question

我正在研究一个检查元素是否是二叉树的一部分的函数.我为我的树定义了一个类型,称为Tree函数以获取根元素和左右子树,以及一个函数,isElement用于检查值是否在我的树中.不幸的是,该函数仅适用于根元素.

以下示例说明了从isElement函数中获得的错误结果:

*Main>let tree = Node 1 Empty (Node 2 Empty (Node 3 Empty Empty))
*Main> isElement  tree 2
False
*Main> isElement  tree 3
False
*Main> isElement  tree 1
True

这是我的代码:

data Tree a = Node a (Tree a) (Tree a) 
        |Empty
        deriving (Show)

nodeValue :: Tree t -> t
nodeValue (Node x _ _) = x

rightTree :: Tree t -> Tree t
rightTree (Node _ _ x) = x

leftTree :: Tree t -> Tree t
leftTree (Node _ x _) = x

isNode ::  Tree t -> Bool 
isNode (Node _ _ _) = True
isNode _ = False

isElement :: (Eq t) => Tree t -> t -> Bool
isElement tree t
    |isNode tree == False = False 
    | nodeValue(tree) == t = True
    | otherwise = (isElement (leftTree(tree)) t) || (isElement (leftTree(tree)) t)

Answer 1

有一个在你定义一个错误isElement的功能:你打电话leftTree的,而不是调用都两次,leftTree和rightTree.因此,从未探索过正确的子树.相应地修改代码,

isElement tree t
    |isNode tree == False = False 
    | nodeValue(tree) == t = True
    | otherwise = (isElement (leftTree(tree)) t) || (isElement (rightTree(tree))

然后isElement像宣传的那样工作:

?> let tree = Node 1 Empty (Node 2 Empty (Node 3 Empty Empty))
?> isElement tree 2
True
?> isElement tree 3
True
?> isElement tree 1
True

但是,仍有改进的余地.你并不真的需要所有这些功能(isNode,nodeValue,等)来定义isElement.相反,您可以通过将模式匹配解压缩,将定义分解为两个等式:一个对应于树为空的情况,另一个对应于树为节点的情况:

isElement :: (Eq a) => Tree a -> a -> Bool
isElement Empty        _ = False
isElement (Node v l r) x = v == x || isElement l x || isElement r x

编辑:正如路易斯·卡西利亚斯在评论中指出的那样,这个替代定义的另一个好处是,它比编译器的详尽检查更适合(比原始定义).