No title

Anonymous Coward 2018-03-04 06:14:04.541669 UTC

1{-
2data Ordering = LT | EQ | GT
3together with a function
4compare :: Ord a => a -> a -> Ordering
5that decides if one value in an ordered type is less than ( LT ), equal to ( EQ ), or greater than ( GT ) another value. Using this function, redefine the function
6occurs :: Ord a => a -> Tree a -> Bool for search trees. Why is this new definition more
7efficient than the original version?
8-}
9
10data Tree a = Leaf a | Node (Tree a) a (Tree a)
11
12-- Old definition
13occurs :: Ord a => a -> Tree a -> Bool
14occurs x (Leaf y) = x == y
15occurs x (Node l y r) | x == y = True
16 | x < y = occurs x l
17 | otherwise = occurs x r
18
19
20-- This version is more efficient becauseit only requires on comparison between x and y for each node, whereas the previous version may require two
21occurs2 x (Leaf y) = x == y
22occurs2 x (Node l y r) = case compare x y of
23 LT -> occurs x l
24 EQ -> True
25 GT -> occurs x r