haskell - index function for balanced binary tree -

i have problem, can't figure out how must decide sub-tree function indexj must choose @ each step walks through balanced binary tree - joinlist.

the idea cache size (number of data elements) of each sub-tree. can used @ each step determine if desired index in left or right branch.

i have code:

data joinlist m = empty                   | single m                   | 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) =  class sized   size :: -> size  instance sized size   size = id  instance monoid size   mempty  = size 0   mappend = (+) 

i write functions:

tag :: monoid m => joinlist m -> m tag empty = mempty tag (single x dt) = x tag (append x l_list r_list) = x  (+++) :: monoid m => joinlist m -> joinlist m -> joinlist m (+++) jl1 jl2 = append (mappend (tag jl1) (tag jl2)) jl1 jl2  indexj :: (sized b, monoid b) => int -> joinlist b -> maybe indexj _ empty = nothing indexj jl | < 0 || (i+1) > (sizejl jl) = nothing     sizejl = getsize . size . tag  indexj 0 (single m d) = d indexj 0 (append m (single sz1 dt1) jl2) = dt1 indexj (append m jl1 jl2) = if (sizejl jl1) >= (sizejl jl2)                                indexj (i-1) jl1                                 else indexj (i-1) jl2     sizejl = getsize . size . tag 

functions tag , (+++) working well, need finish indexj function, must return i-th element joinlist tree, = [0..n]

my function indexj working wrong =) if have empty tree - it's (size 0) if have single (size 1) "data" - it's (size 1) if have append (size 2) (single (size 1) 'k') (single (size 1) 'l') branch must choose? i-1 = 1 , have 2 branches 1 data element in each.

update: if needs take , drop functions joinlist's trees make it:

dropj :: (sized b, monoid b) => int -> joinlist b -> joinlist b 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                 s1 = getsize . size $ tag jl1  takej :: (sized b, monoid b) => int -> joinlist b -> joinlist b 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                 s1 = getsize . size $ tag jl1 

i suppose in

append m joinlist1 joinlist2 

the elements of joinlist1 meant take first indices, followed elements of joinlist2.

then, when indexing

indexj (append m jl1 jl2) 

you have compare i size of jl1 - let call s1. elements of jl1 occupy indices 0 s1 - 1, , elements of jl2 occupy indices s1 s1 + s2 - 1, hence

indexj :: (sized b, monoid b) => int -> joinlist b -> maybe indexj _ empty  = nothing indexj (single m d)     | == 0    = d     | otherwise = nothing indexj (append m jl1 jl2)     | < 0     = nothing     | >= getsize (size m) = nothing     -- optional, more efficient have     | < s1    = indexj jl1     | otherwise = indexj (i - s1) jl2               s1 = getsize . size $ tag jl1 

if index smaller s1, in first sublist, otherwise in second.