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

Но это не совсем работает, где я не прав?

Edit: Выход компилятора:

   • 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

Answer 1

Во-первых, вы не можете представлять пустое дерево с вашим типом данных; Вы можете представлять дерево только с одним узлом без поддеревьев.

numNodes (Node a []) = 1

Во-вторых, каждый узел как 0 или более поддерево как дочерние. Вам нужно использовать map для вычисления количества узлов в каждом поддереве, а затем суммировать количество для каждого дочернего элемента.

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

Поскольку sum [] == 0 по определению, вам на самом деле не нужен базовый случай, так как sum (map numNodes b) вернет правильный счет независимо от того, является ли b непустым.