haskell - 创建可以是多种类型的函数时遇到问题

Question

我试图在 Traceable 类中创建一个单一的函数，它让我可以使用二叉树和变量树并输出所有可能的叶子路径列表。我似乎无法编译并且已经绞尽脑汁试图弄清楚几个小时。如果有人能帮我一把，那就太棒了。

这是我的代码

data Tree a = Null | Node a [Tree a] deriving Show
data BinTree a = Nil | Vertex a (BinTree a) (BinTree a) deriving Show

class Traceable a where
trace :: (BinTree a, Tree z) => z a -> [a]

instance Traceable (BinTree a) where{
trace Nil = []
trace (Vertex x l r) = trace l ++ [x] ++ trace 

instance Traceable (Tree a) where{
trace Null = []
trace (Node a x) = [a] ++ (trace (head x))}

我收到此错误

* Expected a constraint, but `BinTree a' has kind `*'
* In the type signature:
    trace :: (BinTree a, Tree z) => z a -> [a]
  In the class declaration for `Traceable'

* Expected a constraint, but `Tree z' has kind `*'
* In the type signature:
    trace :: (BinTree a, Tree z) => z a -> [a]
  In the class declaration for `Traceable'

* Expecting one fewer argument to `z'
  Expected kind `* -> *', but `z' has kind `*'
* In the type signature:
    trace :: (BinTree a, Tree z) => z a -> [a]
  In the class declaration for `Traceable'

编辑:这对我来说是一个学校项目，我不能使用任何 Haskell 扩展

做你建议的事情会更进一步，但我仍然有一些错误。

* Expecting one fewer argument to `BinTree a'
  Expected kind `* -> *', but `BinTree a' has kind `*'
* In the first argument of `Traceable', namely `BinTree a'
  In the instance declaration for `Traceable (BinTree a)'

* Expecting one fewer argument to `Tree a'
  Expected kind `* -> *', but `Tree a' has kind `*'
* In the first argument of `Traceable', namely `Tree a'
  In the instance declaration for `Traceable (Tree a)'

编辑 #2
感谢您的帮助，从 BinTree 实例化中取出 a 似乎产生了另一个问题

* Couldn't match expected type `[a]'
              with actual type `t0 a0 -> [a0]'
* In the second argument of `(++)', namely `trace'
  In the second argument of `(++)', namely `[x] ++ trace'
  In the expression: trace l ++ [x] ++ trace
* Relevant bindings include
    r :: BinTree a (bound at tree.hs:11:20)
    l :: BinTree a (bound at tree.hs:11:18)
    x :: a (bound at tree.hs:11:16)
    trace :: BinTree a -> [a] (bound at tree.hs:10:2)

Answer 1

错误的原因只是 trace 的签名方法。讨论没有意义BinTree或 Tree那里 - 这些是类的实例，将及时提及(当您声明 instance 时)，而不是在类声明中。你想要的是

class Traceable t where
  trace :: t a -> [a]

然后应该编写实例

instance Traceable BinTree where
  trace Nil = []
  ...
instance Traceable Tree where
  ...

Tree 中还有一个问题实例: trace (head x)只为节点中的第一个子树创建跟踪。一方面，这甚至不能保证存在(可能有零个分支)，另一方面，通常会有多个其他分支以这种方式被忽略。您想要做的是递归到所有分支，即对于 x 中的所有元素列表。 “为列表中的所有事物做某事”通常建议您可以使用 map .所以， map trace x .但是，类型为 [[a]] (因为每个 trace 生成 [a] ，你最终会得到这些列表的列表。

您想要做的是将所有这些列表连接在一起。可以用，等一下: concat .

  trace (Node a x) = [a] ++ concat (map trace x)

...或更优雅

  trace (Node a x) = a : concat (trace <$> x)

事实上，映射和连接的组合是如此普遍，以至于存在一个标准函数: concatMap .而且，它是臭名昭著的 Monad的特色方法。类型类，其中列表是一个实例。知道了就可以写

  trace (Node a x) = a : (trace =<< x)

这是相当不错的。

但实际上，您不需要做任何事情，因为将多态容器的所有字段聚集在一起的想法也非常普遍，并且可以自动处理。这是推荐的解决方案:

{-# LANGUAGE DeriveFunctor, DeriveFoldable #-}

import Data.Foldable

data Tree a = Null | Node a [Tree a]
 deriving (Show, Functor, Foldable)
data BinTree a = Nil | Vertex (BinTree a) a (BinTree a)
 deriving (Show, Functor, Foldable)

然后简单地 trace = toList .