运算符比较和 Prelude.compare

Question

第 8 章 Programming in Haskell (2e) 定义了一个数据 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 章）要求用 Prelude.compare 和问题重新定义 occurs 和问题：

Why is this new definition more efficient than the original version?

这里给出我的定义：

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 更复杂，提升将是显着的。

谢谢n.m.。

运算符比较和 Prelude.compare

operator comparison and Prelude.compare

haskell

haskell-prelude