Подсчет элементов в дереве в Хаскеле

Question

По сути, я создал тип данных полиморфного дерева, и мне нужен способ подсчета количества элементов в данном дереве. Вот объявление для моего типа данных Tree:

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

Есть ли здесь что-то, что я не должен делать?

Answer 1

Я думаю, что это просто опечатка, когда вы пишете

size (Node x y z) = size x + size y + size z

что должно быть просто

size (Node x y z) = size x + size z + 1

, поскольку у не поддерево, а просто сохраненный элемент.

Или, чтобы сделать его еще яснее

size (Node left elem right) = size left + size right + 1

---

Технически, ваша ошибка возникает из-за того, что термин size y имеет смысл, только если y снова дерево, размер которого можно вычислить. Поэтому тип этого пункта будет выведен на Tree (Tree a) -> Int, что по сравнению с фактическим Tree a -> Int, не является общим достаточно .

Answer 2

Посмотрите на последнее предложение: как выглядит y с левой стороны, на Node x y z? size y имеет смысл?