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

问题描述

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

标签： haskell

解决方案

错误的原因只是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)个子树创建跟踪。一方面，这甚至不能保证存在（可能有零个分支），另一方面，通常会有多个其他分支以这种方式被忽略。您要做的是递归到所有分支，即列表中的所有元素。“为列表中的所有事物做某事”通常建议您可以使用. 所以，。但是，它具有类型（因为每个都生成，并且您最终会得到这些列表的列表。xmapmap 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。

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

问题描述

解决方案

推荐阅读