Haskell - need to improve this find el function for a bst to d 1 complexity-CodePudding

data Tree a = Empty | Node (Tree a) a (Tree a) 

naive_find :: (Ord a) => (Tree a) -> a -> Bool
naive_find Empty _ = False
naive_find (Node t1 v t2) x 
    | x == v = True 
    | x  < v = naive_find t1 x 
    | x  > v = naive_find t2 x

thats a snippet of my current bst code, od course there are other functions but i dont think its necessary for the question. i need to reduce the above 2d complexity to d 1 but wont i always need those above comparisons to get through the search tree at minimum? Thanks. Any help appreciated

CodePudding user response：

Use compare. It's part of Data.Ord

naive_find (Node t1 v t2) x = case compare v x of
    LT -> naive_find t1 x
    EQ -> True
    GT -> naive_find t2 x

CodePudding user response：

You don't need the > comparison because at that point you already know that it will succeed, so you can just use otherwise:

data Tree a = Empty | Node (Tree a) a (Tree a) 

naive_find :: (Ord a) => Tree a -> a -> Bool
naive_find Empty _ = False
naive_find (Node t1 v t2) x 
    | x == v    = True 
    | x  < v    = naive_find t1 x 
    | otherwise = naive_find t2 x