有选择地使用变态(或任何递归方案)将二叉树的左或右子树进行递归。

Question

我试图使用函子的不动点来实现二进制搜索树(或set)。我将我的定点定义如下：

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 

为了制作二叉树，我使用了一棵红黑树，如下所示：

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) 

二叉树的传统优点是能够通过选择在左或右子树中进行进一步搜索来缩短搜索时间(在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

如果要搜索的元素小于当前元素，则函数member将左转，如果相反为真，则向右。因此，它改进了O(logn)的搜索时间。

然而，在递归格式中，代数被递归地应用于整个数据结构。我在这里写了一个member代数：

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

但它似乎是O(nlogn)而不是O(logn)。有没有办法有选择地使用递归方案来节省时间复杂度？我是不是想错了？

Answer 1

因为懒惰，left和right只有在你要求的时候才会被评估。因此，只需将当前节点与正在搜索的值进行比较，以确定要进入哪个子树：

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