Подсчет элементов в дереве в Haskell
В основном я сделал полиморфный древовидный тип данных, и мне нужен способ считать число элементов в данном дереве. Вот объявление для моего Древовидного типа данных:
data Tree a = Empty
| Leaf a
| Node (Tree a) a (Tree a)
deriving (Eq, Ord, Show)
Таким образом, я могу определить дерево Ints как это:
t :: Tree Int
t = Node (Leaf 5) 7 (Node (Leaf 2) 3 (Leaf 7))
Однако мне нужна функция для подсчета числа элементов в одном из этих списков. Я определил эту рекурсивную функцию, но я добираюсь, ошибка "вывела тип, не является достаточно общим":
size :: Tree a -> Int
size Empty = 0
size (Leaf n) = 1
size (Node x y z) = size x + size y + size z
Есть ли что-то здесь, я не должен делать?
2 ответа
Я думаю, что это просто опечатка, когда вы пишете
size (Node x y z) = size x + size y + size z
, которое должно быть просто
size (Node x y z) = size x + size z + 1
, поскольку y - это не поддерево, а просто сохраненный элемент.
Или, чтобы было понятнее
size (Node left elem right) = size left + size right + 1
Технически ваша ошибка возникает из-за того, что термин размер y имеет смысл только в том случае, если y снова является деревом, размер которого можно вычислить. Следовательно, тип этого предложения будет выведен из Tree (Tree a) -> Int , что по сравнению с фактическим Tree a -> Int , не является общим { {1}} достаточно .
Посмотрите на последнее предложение: если посмотреть на левую часть, на Node xyz , какой тип y ? Имеет ли смысл размер y ?