Haskell:在三元树中查找值,树未排序

Question

现在我有树数据类型:

data TernaryTree a = EmptyTree
                   | Node a (TernaryTree a) (TernaryTree a) (TernaryTree a)
                   deriving (Show)

我正在尝试创建一个可以在三元树中循环一个值的函数.树没有排序.

treeLook :: (Ord a)=> a -> TernaryTree a -> Bool
treeLook x EmptyTree = False
treeLook x (Node a left mid right) =
    if x /= a
        then do
        treeLook x left 
        treeLook x mid
        treeLook x right
        else 
        True

我现在有这个,但我无法编译它.它说:

Couldn't match expected type "m0 b0" with actual type "bool" on the line:
    treeLook x right

Answer 1

do是一个关键字,用于为monad启用一些语法糖.在这个引用中,没有必要使用monad.

这里有两种情况:EmptyTree这意味着我们找不到值,所以我们返回False.

因为Node我们可以检查最多四个条件:我们查找的值是值,第一个子树中的值是第二个子树中的值,是第三个子树中的值.从其中一项检查开始True,我们就可以返回True.如果所有检查都失败,我们返回False,这是逻辑或(||)的行为.所以我们可以这样写:

treeLook :: Eq a => a -> TernaryTree a -> Bool
treeLook _ EmptyTree = False
treeLook x (Node a l m r) = x == a || treeLook x l || treeLook x m || treeLook x r

或者我们可以定义一个本地范围的函数,阻止我们递归传递我们正在寻找的值:

treeLook :: Eq a => a -> TernaryTree a -> Bool
treeLook x = go
    where go EmptyTree = False
          go (Node a l m r) = x == a || go l || go m || go r

注意,由于树没有排序,我们不需要Ord a类型约束,我们只需要检查相等(这里x == a),所以Eq a类型约束就足够了.

Answer 2

Do 是针对 monad 的。

而是使用任何.

treeLook _ EmptyTree = False
treeLook x (Node y l m r) = any id [x == y, look l, look m, look r]
    where look = treeLook x

正如指出的那样，还是更好地使用。

treeLook x (Node y l m r) = or [x == y, look l, look m, look r]
    where look = treeLook x

我最喜欢的是这个：

treeLook _ EmptyTree = False
treeLook x (Node y l m r) = x == y || any (treeLook x) [l, m, r]