我有問題,我不知道如何決定我的函數indexJ
必須在每個步驟中選擇什麼子樹遍歷我的平衡二叉樹 - JoinList
。平衡二叉樹的索引函數
這個想法是給緩存每個子樹的大小(數據元素的數量)。然後可以在每個步驟中使用它來確定所需的索引是在左邊還是右邊。
我有這樣的代碼:
data JoinList m a = Empty
| Single m a
| Append m (JoinList m a) (JoinList m a)
deriving (Eq, Show)
newtype Size = Size Int
deriving (Eq, Ord, Show, Num)
getSize :: Size -> Int
getSize (Size i) = i
class Sized a where
size :: a -> Size
instance Sized Size where
size = id
instance Monoid Size where
mempty = Size 0
mappend = (+)
我寫功能:
tag :: Monoid m => JoinList m a -> m
tag Empty = mempty
tag (Single x dt) = x
tag (Append x l_list r_list) = x
(+++) :: Monoid m => JoinList m a -> JoinList m a -> JoinList m a
(+++) jl1 jl2 = Append (mappend (tag jl1) (tag jl2)) jl1 jl2
indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a
indexJ _ Empty = Nothing
indexJ i jl | i < 0 || (i+1) > (sizeJl jl) = Nothing
where sizeJl = getSize . size . tag
indexJ 0 (Single m d) = Just d
indexJ 0 (Append m (Single sz1 dt1) jl2) = Just dt1
indexJ i (Append m jl1 jl2) = if (sizeJl jl1) >= (sizeJl jl2)
then indexJ (i-1) jl1
else indexJ (i-1) jl2
where sizeJl = getSize . size . tag
功能tag
和(+++)
運作良好,但我需要完成indexJ
功能,它必須返回從第i個元素我的JoinList樹,i = [0..n]
我的功能indexJ
working wrong =) 如果我有空樹 - 它是(大小0) 如果我有單一(大小1)「數據」 - 它的(大小1) 但如果我有附加(大小2)(單(大小1)'k ')(單(1)'''')我必須選擇哪個分支? i-1 = 1,我有兩個分支,每個分支有1個數據元素。
UPDATE:如果有人需要採取抗摔功能JoinList的樹木 我讓它:
dropJ :: (Sized b, Monoid b) => Int -> JoinList b a -> JoinList b a
dropJ _ Empty = Empty
dropJ n jl | n <= 0 = jl
dropJ n jl | n >= (getSize . size $ tag jl) = Empty
dropJ n (Append m jL1 jL2)
| n == s1 = jL2
| n < s1 = (dropJ n jL1) +++ jL2
| otherwise = dropJ (n - s1) jL2
where s1 = getSize . size $ tag jL1
takeJ :: (Sized b, Monoid b) => Int -> JoinList b a -> JoinList b a
takeJ _ Empty = Empty
takeJ n jl | n <= 0 = Empty
takeJ n jl | n >= (getSize . size $ tag jl) = jl
takeJ n (Append m jL1 jL2)
| n == s1 = jL1
| n < s1 = (takeJ n jL1)
| otherwise = jL1 +++ takeJ (n - s1) jL2
where s1 = getSize . size $ tag jL1
謝謝!您的版本正常工作。我使用1,2,3,4和8個數據元素在JoinLists上測試它=) – 2013-05-11 13:28:21