Конструктор не находится в ошибке разбора совпадения Scope / Pattern

Question

У меня есть следующий тип данных:

data Tree a = Node [Tree a]

, и я хочу подсчитать, сколько узлов в таком дереве, поэтому я определил следующее:

count:: Tree a -> Integer
count [] = 0
count Node label [childrenTree a] = 1 + count a

, что дает мнеошибка «Ошибка разбора в шаблоне: истина». Если я изменяю childrenTree a на Tree a, это говорит о том, что конструктор данных не находится в области действия.

Как мне решить эту проблему?

Answer 1

Указывает, что функция count имеет три аргумента, а это не то, что вам нужно:

count Node label [childrenTree a] = ...
   -- ^1   ^2    ^3

Далее,

count [] = ...

указывает, что существует один аргумент, которыйдолжен быть список (пустой список, если быть точным). Вы хотите, чтобы count принимал деревья в качестве аргумента, а не списки.

Правильный способ написания кода:

count:: Tree a -> Integer
count (Node subtrees) = ...   -- here, we have subtrees :: [Tree a]

В качестве альтернативы:

count:: Tree a -> Integer
count (Node [])     = ...
count (Node (t:ts)) = ...
           --here t is the first tree in the list, ts is the list of remaining ones

---

Вот полная рабочая программа:

data Tree a = Node [Tree a]

count:: Tree a -> Integer
count (Node [])     = 1
count (Node (t:ts)) = count t + count (Node ts)

-- a little test
main :: IO ()
main = print (count (Node [Node [], Node [Node[], Node[]]]))

Выходное значение равно 5, то есть числу Node с на входе.

Answer 2

В общих деревьях есть сложная часть, которую нужно учитывать, у вас есть функция в самом дереве, и у вас есть рекурсия по списку деревьев. Другое дело, что дерево, как оно есть, не сохраняет никакой ценной информации, вы можете немного ее изменить как:

data Tree a = Node a [Tree a] deriving (Show)

и две функции будут выглядеть так:

count:: Tree a -> Integer
count (Node _ trees) = 1 + countLs trees

countLs []     = 0
countLs (t:ts) = (count t) + (countLs ts)

и небольшая демонстрация:

genTree1 = NodeG "1" [NodeG "2" [],
                         NodeG "3" [NodeG "4" [],
                                   NodeG "5" [NodeG "6" [],
                                             NodeG "7" [],
                                             NodeG "8" []
                                             ]
                                   ]
                         ]

пример выполнения:

$> count genTree1
8