算子比较与Prelude.compare

Question

Haskell编程(2e)的第8章定义了数据Tree和二进制搜索函数occurs。

data Tree a = Leaf a | Node (Tree a) a (Tree a)

occurs :: Ord a => a -> Tree a -> Bool
occurs x (Leaf y)                 = x == y
occurs x (Node l y r) | x == y    = True
                      | x < y     = occurs x l
                      | otherwise = occurs x r

练习3(第8章)要求用occurs重新定义Prelude.compare，并提出以下问题：

为什么这个新定义比原来的定义更有效？

在这里，我给出我的定义：

occurs :: Ord a => a -> Tree a -> Bool
occurs x (Leaf y)     = x == y
occurs x (Node l y r) = case compare x y of EQ -> True
                                            LT -> occurs x l
                                            GT -> occurs x r

但我看不出提高效率。有吗？

我是不是学错了？

Answer 1

事实证明很简单：

occurs x (Node l y r) | x == y    = True
                      | x < y     = occurs x l
                      | otherwise = occurs x r

等于

occurs x (Node l y r) = if x == y
                            then True
                            else if x < y
                                then occurs x l
                                else occurs x r

比较(操作符==和<)最多可用于x、y (Tree-Node)两次。

至于

occurs x (Node l y r) = case compare x y of EQ -> True
                                            LT -> occurs x l
                                            GT -> occurs x r

将x、y (Tree-Node)进行一次比较，并保存结果与EQ、LT和GT (Ordering)进行比较。

考虑更坏情况的费用：

operator-comparison = cost(compare(Tree-node)) * 2

而

Prelude.compare = cost(compare(Tree-node)) + cost(compare(Ordering))*2

随着Tree-node变得比Ordering更加复杂，Boost将是值得注意的。

谢谢n.m.。