Monoid mempty in pattern matching

Question

I tried to write a generalized maximum function similar to the one in Prelude. My first naiv approach looked like this:
maximum' :: (F.Foldable a, Ord b) => a b -> Maybe b
maximum' mempty = Nothing
maximum' xs = Just $ F.foldl1 max xs

However, when I test it it always returns Nothing regardless of the input:
> maximum' [1,2,3]
> Nothing

Now I wonder whether it's possible to obtain the empty value of a Monoid type instance. A test function I wrote works correctly:
getMempty :: (Monoid a) => a -> a
getMempty _ = mempty

> getMempty [1,2,3]
> []

I had already a look at these two questions but I didn't figure out how the answers solve my problem:
Write a Maximum Monoid using Maybe in Haskell
Haskell Pattern Matching on the Empty Set

How would I rewrite the maximum' function to get it to work ?

Answer 1

As C. A. McCann points out in his comment, you can't pattern match on values, only patterns.

The equation maximum' mempty = Nothing is actually equivalent to the equation maximum' x = Nothing. The argument gets bound to a name and Nothing is returned.

Here's a way to make your code work:

maximum' :: (F.Foldable a, Ord b, Eq (a b), Monoid (a b)) => a b -> Maybe b
maximum' xs
  | xs == mempty = Nothing
  | otherwise    = Just $ F.foldl1 max xs

I.e. you can compare the value xs against mempty. Note that we need a Monoid constraint to be able to get at the value mempty :: a b and an Eq constraint to be able to compare as well.

An other, more elegant, solution would be to use a fold to differentiate between the empty and non-empty cases:

maximum'' :: (F.Foldable a, Ord b) => a b -> Maybe b
maximum'' xs = F.foldl max' Nothing xs
  where max' Nothing x = Just x
        max' (Just y) x = Just $ max x y

Answer 2

There are a few ways to do this (the one @opqdonut demonstrates is good). One could also make a "maximum" monoid around Maybe, and use foldMap.

newtype Maximum a = Max { unMaximum :: Maybe a }

instance (Ord a) => Monoid (Maximum a) where
  mempty = Max Nothing
  mappend (Max Nothing) b = b
  mappend a (Max Nothing) = a
  mappend (Max (Just a)) (Max (Just b)) = Max . Just $ (max a b)

maximum' = unMaximum . F.foldMap (Max . Just)

Answer 3

There are many ways, one is (as you mention) to create an instance of Monoid. However, we need to wrap it to Maybe to distinguish the case when we have no values. The implementation might look like this:

import Data.Monoid (Monoid, mempty, mappend)
import qualified Data.Foldable as F

-- Either we have a maximum value, or Nothing, if the
-- set of values is empty.
newtype Maximum a = Maximum { getMaximum :: Maybe a }
    deriving (Eq, Ord, Read, Show)

instance Ord a => Monoid (Maximum a) where
    mempty                      = Maximum Nothing

    -- If one part is Nothing, just take the other one.
    -- If both have a value, take their maximum.
    (Maximum Nothing) `mappend` y    = y
    x `mappend` (Maximum Nothing)    = x
    (Maximum (Just x)) `mappend` (Maximum (Just y))
                                     = Maximum (Just $ x `max` y)


maximum' :: (F.Foldable t, Ord a) => t a -> Maximum a
maximum' = F.foldMap (Maximum . Just)

Answer 4

As many have already told you, you can't pattern match on a value.

As fewer people have told you, pattern matching is arguably the Haskell equivalent of object fields in a language like Java: it's valuable for internal consumption by tightly coupled code, but probably not something you wish to expose to external client code. Basically, if you let a piece of code know your type's constructors, now you can never change these constructors without changing that other piece of code—even if your type's semantics did not really change.

The best solution here is really to just use Foldable.foldr:

maximum' :: (F.Foldable a, Ord b) => a b -> Maybe b
maximum' = F.foldr step Nothing
    where step x Nothing = Just x
          step x (Just y) = Just (max x y)

Note that foldr is a generalized destructor or eliminator for Foldable instances: its two arguments are "what to do with a non-empty Foldable" and "what to do with mempty. This is more abstract and reusable than pattern matching.

Answer 5

How about

maximum' :: (Monoid (t a), F.Foldable t, Ord a, Eq (t a)) => t a -> Maybe a
maximum' xs
   | xs == mempty = Nothing
   | otherwise    = Just $ F.foldl1 max xs

You were missing a guard.

On the getEmpty function, you don't need it. Just use mempty, and allow its type to be inferred.