Оператор сравнения и Prelude.compare

Question

Глава 8 Программирование на 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) просит переопределить 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,

Спасибо, n.m..