Вставка значения в упорядоченное дерево в Haskell - PullRequest
Новая
       15

Вставка значения в упорядоченное дерево в Haskell

5 голосов
/ 08 февраля 2010

В основном я определил тип данных Tree, который определяется следующим образом: 

data Tree a = Empty
| Leaf a
| Node (Tree a) a (Tree a)
deriving (Eq, Ord, Show)

Теперь мне нужно создать функцию для вставки значения в упорядоченное дерево (не нужно сортировать дерево, просто добавьте значение). Это то, что я придумал до сих пор: 

insert :: a -> Tree a -> Tree a
insert x Empty      = Leaf x
insert x (Leaf m)   | m < x     = Node (Leaf x) m Empty
                    | otherwise = Node Empty m (Leaf x)
insert x (Node l m r)   | x > m     = Node (Leaf l) m (insert x r)
                        | otherwise = Node (insert x l) m (Leaf r)

Однако, когда я запускаю это, я получаю следующее сообщение об ошибке:

Не удалось найти ожидаемый тип «а» (жесткая переменная) против предполагаемого типа "Дерево а" «a» связан подписью типа для «insert» в Main.hs: 11: 10 В первом аргументе «листа», а именно «я» В первом аргументе «Узел», а именно «(Лист l)» В выражении: Node (Leaf l) m (insert x r)

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

Ответы [ 3 ]

10 голосов
/ 08 февраля 2010

Ваша проблема в том, что 

insert x (Node l m r)   | x > m     = Node (Leaf l) m (insert x r)
                        | otherwise = Node (insert x l) m (Leaf r)

должно быть 

insert x (Node l m r)   | x > m     = Node l m (insert x r)
                        | otherwise = Node (insert x l) m r

потому что l и r уже являются деревьями.

9 голосов
/ 08 февраля 2010

Перевод примерно с type-checker-ese на английский:

Не удалось найти ожидаемый тип 'a' (a жесткая переменная)

Это означает, что он ожидал произвольный тип a, который также используется в другом месте (следовательно, "жесткий"), поэтому он не может просто взять любой старый тип.

против предполагаемого типа 'Tree a'

Это означает, что вместо этого он обнаружил Tree, содержащий элементы ожидаемого жесткого полиморфного типа. Это, очевидно, не имеет смысла, поэтому жалуется.

'a' связан подписью типа для 'insert' в Main.hs: 11: 10

Это просто говорит о том, что тип ограничен, потому что вы указали его в сигнатуре этого типа.

В первом аргументе «Leaf», а именно «l» В первом аргумент «Узел», а именно «(Лист l)» В выражении: Узел (Лист l) m (вставить x r)

Это просто говорит вам, на какой конкретный термин он жалуется, с некоторым контекстом.

Итак, чтобы разобраться: переменная l - это Tree a, используемая в контексте, который требует только a. В этом случае l, очевидно, имеет правильный тип, поэтому ошибка в том, как он используется. Почему средство проверки типов ищет тип a? Потому что вы применили к нему конструктор данных Tree. Но подождите, l уже Tree a! и вуаля , весы падают с наших глаз, и правда видна.

... который был всего лишь длинным способом объяснить, почему Эдвард Кметт * быстрый ответ является правильным и какие рассуждения можно использовать, чтобы прийти к такому ответу.

2 голосов
/ 08 февраля 2010

l - это первый параметр Node, поэтому он имеет тип Tree a (все левое поддерево). Leaf, с другой стороны, принимает в качестве параметра только одно значение, а не целое дерево. Поэтому Leaf l выдает ошибку типа, так как пытается создать лист из целого дерева. Возможно, вы просто хотели l вместо Leaf l в этом месте.

Кроме того, в чем разница между Leaf x и Node Empty x Empty? Вы уверены, что вам нужны оба конструктора?

...