Haskell二叉搜索树检查函数模式匹配告警问题求助

问题背景 #

我们定义了如下二叉树结构：

data BB a = L | K a (BB a) (BB a) deriving Show

示例二叉搜索树：

baumA = K 5 (K 3 (K 1 L L) L) (K 7 L (K 12 (K 9 L L) L))

编写的判断二叉搜索树的函数及辅助函数代码如下：

isBinarySearchTree :: Ord a => BB a -> Bool
isBinarySearchTree (K initial l r) = hilf l initial 0 && hilf r initial 1 
-- "0" means left side and "1" means right side


hilf L _ _ = True -- neutral case

hilf (K w l r) acc 0                                
    | w < acc && hilf l w 0 && hilf r w 1 = True
    | otherwise = False

hilf (K w L L) acc 0
    | w < acc  = True
    | otherwise = False

hilf (K w l r) acc 1
    | w > acc && hilf l w 0 && hilf r w 1 = True
    | otherwise = False

hilf (K w L L) acc 1
    | w > acc  = True
    | otherwise = False

运行代码时出现两处模式匹配告警：

• Pattern match has inaccessible right hand side In an equation for hilf': hilf (K w L L) acc 0 = ...`
• Pattern match is redundant In an equation for hilf': hilf (K w L L) acc 1 = ...`

告警原因解析 #

第一个告警：hilf (K w L L) acc 0 模式不可达 #

Haskell的模式匹配遵循从上到下依次尝试匹配的规则。在辅助函数hilf中，当第三个参数为0时，先定义的hilf (K w l r) acc 0模式可以匹配任意带有左右子树的K节点，自然也包含了左右子树均为L的叶子节点K w L L。

当程序处理K w L L且第三个参数为0的调用时，会优先匹配上方的通用K节点模式，永远不会走到下方的叶子节点专用模式，导致该模式的右侧代码永远无法执行，因此编译器提示“模式匹配的右侧不可达”。

第二个告警：hilf (K w L L) acc 1 模式冗余 #

逻辑与第一个告警完全一致：当第三个参数为1时，先定义的hilf (K w l r) acc 1模式已经覆盖了所有K节点的情况（包括叶子节点K w L L）。后续的叶子节点专用模式永远不会被匹配到，属于多余的代码，因此编译器提示“模式匹配冗余”。

额外优化提示 #

这两个叶子节点专用模式完全没必要保留——通用K节点模式已经包含了叶子节点的情况，且通用模式中的hilf l w 0 && hilf r w 1逻辑，在l=L和r=L时会触发hilf L _ _ = True的匹配，最终效果和叶子节点专用模式完全一致。直接删除这两个冗余模式，代码即可正常运行且无告警。

内容的提问来源于stack exchange，提问作者AJ.beProgramming