haskell - 我的 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 和 右树。结果，永远不会探索右子树。相应地修改代码，

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

编辑:正如 Luis Casillas 在 his comment 中指出的那样，这个替代定义的另一个好处是它更适合(比原始定义)编译器详尽检查。