Searching a Join List for an index 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) =&gt; Int -&gt; JoinList b a -&gt; 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 &gt;= 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 -&gt; Int
getSize (Size i) = i

class Sized a where
  size :: a -&gt; Size


...

tag :: Monoid m =&gt; JoinList m a -&gt; m

Testing

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

*JoinList&gt; indexJ 1 jlIndex1
Just "bar"
*JoinList&gt; indexJ 33 jlIndex1
Nothing


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

indexJ i (Append _ left right) 
  | (getSize . size . tag) left &gt;= 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.