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


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

Please critique my implementation.


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.