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

Я разбираюсь в книгах 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, потому что я определил его в строках выше метода высоты. Но когда я пытаюсь загрузить файл, мне говорят, что конструктор данных не входит в объем. Я ценю вашу помощь и объяснение причины этой ошибки. Благодаря, Кевин

Ответы

Ответ 1

Изменить

height (Tree node left right)

к

height (Node node left right)

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

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

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

:t height

в ghci или hugs.

Ответ 2

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

  • Неправильная подпись типа Tree всегда Tree определенного типа - который вы назвали a в своем объявлении и который может быть любым типом (поскольку вы не ограничивали его). Поэтому heigth должен взять Tree некоторого типа - a 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 или максимум "height и т.д. До бесконечности. Вы должны увеличивать результат на каждом уровне;)

Ответ 3

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

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

height Empty = 0
height (Node _ l r) = 1 + max (height l) (height r)