haskell - Haskell：计算树的节点

Question

我有一个自定义数据类型：

data Tree a = Node a [Tree a]

示例树：

tree1 = Node 3 [Node 4 [Node 3 [], Node 2 []], Node 5 []]

我正在努力创建一个函数来计算树的节点。

我有一个功能：

numNodes :: Num p => Tree a -> p
numNodes(Node a []) = 0
numNodes(Node a b) = 1 + numNodes b

但这并没有真正起作用，我错在哪里？

编辑：编译器输出：

   • Couldn't match type ‘Tree a’ with ‘[Tree a]’
      Expected type: [Tree a] -> p
        Actual type: Tree a -> p

   • Relevant bindings include
        numNodes :: [Tree a] -> p (bound at tree.hs:28:1)


28 | numNodes(Node a []) = 0

标签： haskellcountfunctional-programmingtreenodes

Answer 1

首先，您不能用您的数据类型表示一棵空树；您只能表示具有单个节点且没有子树的树。

numNodes (Node a []) = 1

其次，将每个节点作为 0 个或多个子树作为子节点。您需要使用map计算每个子树中的节点数，然后将每个子树的计数相加。

numNodes (Node a b) = 1 + sum (map numNodes b)

因为sum [] == 0根据定义，您实际上并不需要基本情况​​，因为sum (map numNodes b)无论是否b非空都会返回正确的计数。