Searching a Join List for an index Attempt #2 Originally I posted this incorrect attempt - Searching a Join List for an index.

Given a JoinList:

data JoinList m a = Empty
                  | Single m a
                  | Append m (JoinList m a) (JoinList m a)
    deriving (Eq, Show)


where m represents the size of the JoinList, find the element (Maybe a) at the given index in the JoinList structure.

indexJ :: (Sized b, Monoid b) =&gt; Int -&gt; JoinList b a -&gt; Maybe a
indexJ _ Empty             = Nothing
indexJ i (Single _ x) 
  | i == 0                 = Just x
  | otherwise              = Nothing
indexJ i (Append _ left right)
  | leftHt &gt; i             = indexJ i left
  | (rightHt + leftHt) &gt; i = indexJ (i-leftHt) right
  | otherwise              = Nothing
  where leftHt  = (getSize. size . tag) left
        rightHt = (getSize. size . tag) right


where tag = 

tag :: Monoid m =&gt; JoinList m a -&gt; m
tag Empty          = mempty
tag (Single x _)   = x
tag (Append x _ _) = x 


Testing

Data

jlIndex2 :: JoinList Size String
jlIndex2 = Append (Size 3) 
                       (Single (Size 1) "foo") 
                       (Append (Size 2) 
                             (Single (Size 1) "bar") 
                             (Single (Size 1) "baz"))

jlIndex3 :: JoinList Size String
jlIndex3 = Append (Size 4) (Single 1 "biz") jlIndex2


Tests

*JoinList&gt; indexJ 3 jlIndex3
Just "baz"
*JoinList&gt; indexJ 0 jlIndex3
Just "biz"
*JoinList&gt; indexJ 100 jlIndex3
Nothing


Note - I would've used QuickCheck, but I'm not sure how to use it with algebraic data types.
Your code is completely fine, although the suffix Ht for the sublist sizes is a little bit strange.

For the tests you can use

genJoinList :: Arbitrary a =&gt; Int -&gt; Gen (JoinList Size a)
genJoinList 0 = pure Empty
genJoinList 1 = Single (Size 1) &lt;$&gt; arbitrary
genJoinList n = do
  left &lt;- choose (0, n)
  Append (Size n) &lt;$&gt; (genJoinList left) &lt;*&gt; (genJoinList (n - left))

toList :: JoinList b a -&gt; [a]
toList Empty          = []
toList (Single _ x)   = [x]
toList (Append _ l r) = toList l ++ toList r


You can now check whether indexJ n js returns the same value as toList js !! n:

prop_index :: (Eq a, Sized m, Monoid m) =&gt; Int -&gt; JoinList m a -&gt; Bool
prop_index n js = indexJ n js == indexI n (toList js)
  where
    indexI n xs = lookup n $ zip [0..] xs

main = quickCheck $ \n -&gt; forAll (sized genJoinList) $ \js -&gt; prop_index n js


An Arbitrary instance would need FlexibleInstances by the way.