Monoid on any Foldable

Question

I'm trying to make an instance of a Monoid on haskell, a monoid that can be applicable on any Foldable strutucture that contains comparables elements and returns the maximun value stored.

So far i have this

import Data.List
import Data.Functor
import Data.Monoid
import Data.Foldable
import Data.Tree

newtype Max a = Max { getMax :: Maybe a}
   deriving (Eq, Ord, Show, Read)

instance Ord a => Monoid (Max a) where
   mempty = Max Nothing
   mappend (Max x) (Max y) = Max (max x y)

It works prefectly on list but have some issue with Trees. When i use it on void list it returns

ghci> foldMap (Max . Just) []
Max {getMax = Nothing}

And that's what i want, but when i use it on Trees with no elements

ghci> foldMap (Max . Just) (Node [] [])
Max {getMax = Just []}

But i want to it returns Nothing instead Just []. It doesn't opperate with Nodes with no childrens but it works with valued ones

ghci> foldMap (Max . Just) (Node 22 [Node 7 [Node 42 []], Node 18 [] ])
Max {getMax = Just 42}

Any suggestion?

PD: I'm using ghci 7.10

Answer 1

The Tree type in Data.Tree does not support empty trees. Ask GHCI what the type of Node [] [] is and you'll find out something like this:

Node [] [] :: a => Tree [a]

Your monoid works fine.