index fonction pour arbre binaire équilibrée

Question

J'ai un problème, je ne peux pas comprendre comment je dois décider quel sous-arbre ma fonction indexJ doit choisir à chaque étape marche à travers mon arbre binaire équilibré - JoinList.

L'idée est de mettre en cache la taille (nombre d'éléments de données) de chaque sous-arbre. Cela peut ensuite être utilisé à chaque étape pour déterminer si l'index souhaité est dans la branche gauche ou droite.

J'ai ce code:

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 = (+) 

i écrire des fonctions:

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 

fonctions de travail bien tag et (+++), mais je dois terminer indexJ fonction, qui doit retourner l'élément i-ième de mon arbre JoinList, i = [0..n]

ma fonction indexJ fonctionne mal =) si j'ai l'arbre vide - c'est (taille 0) si j'ai Single (taille 1) "données" - c'est (taille 1) mais qu'en est-il si j'ai Append (Taille 2) (Single (Size 1) 'k ') (Simple (Taille 1)' l ') quelle branche je dois choisir? i-1 = 1 et j'ai deux branches avec 1 élément de données dans chacune.

MISE À JOUR: si quelqu'un a besoin de prendre et les fonctions de chute pour les arbres de JoinList je le fais:

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

Je suppose que dans

Append m joinList1 joinList2 

les éléments de joinList1 sont destinés à prendre les premiers indices, suivis par les éléments de joinList2.

Ensuite, lors de l'indexation

indexJ i (Append m jL1 jL2) 

vous devez comparer i à la taille de jL1 - Appelons que s1. Ensuite, les éléments de jL1 occupent les indices 0-s1 - 1, et les éléments de jL2 occupent les indices de s1 à s1 + s2 - 1, d'où

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 

si l'indice est inférieur à s1, nous regardons dans la première sous-liste, sinon la deuxième.

Answer 2

En général, vous encoderait la position dans une structure arborescente par des séquences de nombres, et pas seulement un seul nombre. Par exemple (en supposant que les indices commencent à 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 

qui rendrait la mise en œuvre d'une fonction d'index beaucoup plus simple.