Функция для измерения размера двоичного дерева

Question

Когда я попытался size (N a (left a) (right a)) вместо size (N a left right), мне сказали, что эта строка конфликтует при определении.Я не уверен почему, потому что в моей подписи данных это N a (Tree a) (Tree a).size - это функция для подсчета количества узлов в бинарном дереве.

data Tree a = Nil | N a (Tree a) (Tree a) deriving (Show, Read, Eq)


size :: Tree Int -> Int
size Nil = 0
size (N _ left right) = 1 + size left + size right

Answer 1

Чтобы помочь вам увидеть, что происходит, вы можете написать внутренние совпадающие узлы для именования левого и правого поддеревьев и их соответствующих значений с помощью

size (N _ left@(N a _ _) right@(N b _ _)) = 1 + size left + size right

Раздел 3.17.1 «Шаблоны» описывает, что происходит с символами at, которые позволяют программисту называть левое и правое поддеревья.

Шаблоны вида var@pat называются as-pattern и разрешить использовать var в качестве имени для сопоставляемого значения: pat .

. Широкий подход неэлегатен по ряду причин.

1. left и right уже ограничены типом Tree из-за объявления Tree алгебраического типа данных.
2. Гораздо хуже, вы бытакже необходимо определить три других случая size для одного или двух Nil аргументов.

Раздел 3.17.2 Неофициальная семантика сопоставления с образцом описывает случаи длякак язык обрабатывает шаблоны.Особого внимания вам в контексте этого вопроса заслуживают

1.Сопоставление шаблона var со значением v всегда завершается успешно и связывает var с v .

и

5.Сопоставление шаблона con pat ₁ … pat _n со значением, где con - конструктор, определенный data, зависит отзначение:

• Если значение имеет вид con v ₁ … v _n , подшаблоны сопоставляются слева-право против компонентов значения данных;если все совпадения успешны, общее совпадение успешно;первый сбой или расхождение приводят к сбою или расхождению общего совпадения соответственно.
• Если значение имеет вид con ′ v ₁ … v _n , где con - это конструктор, отличный от con ′ , сопоставление не выполняется.
• Если значение равно ⊥, совпадение расходится.

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

Сравнение с шаблоном Haskell может быть более сложным, например , просмотр шаблонов ,Для изучения упражнений сначала освоите основы.

Answer 2

Когда я попытался изменить размер (N a (слева a) (справа a)) вместо размера (N a left right)

left и right в этомcase - это выражения типа Tree Int.

a не является известной переменной или типом в этом контексте.

Если определение обновлено до size (N a left right), то aявляется связанным выражением типа Int.