Haskell 树 - 搜索树

Question

我的作业有问题：我正在尝试编写一个代码，列出我告诉他的所有节点值（例如，将值为 4 的所有节点放入一个整洁的列表中） .

我写了以下内容：

findValue :: a -> (MyTree a) -> [a]
findValue x Leaf = []
findValue x (Node a l r)
    |a == x = x++(findValue x l)++(findValue x r)
    |a /= x = (findValue x l)++(findValue x r)

我定义树如下：

data MyTree a = Leaf  | Node a (MyTree a) (MyTree a)

我收到以下错误消息：

Couldn't match expected type ‘[a]’ with actual type ‘a’
      ‘a’ is a rigid type variable bound by
          the type signature for findValue :: a -> MyTree a -> [a]
          at assignment.hs:10:14
    Relevant bindings include
      r :: MyTree a (bound at assignment.hs:12:25)
      l :: MyTree a (bound at assignment.hs:12:23)
      a :: a (bound at assignment.hs:12:21)
      x :: a (bound at assignment.hs:12:11)
      findValue :: a -> MyTree a -> [a]
        (bound at assignment.hs:11:1)
    In the first argument of ‘(++)’, namely ‘x’
    In the expression: x ++ (findValue x l) ++ (findValue x r)

如果有人向我解释错误信息，我将非常高兴。提前致谢！

Answer 1

(++)的类型是[a] -> [a] -> [a]，但是x的类型是a。因此你可以写

x : (findValue x l) ++ (findValue x r) （使用 "cons" 运算符 (:) :: a -> [a] -> [a]），或

[x] ++ (findValue x l) ++ (findValue x r)

以下是您应该自己确定的方法：

错误显示 Couldn't match exptected type '[a]' with actual type 'a' ... in the first argument of '(++)', namely 'x'

这意味着参数 x 到 (++)（在指示的行上）应该具有类型 [a]（即预期类型），但实际上具有a类型（推断类型）。

那么你应该查找 (++) 的类型签名，看看问题可能是什么（例如使用 hoogle, hayoo, or ghci）在你的情况下，问题是第一个和第二个的类型(++) 的参数不一样，但应该是。

Answer 2

想想你在做什么。 findValue 是 a -> MyTree a -> [a] 类型，这意味着 x 是 a.

类型

但是，(++)运算符是[a] -> [a] -> [a]类型的，而你写的是x ++ (findValue x l) ++ (findValue x r)。因此它给你一个错误说：

Couldn't match expected type ‘[a]’ with actual type ‘a’
      ‘a’ is a rigid type variable bound by
          the type signature for findValue :: a -> MyTree a -> [a]
          at assignment.hs:10:14
    Relevant bindings include
      r :: MyTree a (bound at assignment.hs:12:25)
      l :: MyTree a (bound at assignment.hs:12:23)
      a :: a (bound at assignment.hs:12:21)
      x :: a (bound at assignment.hs:12:11)
      findValue :: a -> MyTree a -> [a]
        (bound at assignment.hs:11:1)
    In the first argument of ‘(++)’, namely ‘x’
    In the expression: x ++ (findValue x l) ++ (findValue x r)

报错信息明明是Couldn't match expected type ‘[a]’ with actual type ‘a’。它进一步告诉你问题出在哪里，In the first argument of ‘(++)’, namely ‘x’。它甚至会告诉您在哪里可以找到该表达式 In the expression: x ++ (findValue x l) ++ (findValue x r).

Haskell 错误消息可能看起来很吓人，但它们实际上提供了丰富的信息且易于理解。不要让像 ‘a’ is a rigid type variable bound by 这样的短语吓到你。

我明白当你读到的第二句话是你不明白的东西时很容易放弃，而且我明白在 SO 上 post 关于它的问题更容易。帮自己一个忙，不要。了解如何理解错误消息。

授人以鱼，一日不食。授人以渔，终生受用

顺便说一句，为什么需要 findValue 类型的 a -> MyTree a -> [a] 函数？更有意义的是：

hasValue :: a -> MyTree a -> Bool
hasValue x Leaf         = False
hasValue x (Node a l r)
    | a == x            = True
    | otherwise         = findValue x l || findValue x r

numValue :: a -> MyTree a -> Int
numValue x Leaf         = 0
numValue x (Node a l r)
    | a == x            = depth + 1
    | otherwise         = depth
    where depth = findValue x l + findValue x r

对我来说，findValue 函数没有任何意义，因为给定 findValue x t 结果是：

空列表或非空列表（分别为 False 或 True）。因此 hasValue.
仅重复 x 个值的列表，在这种情况下，只有长度很重要。因此 numValue.
```
findValue :: a -> MyTree a -> [a]
findValue x t = replicate (numValue x t) x
```

Haskell 树 - 搜索树

Haskell Tree - searching through tree

tree

haskell