haskell - 使用 Preorder 遍历 IntTree

Question

我正在尝试创建一个预购函数来遍历 IntTree。

树类如下

data IntTree = Empty | Branch IntTree Int IntTree deriving (Show, Eq)

我有两个问题 1. 我收到如下所示的错误。

E:\Haskell\Uebungsblatt_2_Aufgabe_2_a.hs:7:14: error:
    * Expected kind `* -> Constraint', but `IntTree' has kind `*'
    * In the type signature: preorder :: (IntTree c) => c -> [a]
  |
7 | preorder :: (IntTree c) => c->[a]

  |              ^^^^^^^^^
[Finished in 0.5s]

我不明白为什么。它们发生在以下行

preorder :: (IntTree c) => c->[a]

2. 我认为以下行是不正确的。我想我需要写其他表达式而不是“ l : preorder a : preorder r:[] ”

preorder Branch a l r = l : preorder a : preorder r:[]

我提前感谢您的帮助！

main :: IO ()    -- This says that main is an IO action.
main = return () -- This tells main to do nothing

data IntTree = Empty | Branch IntTree Int IntTree deriving (Show, Eq)


preorder :: (IntTree c) => c->[a]
preorder Empty = []
preorder Branch Empty x Empty = [x]
preorder Branch a l r = l : preorder a : preorder r:[]

标签： haskellpreorder

Answer 1

对于问题 1：签名

preorder :: (IntTree c) => c->[a]

错了：IntTree不是类型类，它是普通类型，所以我们可以按原样使用它。

preorder :: IntTree -> [Int]

最终类型必须是Int，因为我们生成的是整数列表，而不是[a]for any的列表a。

对于问题 2： :将元素添加到列表中，它具有类型

(:) :: a -> [a] -> [a]

因此，它不会连接两个列表。为此，请改用

(++) :: [a] -> [a] -> [a]

如在

preorder (Branch a l r) = l : preorder a ++ preorder r

（最后不需要使用++ []）