我正在嘗試使用函子的固定點來實作二叉搜索樹（或集合）。我將我的固定點定義如下：
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)
二叉樹的傳統好處是能夠通過選擇是在左子樹還是右子樹中進一步搜索來減少搜索時間，如下所示（在偽代碼中）：
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)。有沒有辦法使用遞回方案選擇性地遞回以節省時間復雜度？我在想這個錯誤的方式嗎？
uj5u.com熱心網友回復：
因為懶惰，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
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/517162.html
上一篇：保留演算法不正常
下一篇：計算字串中的出現次數