운영자 비교 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 

하는 y (Tree-Node)에서 가장 두 번, x에 적용 할 것

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

비교 (운영자 == 및 <)에 해당합니다. x의

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

비교에 관해서는

는 y (Tree-Node)을 한번 할 것이며, 그 결과는 EQ, LT 및 GT (Ordering)와 비교하는 저장됩니다. Tree-node이 Ordering보다 더 복잡 해짐에 따라 주목할만한 것

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

부스트

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

동안 :

는 최악의 경우 비용을 고려한다.

감사합니다. n.m.입니다.