2

现在我有树数据类型：

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
4

3 回答 3

5

do是一个关键字，用于为monads启用一些语法糖。在这种情况下，不需要单子。

这里有两种情况：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类型约束就足够了。

于 2018-03-10T21:15:01.110 回答
5

Do 是为了单子。

而是使用任何.

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]
于 2018-03-10T21:26:40.683 回答
3

一种选择是使用elem，它检查值是否是Foldable容器的元素。

treeLook :: Eq a => a -> TernaryTree a -> Bool
treeLook = elem

现在你只需要写一个Foldable. 一种选择是启用DeriveFoldable扩展并仅用于deriving (Show, Foldable)让 GHC 为您编写实例。但是那样你不会学到很多东西。因此，让我们探索一些方法来做到这一点。

-- This import is needed for non-bleeding-edge GHC versions.
import Data.Monoid ((<>))

instance Foldable TernaryTree where
  -- Fold over the tree in pre-order
  foldMap _ EmptyTree = mempty
  foldMap f (Node x ls cs rs) =
    f x <> foldMap f ls <> foldMap f cs <> foldMap f rs

但是这种重复foldMap本身就是一种“模式”，您可以通过为树编写“catamorphism”来提取：

cataTree :: r -> (a -> r -> r -> r -> r) -> TernaryTree a -> r
cataTree e _ EmptyTree = e
cataTree e f (Node x ls cs rs) =
  f x (cataTree e f ls) (cataTree e f cs) (cataTree e f rs)

现在您可以foldMap这样定义：

foldMap f = cataTree mempty (\a lr cr rr -> f a <> lr <> cr <> rr)

现在foldMap自己有了一个更厉害的表弟，traverse。所以另一种选择是从那里开始：

import Data.Traversable (fmapDefault, foldMapDefault)

instance Traversable TernaryTree where
  -- Traverse the tree in pre-order
  traverse f =
    cataTree (pure EmptyTree)
             (\a ls cs rs -> Node <$> f a <*> ls <*> cs <*> rs)

instance Functor TernaryTree where
  fmap = fmapDefault

instance Foldable TernaryTree where
  foldMap = foldMapDefault

显然，您不会想要做任何花哨的事情，但是一旦您想要快速生成一堆函数，这些技术实际上是有用的。

于 2018-03-10T23:29:57.183 回答