Retrieve annotation from a tree annotated with a Monoid

Question

Working on this homework from 2013 for self-learning.

For the following Algebraic Data Type:

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

I implemented tag:

tag :: Monoid m => JoinList m a -> m
tag Empty                 = mempty
tag (Single x _)          = x
tag (Append x left right) = x 

Example:

*JoinList Data.Monoid> tag (Append (Product 100) (Single (Product 10) "foo") (Single (Product 10) "bar"))
Product {getProduct = 100}

*JoinList Data.Monoid> tag (Empty :: JoinList (Product Integer) String)
Product {getProduct = 1}

*JoinList Data.Monoid> tag (Single (Product 5) "foo")
Product {getProduct = 5}

Originally, I had implemented the Append ... case as:

tag (Append x left right) = x  `mappend` (tag left) `mappend` (tag right)

But, I'm not sure if I can assume that the Monoid m in JustList m x is already populated.

Please critique my implementation.

Answer 1

Since this is a relatively simple question, 4 days is enough waiting for a more knowledgeable answer.

Your implementation of tag is correct and there is neither much room for improvement, nor there really is other ways to do it. You can replace Append x left right with Append x _ _ like you did for Single, and that's about the change you can make.

Originally, I had implemented the Append ... case as:

That implementation was just wrong, consider what the two implementations return for your first example: 100 != 100 * 10 * 10.

I'm not sure if I can assume that the [a] in [B] is already populated.

You can assume it is populated, you cannot have instances of algebraic data types with missing elements.

What you were trying to do probably is ensuring that an invariant, namely tag (Append x left right) == tag left <> tag right, is satisfied. This is the duty of a smart constructor. In this case the other function (+++ operator) you were asked to implement in the homework.