Функция индекса для сбалансированного двоичного дерева

Question

У меня проблема, я не могу понять, как я должен решить, какое поддерево моя функция 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 не работает =) Если у меня пустое дерево - это (размер 0) , если у меня есть один (размер 1) «данные» - это (размер 1) , но как насчет того, если у меня есть Append (размер 2) (Single (Size 1) 'k ') (Single (размер 1)' l '), какую ветку я должен выбрать? i-1 = 1 и i имеют две ветви с 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 

Answer 1

Я полагаю, в

Append m joinList1 joinList2 

элементы joinList1 призваны занять первые показатели, за которыми следуют элементы joinList2.

Затем при индексировании

indexJ i (Append m jL1 jL2) 

вы должны сравнить i с размером jL1 - назовем это s1. Тогда элементы jL1 занимают индексы от 0 до s1 - 1, а элементы jL2 занимают индексы от s1 до s1 + s2 - 1, следовательно

indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a 
indexJ _ Empty = Nothing 
indexJ i (Single m d) 
    | i == 0 = Just d 
    | otherwise = Nothing 
indexJ i (Append m jL1 jL2) 
    | i < 0  = Nothing 
    | i >= getSize (size m) = Nothing  -- optional, more efficient to have it 
    | i < s1 = indexJ i jL1 
    | otherwise = indexJ (i - s1) jL2 
     where 
     s1 = getSize . size $ tag jL1 

, если индекс меньше s1, мы смотрим в первую подсписка, в противном случае в второй.

Answer 2

Обычно вы закодировать позицию в виде древовидной структуры с помощью последовательности чисел, а не только отдельных номер. Например (если индексы начинаются с 0):

[] -- empty sequence = root of tree 
[0,1] -- first follow the first child, then the second child 
[0,0,0] -- go 3 levels down in the leftmost branch 

Это значительно упростит реализацию функции индекса.