Начало Haskell - получение ошибки «не в области: конструктор данных»

17

Я разбираюсь в книгах Haskell O'Reilly. Проблема, над которой я работаю, -

Using the binary tree type that we defined earlier in this chapter, 
write a function that will determine the height of the tree. The height 
is the largest number of hops from the root to an Empty. For example, the 
tree Empty has height zero; Node "x" Empty Empty has height one; 
Node "x" Empty (Node "y" Empty Empty) has height two; and so on.

Я пишу свой код в файле ch3.hs. Вот мой код:

36 data Tree a = Node a (Tree a) (Tree a)
37             | Empty
38               deriving (Show)
39
40 --problem 9:Determine the height of a tree
41 height :: Tree -> Int
42 height (Tree node left right) = if (left == Empty && right == Empty) then 0 else max (height left) (height right) 

открытие ghci в терминале и ввод: load ch3.hs. Когда я это сделаю, я получаю следующую ошибку:

Prelude> :load ch3.hs
[1 of 1] Compiling Main             ( ch3.hs, interpreted )

ch3.hs:42:7: Not in scope: data constructor 'Tree'
Failed, modules loaded: none.

Я ожидаю, что там должен быть конструктор данных Tree, потому что я определил его в строках выше метода высоты. Но когда я пытаюсь загрузить файл, мне говорят, что конструктор данных не входит в объем. Я ценю вашу помощь и объяснение причины этой ошибки. Благодаря, Кевин

    
задан Kevin Burke 28.08.2010 в 21:56
источник

3 ответа

21

Изменить

height (Tree node left right) 

к

height (Node node left right)

Это означает, что соответствие шаблонов работает над конструкторами типа алгебраических данных (ADT). Tree не является конструктором, это имя ADT.

Btw, вы должны прокомментировать объявление подписи функции для компиляции кода, поскольку оно содержит ошибку.

Затем вы можете проверить тип вывода с помощью

:t height

в ghci или объятиями .     

ответ дан maxschlepzig 28.08.2010 в 22:03
источник
  • Спасибо, это сработало. Я до сих пор не совсем понимаю, что происходит, и теперь получаю ошибки во время выполнения, но будет продолжать смотреть, думать и отлаживать. –  Kevin Burke 28.08.2010 в 22:17
  • Другим примером может быть проще понять. Давайте притворимся, что мы работаем с целыми числами, а не с деревьями. Int - это имя целочисленного типа. Вы не можете добавить «Int + Int», потому что Int - это имя типа, а не конструктор, который возвращает значение этого типа. Такие вещи, как 0, 1, 2, ... являются конструкторами, и если вы хотите работать с целыми числами, вот как вы их используете в своей программе. Применив это к вашему случаю, Tree - это имя типа, а Node (или Empty) - это то, как вы получаете значение этого типа. –  jrockway 29.08.2010 в 03:44
  • В HaskellWiki также есть полезный раздел, и он даже использует Tree в качестве примера: haskell.org/haskellwiki/Constructor –  jrockway 29.08.2010 в 03:45
  • @KevinBurke Другим способом думать об этом является «data Bool = True | Ложь'. Импортирование только True или False было бы бессмысленным. Сам Bool необходимо импортировать, чтобы разрешить доступ как к True, так и к False. –  Carcigenicate 11.07.2014 в 02:49
6

Ваш код неверен, на нескольких уровнях. Похоже, вы неправильно поняли типы алгебраических данных.

  • Подпись типа неверна, Tree всегда является Tree определенного типа, который вы назвали a в своем объявлении, и который может быть любым типом (поскольку вы не ограничивали его). Таким образом, heigth должно принять Tree некоторого типа - Tree SomeType . Вы можете и должны использовать наиболее общий тип для SomeType , т. Е. Переменную типа, например a .
  • При сопоставлении шаблонов вы указываете конкретный конструктор - Node a (Tree a) (Tree a) или Empty - для сопоставления, а не против типа в целом. Таким образом, height (Node ...) будет соответствовать Node , height (Empty) будет соответствовать Empty , а height (Tree ...) будет пытаться сопоставить конструктор с именем Tree , но его нет. Это сообщение об ошибке, которое вы получаете.
  • Никогда не сравнивайте (через == ) с конструктором. Это будет работать, если вы написали deriving (Show, Eq) . Но вы должны использовать сопоставление образцов, чтобы определить, достигли ли вы Empty
  • Что приводит к: вы используете только Node , а не Empty - вы должны добавить предложение для Empty .
  • Кроме того, ваша функция по-прежнему возвращает 0 для всех входов, если вы исправите все вышеперечисленные проблемы. Вы никогда не возвращаете ничего, кроме 0 или максимум% s_de% детей. В свою очередь, они могут возвращать только 0 или максимум их% s %_ %_% и т. Д. Ad infinitum. Вы должны увеличивать результат на каждом уровне;)
ответ дан user395760 28.08.2010 в 22:34
источник
  • Спасибо за помощь. Я только что начал немного назад и до сих пор привык к новому языку. –  Kevin Burke 28.08.2010 в 22:49
2

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

Это гораздо более прямолинейно, и , прежде всего, исправить:

height Empty = 0
height (Node _ l r) = 1 + max (height l) (height r)
    
ответ дан Dario 28.08.2010 в 22:18
источник
  • -1 Это неправильно. Тест с высотой (Node 1 (Node 2 Empty Empty) (Узел 3 Empty Empty)). Должно быть 2, равно 0 - это 0 для любого ввода, из-за той же ошибки, что и у OP. –  28.08.2010 в 22:36
  • Спасибо. Я все еще пытаюсь привыкнуть к сопоставлению шаблонов. Я правильно ответил на другой ответ, потому что вопрос касался конструктора данных, но это также полезно. –  Kevin Burke 28.08.2010 в 22:48
  • Исправлено - нужно добавить 1 к значению max (высота слева) (высота справа), чтобы он не продолжал возвращать 0. –  Kevin Burke 28.08.2010 в 22:54
  • Извините, конечно, нам нужен + 1. –  Dario 29.08.2010 в 10:46