Searching a Join List for an index

Question

For the Join List algebraic data type:

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

This homework's problem states to implement indexJ:

Exercise 2 The first annotation to try out is one for fast indexing into a JoinList . The idea is to cache the size (number of data ele- ments) of each subtree.

This can then be used at each step to deter- mine if the desired index is in the left or the right branch. We have provided the Sized module that defines the Size type, which is simply a newtype wrapper around an Int .

In order to make Size s more accessible, we have also defined the Sized type class which provides a method for obtaining a Size from a value.

indexJ finds the JoinList element at the specified index. If the index is out of bounds, the function returns Nothing. By an index in a JoinList we mean the index in the list that it represents. That is, consider a safe list indexing function

I implemented indexJ, which searches for a matching index within a JList.

indexJ :: (Sized b, Monoid b) => Int -> JoinList b a -> Maybe a
indexJ _ Empty = Nothing
indexJ i (Single s x)
  | (getSize . size) s == i = Just x
  | otherwise               = Nothing
indexJ i (Append _ left right) 
  | (getSize . size . tag) left >= i = indexJ i left
  | otherwise                        = indexJ i right

with the following background:

tag's definition

newtype Size = Size Int
  deriving (Eq, Ord, Show, Num)

getSize :: Size -> Int
getSize (Size i) = i

class Sized a where
  size :: a -> Size

...

tag :: Monoid m => JoinList m a -> m

Testing

jlIndex1 :: JoinList Size String
jlIndex1 = Append (Size 1) (Single (Size 0) "foo") (Single (Size 1) "bar")

*JoinList> indexJ 1 jlIndex1
Just "bar"
*JoinList> indexJ 33 jlIndex1
Nothing

Please critique my implementation.

Answer 1

The implementation of indexJ seems to be broken. In particular:

indexJ i (Append _ left right) 
  | (getSize . size . tag) left >= i = indexJ i left
  | otherwise                        = indexJ i right

indexing with i in the right part is wrong. I'd suggest you to create a function that converts a list into a JoinedList (ideally a blanced one), and then test if indexing into the list produces the same result as indexing into the JoinedList.

Also the implementation of tag is missing, but this is a crucial part of the code, without it it can't be really reviewed.

I'd also suggest to implement other operations on JoinLists, in particular creating a singleton list and concatenation, perhaps also prepending/appending an element to a list.

Finally, you're using a Monoid instance for tagging the tree. This is in general a good idea, but the assignment doesn't say anythong about monoids, sobe sure to understand how the monoid there should be used. You never use the fact that m a monoid in your code. If you're unsure, I'd suggest to forget about monoids at this point and use just the provided Size data type.