Selectively recurse into left or right subtree of a binary tree using a catamorphism (or any recursi-CodePudding

I'm trying to implement a binary search tree (or set) using fixed points of functors. I've defined my fixed point as follows:

newtype Fix f = In (f (Fix f))

out :: Fix f -> f (Fix f)    
out (In f) = f    
    
-- Catamorphism    
type Algebra f a = f a -> a    
    
cata :: (Functor f) => Algebra f a -> Fix f -> a    
cata f = f . fmap (cata f) . out

To make the binary tree, I'm using a red-black tree like so:

data NodeColor = Red | Black deriving (Eq, Show)    
    
data RedBlackTreeF a r = EmptyRedBlackTreeF | RedBlackTreeNodeF NodeColor r a r deriving (Eq, Show)
    
instance Functor (RedBlackTreeF a) where                                             
        fmap _ EmptyRedBlackTreeF = EmptyRedBlackTreeF                               
        fmap f (RedBlackTreeNodeF color r1 a r2) =                                   
                RedBlackTreeNodeF color (f r1) a (f r2)                              
                                                                                     
type RedBlackTreeF' a = Fix (RedBlackTreeF a)

The traditional benefit of a binary tree is being able to cut down search time by choosing whether to search further in the left or right subtree like so (in psuedocode):

fun member (x, E) = false
   | member (x, T (_, a, y, b)) =
     if x < y then member (x, a)
     else if x > y then member (x, b)
     else true

The function member will go left if the element that is being searched for is less than the current element and right if the opposite is true. It therefore improves search time to O(logn).

However, in a recursion scheme, the algebra is recursively applied to the entire data structure. I've written an member algebra here:

memberPAlg :: Ord a => a -> RedBlackTreeF a Bool -> Bool    
memberPAlg _ EmptyRedBlackTreeF = False    
memberPAlg elem (RedBlackTreeNodeF _ left cur right) =    
        (elem == cur) || (left || right)

But it seems to be O(nlogn) rather than O(logn). Is there any way to selectively recurse using a recursion scheme to save time complexity? Am I thinking about this the wrong way?

CodePudding user response：

Because of laziness, left and right are evaluated only if you ask for them. So, just compare the current node with the value being searched for to decide which subtree to go into:

memberPAlg :: Ord a => a -> RedBlackTreeF a Bool -> Bool    
memberPAlg _ EmptyRedBlackTreeF = False    
memberPAlg elem (RedBlackTreeNodeF _ left cur right) =    
   case compare elem cur of
     EQ -> True
     LT -> left
     GT -> right