Haskell размер дерева

Question

Ещё один haskell noob здесь!

Я пытаюсь получить размер дерева?

data Tree a = Leaf a | Node (Tree a) (Tree a) 

size :: Tree a -> Int 
size empty = 0 
size (Leaf n) = 1 
size (Node x z) = size x + size z + 1 

Если я вызываю функцию с

size (Node (Node (Leaf 1)(Leaf 3)) (Leaf 2)) 

Все, что я получаю 0. Является ли правильный код, и я просто не назвав его правильно?

BTW, я видел множество примеров с пустым, а не пустым, но это вызывает ошибку при компиляции. Что мне здесь не хватает?

Answer 1

Обратите внимание, что у вас есть совпадение совпадений в вашей функции size. Строка size empty будет всегда совпадать с шаблоном, в результате чего всегда будет значение 0. Ваша size функция должна быть такой:

size :: Tree a -> Int 
size (Leaf n) = 1 
size (Node x z) = size x + size z + 1 

Demo в ghci:

λ> size (Node (Node (Leaf 1)(Leaf 3)) (Leaf 2)) 
5 

Answer 2

Эта линия является проблематичным:

size empty = 0 

empty не является конструктором, так что он соответствует ничего, и немедленно возвращает 0, что делает вашу функцию эквивалентной const 0.

Потому что есть без пустого дерева с вашим определением, бессмысленно добавлять такую ​​строку.

Если ты хочешь, чтобы сделать возможным пустое дерево, вы должны изменить ваши определения немного:

data Tree a = Empty | Node a (Tree a) (Tree a) 

size Empty  = 0 
size (Node _ a b) = 1 + size a + size b