Searching a Join List for an index Attempt #2

Question

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) => Int -> JoinList b a -> Maybe a
indexJ _ Empty             = Nothing
indexJ i (Single _ x) 
  | i == 0                 = Just x
  | otherwise              = Nothing
indexJ i (Append _ left right)
  | leftHt > i             = indexJ i left
  | (rightHt + leftHt) > i = indexJ (i-leftHt) right
  | otherwise              = Nothing
  where leftHt  = (getSize. size . tag) left
        rightHt = (getSize. size . tag) right

where tag =

tag :: Monoid m => JoinList m a -> 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> indexJ 3 jlIndex3
Just "baz"
*JoinList> indexJ 0 jlIndex3
Just "biz"
*JoinList> indexJ 100 jlIndex3
Nothing

Note - I would've used QuickCheck, but I'm not sure how to use it with algebraic data types.

Answer 1

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 => Int -> Gen (JoinList Size a)
genJoinList 0 = pure Empty
genJoinList 1 = Single (Size 1) <$> arbitrary
genJoinList n = do
  left <- choose (0, n)
  Append (Size n) <$> (genJoinList left) <*> (genJoinList (n - left))

toList :: JoinList b a -> [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) => Int -> JoinList m a -> Bool
prop_index n js = indexJ n js == indexI n (toList js)
  where
    indexI n xs = lookup n $ zip [0..] xs

main = quickCheck $ \n -> forAll (sized genJoinList) $ \js -> prop_index n js

An Arbitrary instance would need FlexibleInstances by the way.