オペレータ比較Prelude.compare

Question

は Programming in Haskell (2e)の

第8章データを定義Treeとバイナリ検索機能occurs：

：（CHAP 8）

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 Prelude.compareと質問とoccursを再定義するように求められ

なぜこの新しい定義は元のバージョンより効率的ですか？ここで

私は私の定義を与える：

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 

は比較（オペレータ==と<）は、せいぜい二回（Tree-Node）y、xに適用される

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

に相当します。

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）と比較するために保存されているとして

。 Tree-nodeがOrderingよりも複雑になるよう

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

ブーストは注目すべきであろうが

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

：

は、最悪の場合のコストを検討してください。

ありがとうございます。n.m.です。