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
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
indexJ, which searches for a matching index within a
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:
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 Nothing
Please critique my implementation.