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.