list - 树的标签

Question

具有以下数据类型

data Tree a = Node a [Tree a]

我想创建以下功能:

labels:: Tree a -> [a]
labels (Node label children) = label: (map labels children)

但这实际上是

   * Occurs check: cannot construct the infinite type: a ~ [a]
      Expected type: [a]
        Actual type: [[a]]

将 child 设置为 x:xs 也没有帮助，因为 xs 仍然是一个树列表而不是一棵树。

Answer 1

您的函数labels的类型为Tree a -> [a]。这意味着，如果您构造一个 map labels，它的类型为 map labels::[Tree a] -> [[a]]。因此，您需要连接这些项目，以便我们生成一个列表 [a] 而不是 [[a]]。

您可以使用concatMap :: Foldable f => (a -> [b]) -> f a -> [b]相反:

labels :: Tree a -> [a]
labels (Node label children) = label : <b>concatMap</b> labels children

Having children as x:xs didnt help either as xs would still be a list of trees and not a single tree.

事实上，此外，通过使用(x:xs)，您将(不必要)将自己限制在具有非空子列表的树上。一种常见的误解是，x 和 xs 是 (x:xs) 中的“特殊”变量名称。您只需对“cons”数据构造函数进行模式匹配(:)。