Write a Maximum Monoid using Maybe in Haskell

Question

I've been going through Haskell monoids and their uses, which has given me a fairly good understanding of the basics of monoids. One of the things introduced in the blog post is the Any monoid, and it's usage like the following:

foldMap (Any . (== 1)) tree
foldMap (All . (> 1)) [1,2,3]

In a similar vein, I've been trying to construct a Maximum monoid and have come up with the following:

newtype Maximum a = Maximum { getMaximum :: Maybe a }
        deriving (Eq, Ord, Read, Show)

instance Ord a => Monoid (Maximum a) where
        mempty = Maximum Nothing
        m@(Maximum (Just x)) `mappend` Maximum Nothing = m
        Maximum Nothing `mappend` y = y
        m@(Maximum (Just x)) `mappend` n@(Maximum (Just y))
          | x > y = m
          | otherwise = n

I could construct a Maximum monoid for a specific type - say Num for example, quite easily, but want it to be useful for anything (with the obvious requirement that the anything is an instance of Ord).

At this point my code compiles, but that's about it. If I try to run it I get this:

> foldMap (Just) [1,2,3]

<interactive>:1:20:
    Ambiguous type variable `a' in the constraints:
      `Num a' arising from the literal `3' at <interactive>:1:20
      `Monoid a' arising from a use of `foldMap' at <interactive>:1:0-21
    Probable fix: add a type signature that fixes these type variable(s)

I'm not sure if this is because I'm calling it wrong, or because my monoid is incorrect, or both. I'd appreciate any guidance on where I'm going wrong (both in terms of logic errors and non-idiomatic Haskell usage, as I'm very new to the language).

-- EDIT --

Paul Johnson, in a comment below, suggested leaving Maybe out. My first attempt looks like this:

newtype Minimum a = Minimum { getMinimum :: a }
        deriving (Eq, Ord, Read, Show)

instance Ord a => Monoid (Minimum a) where
        mempty = ??
        m@(Minimum x) `mappend` n@(Minimum y)
          | x < y     = m
          | otherwise = n

but I'm unclear how to express mempty without knowing what the mempty value of a should be. How could I generalise this?

I see how it works, but why have "Maybe a" inside the Maximum type? If you just said "Maximum a" then it simplifies your instance. "Maybe a" is an instance of Ord as long as "a" is, so you could just say "Maximum (Maybe Integer)" and it would do the Right Thing. — Paul Johnson
@Paul Johnson I see your reasoning behind leaving out the Maybe, but I don't know how to express that. I added the code to my question above so that it is more readable. — lukerandall
Ahh, I see your problem. If you added "Bounded" as a constraint then you could have mempty return the lower bound for Minimum and upper bound for Maximum. Otherwise you are correct; there is no Right Thing for mempty to do. Which means that this isn't a monoid. — Paul Johnson

interjay interjay · Accepted Answer · 2011-03-17T20:43:08

The function passed to foldMap needs to return a monoid, in this case of type Maximum a:

> foldMap (Maximum . Just) [1,2,3]
Maximum {getMaximum = Just 3}

Write a Maximum Monoid using Maybe in Haskell

1 Answers