创建一个可以是多种类型的函数时遇到麻烦

我试图在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)

leftaroundab.. 7

错误的原因仅仅是该trace方法的签名。谈论BinTree或Tree在那里没有意义-这些是该类的实例，并且会在您声明时及时（而instance不是在类声明内）提及。你想要的是

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

然后应该写实例

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

There's another problem in the Tree instance: trace (head x) just creates the trace for the first subtree in the node. For one thing, that's not even guaranteed to exist (there could be zero branches), for another, there will typically be multiple other branches that are ignored this way. What you want to do is recurse into all the branches, i.e. for all the elements in the x list. “Doing something for all things in a list” generally suggests that you could use map. So, map trace x. However, that has type [[a]] (because each trace generates [a], and you end up with a list of those lists.

What you want to do is concatenate all of those lists together. That can be done with, wait for it: concat.

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

...or more elegantly

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

实际上，映射和串联的组合非常普遍，以至于存在一个标准功能：concatMap。而且，它是臭名昭著的Monad类型类的特征方法，其中列表是一个实例。知道了，你可以写

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

很好

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

{-# 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。


1> leftaroundab..：
错误的原因仅仅是该trace方法的签名。谈论BinTree或Tree在那里没有意义-这些是该类的实例，并且会在您声明时及时（而instance不是在类声明内）提及。你想要的是

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


然后应该写实例

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


There's another problem in the Tree instance: trace (head x) just creates the trace for the first subtree in the node. For one thing, that's not even guaranteed to exist (there could be zero branches), for another, there will typically be multiple other branches that are ignored this way. What you want to do is recurse into all the branches, i.e. for all the elements in the x list. “Doing something for all things in a list” generally suggests that you could use map. So, map trace x. However, that has type [[a]] (because each trace generates [a], and you end up with a list of those lists.

What you want to do is concatenate all of those lists together. That can be done with, wait for it: concat.

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


...or more elegantly

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


实际上，映射和串联的组合非常普遍，以至于存在一个标准功能：concatMap。而且，它是臭名昭著的Monad类型类的特征方法，其中列表是一个实例。知道了，你可以写

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

很好

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

{-# 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。