我有以下代数数据类型：
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.我有两个问题（第二个是可选的）：
1.如何修复编译时错误？
1.是否有可能提高所讨论的功能的效率？
2条答案
按热度按时间uqcuzwp81#
由于
if是Haskell中的一个表达式，因此每个if都必须有一个then和一个else，但这有7个
if和7个then，但只有4个else我可能会使用模式匹配来避免这种深度嵌套的
if树：但是我认为除了
getTreeMaximum Empty之外的子句根本没有任何理由返回Nothing，因为总是有一个value，所以你必须调整这些。vcudknz32#
一个效率小贴士：你不需要计算最大值和最小值来检查树是否排序。您可以更直接地检查它，如下所示。
定义一个函数
sortedAndWithin tree lowerBound upperBound，它检查tree是否已排序，以及它的所有值是否在边界之间。叶子的处理很简单：它们总是被分类的。
相反，
Node value left right被排序并且在边界内，当且仅当：left子树在 * 新 * 边界内…然后...right子树在 * 新 * 边界内…然后...这个递归在整个树上进行一次遍历。
最初，您希望将边界设置为“-无穷大”和“+无穷大”。在Haskell中有几种方法可以实现这一点。一个次优但仍然有效的方法是找到树的最小值和树的最大值，并将其用作起始边界。注意，以这种方式，算法仅计算一次最小值/最大值，而不是在每个递归步骤中都这样做。