2

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

但我看不到效率的提高。有没有？

我是不是学错了？

4

1 回答 1

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

Boost 将值得注意，因为它Tree-node变得比Ordering.

谢谢纳米。_

于 2016-10-29T07:19:10.147 回答