Исправление функции, проверяющей, упорядочено ли входное бинарное дерево
У меня есть следующий алгебраический тип данных:
data Tree a = Empty | Node a (Tree a) (Tree a)
deriving (Show, Eq)
Кроме того, у меня есть этот фрагмент кода:
fromJust :: Maybe a -> a
fromJust (Just val) = val
fromJust Nothing = error "Cannot unpack Nothing."
getTreeMinimum :: Ord a => Tree a -> Maybe a
getTreeMaximum :: Ord a => Tree a -> Maybe a
getTreeMaximum Empty = Nothing
getTreeMaximum (Node value l r) =
if l == Empty && r == Empty then Just value else
if l == Empty && r /= Empty then if value < fromJust (getTreeMinimum r) then (getTreeMaximum r) else
if l /= Empty && r == Empty then if fromJust (getTreeMaximum l) < value then Just (value) else
if l /= Empty && r /= Empty then if fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r) then (getTreeMaximum r) else Nothing
getTreeMinimum Empty = Nothing
getTreeMinimum (Node value l r) =
if l == Empty && r == Empty then Just value else
if l == Empty && r /= Empty then if value < fromJust (getTreeMinimum r) then Just (value) else
if l /= Empty && r == Empty then if fromJust (getTreeMaximum l) < value then (getTreeMinimum l)
if l /= Empty && r /= Empty then if fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r) then (getTreeMinimum l) else Nothing
isOrderedHelper :: Ord a => Tree a -> Bool
isOrderedHelper Empty = True
isOrderedHelper (Node nodeValue leftChild Empty) = if isOrderedHelper leftChild == False then False else (fromJust (getTreeMaximum leftChild)) < nodeValue
isOrderedHelper (Node nodeValue Empty rightChild) = if isOrderedHelper rightChild == False then False else nodeValue < fromJust ((getTreeMinimum rightChild))
isOrderedHelper (Node nodeValue leftChild rightChild) =
if isOrderedHelper leftChild == False || isOrderedHelper rightChild == False
then False
else fromJust (getTreeMaximum leftChild) < nodeValue && nodeValue < fromJust (getTreeMinimum rightChild)
isOrdered :: Ord a => Tree a -> Bool
isOrdered Empty = True
isOrdered tree = isOrderedHelper tree
Вышеупомянутое дает мне:
error: parse error on input 'getTreeMinimum'
getTreeMinimum Empty = Nothing
^^^^^^^^^^^^^^
Failed, no modules loaded.
У меня два вопроса (второй по желанию):
- Как исправить ошибку времени компиляции?
- Можно ли повысить эффективность рассматриваемой функции?
@cafce25 Готово. Проверьте это.
Я думаю, что вам не хватает нескольких else в if l /= Empty && r /= Empty then if fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r) then (getTreeMaximum r) else Nothing
Обратите внимание, что в языках программирования очень распространено, когда компилятор сигнализирует о синтаксической ошибке в строке, что ваша фактическая ошибка была в строке до этого. Здесь ваша ошибка — недостающие elses; компилятор замечает ошибку только тогда, когда встречает следующую строку, ожидая, что она начинается с else, и замечает, что она не начинается с else.
Примечания: e == False то же, что и not e; if not e1 then False else e2 то же, что и e1 && e2; if e1 then False else e2 то же, что и (not e1) && e2; if not e1 || not e2 then False else e3 && e4 то же, что e1 && e2 && e3 && e4.
Ответы 2
Поскольку if является выражением в Haskell, каждое if должно иметь ровно одно then и одно else, но это
getTreeMaximum (Node value l r) =
if l == Empty && r == Empty then Just value else
if l == Empty && r /= Empty then if value < fromJust (getTreeMinimum r) then (getTreeMaximum r) else
if l /= Empty && r == Empty then if fromJust (getTreeMaximum l) < value then Just (value) else
if l /= Empty && r /= Empty then if fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r) then (getTreeMaximum r) else Nothing
имеет 7 if и 7 then
но только 4 else
Я бы, наверное, написал, что использование сопоставления с образцом позволяет избежать такого глубоко вложенного дерева if:
getTreeMaximum (Node value Empty Empty) = Just value
getTreeMaximum (Node value Empty r) = if value < fromJust (getTreeMinimum r) then (getTreeMaximum r) else Nothing
getTreeMaximum (Node value l Empty) = if fromJust (getTreeMaximum l) < value then Just (value) else Nothing
getTreeMaximum (Node value l r) = if fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r) then (getTreeMaximum r) else Nothing
Но я не думаю, что у предложений, кроме getTreeMaximum Empty, есть какие-либо причины для возврата Nothing, поскольку всегда есть value, поэтому вам придется их настроить.
Совет по эффективности: вам не нужно вычислять максимум и минимум, чтобы проверить, отсортировано ли дерево. Вы можете более непосредственно проверить это следующим образом.
Определите функцию sortedAndWithin tree lowerBound upperBound, которая проверяет, что tree отсортировано и что все его значения находятся между границами.
С листьями несложно обращаться: они всегда отсортированы.
Вместо этого Node value left right сортируется и находится в границах, если и только если:
- значение находится в пределах
- поддерево
leftнаходится в новых границах... и... - поддерево
rightнаходится в новых границах... и...
Эта рекурсия делает один проход по всему дереву.
Первоначально вы хотите установить границы на «-бесконечность» и «+ бесконечность». Есть несколько способов добиться этого в Haskell. Неоптимальный, но все же работающий метод состоит в том, чтобы найти минимум дерева и максимум дерева и использовать их в качестве начальных границ. Обратите внимание, что таким образом алгоритм вычисляет минимум/максимум только один раз, а не на каждом шаге рекурсии.
@cafce25 Конечно. Минутку, пожалуйста.