检查二叉树是否有序的函数报错：无法解包Nothing

定义的代数数据类型 #

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 Empty Empty) = Just value
getTreeMaximum (Node value Empty right) = if value < fromJust (getTreeMinimum right) then (getTreeMaximum right) else Nothing
getTreeMaximum (Node value left Empty) = if fromJust (getTreeMaximum left) < value then Just value else Nothing
getTreeMaximum (Node value left right) = if fromJust (getTreeMaximum left) < value && value < fromJust (getTreeMinimum right) then getTreeMaximum right else Nothing

----
getTreeMinimum Empty = Nothing
getTreeMinimum (Node value Empty Empty) = Just value
getTreeMinimum (Node value Empty right) = if value < fromJust (getTreeMinimum right) then Just value else Nothing
getTreeMinimum (Node value left Empty) = if fromJust (getTreeMaximum left) < value then Just value else Nothing
getTreeMinimum (Node value left right) = if fromJust (getTreeMaximum left) < value && value < fromJust (getTreeMinimum right) then getTreeMinimum left else Nothing

isOrderedHelper :: Ord a => Tree a -> Bool
isOrderedHelper Empty = True

isOrderedHelper (Node value l Empty) = if not (isOrderedHelper l) then False else (fromJust (getTreeMaximum l)) < value

isOrderedHelper (Node value Empty r) = if not (isOrderedHelper r) then False else value < fromJust ((getTreeMinimum r))

isOrderedHelper (Node value l r) =
  if not (isOrderedHelper l) || not (isOrderedHelper r)
  then False 
  else fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r)

isOrdered :: Ord a => Tree a -> Bool
isOrdered Empty = True
isOrdered tree = isOrderedHelper tree

测试代码与异常 #

运行以下测试代码：

print (isOrdered (Node 1 (Node 0 Empty Empty) (Node 2 Empty Empty)))

抛出异常：

*** Exception: Cannot unpack Nothing.
CallStack (from HasCallStack):
  error, called at Main.hs:...

问题原因 #

核心问题出在isOrderedHelper的模式匹配逻辑：

• 叶子节点（Node value Empty Empty）没有单独的匹配分支，会被错误地匹配到(Node value l Empty)或(Node value Empty r)模式（取决于匹配顺序）。
• 以测试用例中的Node 2 Empty Empty为例，它会匹配(Node value l Empty)模式，此时l是Empty。代码会调用getTreeMaximum l，也就是getTreeMaximum Empty，返回Nothing，随后fromJust解包Nothing直接抛出异常。

此外，getTreeMaximum和getTreeMinimum的设计本身存在风险：它们仅在树有序时返回Just值，否则返回Nothing，但isOrderedHelper调用时默认它们一定返回Just，完全没处理Nothing的情况，进一步放大了崩溃概率。

修复方案 #

方案1：修复现有逻辑的模式匹配 #

给isOrderedHelper添加叶子节点的匹配分支，放在其他Node模式之前：

isOrderedHelper :: Ord a => Tree a -> Bool
isOrderedHelper Empty = True
-- 新增叶子节点匹配
isOrderedHelper (Node _ Empty Empty) = True
isOrderedHelper (Node value l Empty) = if not (isOrderedHelper l) then False else (fromJust (getTreeMaximum l)) < value
isOrderedHelper (Node value Empty r) = if not (isOrderedHelper r) then False else value < fromJust ((getTreeMinimum r))
isOrderedHelper (Node value l r) =
  if not (isOrderedHelper l) || not (isOrderedHelper r)
  then False 
  else fromJust (getTreeMaximum l) < value && value < fromJust (getTreeMinimum r)

但这种方案仍未解决getTreeMaximum/getTreeMinimum可能返回Nothing的问题，若树无序，依然会触发异常。

方案2：重构为更安全的上下界遍历实现 #

放弃依赖getTreeMaximum/getTreeMinimum，改用传递上下界的方式实现，全程避免fromJust的风险：

isOrdered :: Ord a => Tree a -> Bool
isOrdered = isOrdered' Nothing Nothing
  where
    isOrdered' :: Ord a => Maybe a -> Maybe a -> Tree a -> Bool
    isOrdered' _ _ Empty = True
    isOrdered' minBound maxBound (Node val left right) =
      -- 检查当前节点值是否在上下界范围内
      (case minBound of
         Nothing -> True
         Just m -> m < val) &&
      (case maxBound of
         Nothing -> True
         Just m -> val < m) &&
      -- 左子树的上界是当前节点值，下界不变
      isOrdered' minBound (Just val) left &&
      -- 右子树的下界是当前节点值，上界不变
      isOrdered' (Just val) maxBound right

这种实现不仅避免了异常，逻辑更清晰，时间复杂度也从O(n²)优化到O(n)（原方案中每个节点都要遍历子树找最值）。

内容的提问来源于stack exchange，提问作者coderodde