Searching a Join List for an index Attempt #2
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.