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

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

ОБНОВЛЕНИЕ: если кому-то нужны функции take and drop для деревьев 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

haskell binary-tree monoids
person Сергей Кузминский    schedule 10.05.2013    source источник

Ответы (2)


arrow_upward
6
arrow_downward

я полагаю в

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, ищем в первом подсписке, иначе во втором.

person Daniel Fischer    schedule 10.05.2013
comment
Спасибо! Ваша версия работает правильно. Я тестирую его на своих JoinList с 1,2,3,4 и 8 элементами данных =) - person Сергей Кузминский; 11.05.2013

arrow_upward
1
arrow_downward

Обычно вы должны кодировать позицию в древовидной структуре последовательностями чисел, а не только одним числом. Например (при условии, что индексы начинаются с 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

Это сделало бы реализацию индексной функции намного проще.

person chris    schedule 10.05.2013