Choosing the non-empty Monoid

Question

I need a function which will choose a non-empty monoid. For a list this will mean the following behaviour:

> [1] `mor` []
[1]
> [1] `mor` [2]
[1]
> [] `mor` [2]
[2]

Now, I've actually implemented it but am wondering wether there exists some standard alternative, because it seems to be a kind of a common case. Unfortunately Hoogle doesn't help.

Here's my implementation:

mor :: (Eq a, Monoid a) => a -> a -> a
mor a b = if a /= mempty then a else b

Answer 1

[This is really a long comment rather than an answer]

In my comment, when I said "monoidal things have no notion of introspection" - I meant that you can't perform analysis (pattern matching, equality, <, >, etc.) on monoids. This is obvious of course - the API of Monoids is only unit (mempty) and an operation mappend (more abstractly <>) that takes two monodial things and returns one. The definition of mappend for a type is free to use case analysis, but afterwards all you can do with monoidal things is use the Monoid API.

It's something of a folklore in the Haskell community to avoid inventing things, prefering instead to use objects from mathematics and computer science (including functional programming history). Combining Eq (which needs analysis of is arguments) and Monoid introduces a new class of things - monoids that support enough introspection to allow equality; and at this point there is a reasonable argument that an Eq-Monoid thing goes against the spirit of its Monoid superclass (Monoids are opaque). As this is both a new class of objects and potentially contentious - a standard implementation won't exist.

Answer 2

If your lists contain at most one element, they're isomorphic to Maybe, and for that there's the "first non empty" monoid: First from Data.Monoid. It's a wrapper around Maybe a values, and mappend returns the first Just value:

import Data.Monoid
main = do
    print $ (First $ Just 'a') <> (First $ Just 'b')
    print $ (First $ Just 'a') <> (First Nothing)
    print $ (First Nothing)    <> (First $ Just 'b')
    print $ (First Nothing)    <> (First Nothing :: First Char)

==> Output:
First {getFirst = Just 'a'}
First {getFirst = Just 'a'}
First {getFirst = Just 'b'}
First {getFirst = Nothing}

Conversion [a] -> Maybe a is achieved using Data.Maybe.listToMaybe.

On a side note: this one does not constrain the typeclass of the wrapped type; in your question, you need an Eq instance to compare for equality with mempty. This comes at the cost of having the Maybe type, of course.

Answer 3

First, your mor function looks rather suspicious because it requires a Monoid but never uses mappend, and so it is significantly more constrained than necessary.

mor :: (Eq a, Monoid a) => a -> a -> a
mor a b = if a /= mempty then a else b

You could accomplish the same thing with merely a Default constraint:

import Data.Default

mor :: (Eq a, Default a) => a -> a -> a
mor a b = if a /= def then a else b

and I think that any use of Default should also be viewed warily because, as I believe many Haskellers complain, it is a class without principles.

My second thought is that it seems that the data type you're really dealing with here is Maybe (NonEmpty a), not [a], and the Monoid you're actually talking about is First.

import Data.Monoid

morMaybe :: Maybe a -> Maybe a -> Maybe a
morMaybe x y = getFirst (First x <> First y)

And so then we could use that with lists, as in your example, under the (nonEmpty, maybe [] toList) isomorphism between [a] and Maybe (NonEmpty a):

import Data.List.NonEmpty

morList :: [t] -> [t] -> [t]
morList x y = maybe [] toList (nonEmpty x `mor` nonEmpty y)

λ> mor'list [1] []
[1]

λ> mor'list [] [2]
[2]

λ> mor'list [1] [2]
[1]

(I'm sure that somebody more familiar with the lens library could provide a more impressive concise demonstration here, but I don't immediately know how.)

You could extend Monoid with a predicate to test whether an element is an identity.

class Monoid a => TestableMonoid a
  where
    isMempty :: a -> Bool

    morTestable :: a -> a -> a
    morTestable x y = if isMempty x then y else x

Not every monoid can have an instance of TestableMonoid, but plenty (including list) can.

instance TestableMonoid [a]
  where
    isMempty = null

We could even then write a newtype wrapper with a Monoid:

newtype Mor a = Mor { unMor :: a }

instance TestableMonoid a => Monoid (Mor a)
  where
    mempty = Mor mempty
    Mor x `mappend` Mor y = Mor (morTestable x y)

λ> unMor (Mor [1] <> Mor [])
[1]

λ> unMor (Mor [] <> Mor [2])
[2]

λ> unMor (Mor [1] <> Mor [2])
[1]

So that leaves open the question of whether the TestableMonoid class deserves to exist. It certainly seems like a more "algebraically legitimate" class than Default, at least, because we can give it a law that relates it to Monoid:

• isEmpty x iff mappend x = id

But I do question whether this actually has any common use cases. As I said earlier, the Monoid constraint is superfluous for your use case because you never mappend. So we should ask, then, can we envision a situation in which one might need both mappend and isMempty, and thus have a legitimate need for a TestableMonoid constraint? It's possible I'm being shortsighted here, but I can't envision a case.

I think this is because of something Stephen Tetley touched on when he said that this "goes against the spirit of its Monoid." Tilt your head at the type signature of mappend with a slightly different parenthesization:

mappend :: a -> (a -> a)

mappend is a mapping from members of a set a to functions a -> a. A monoid is a way of viewing values as functions over those values. The monoid is a view of the world of a only through the window of what these functions let us see. And functions are very limited in what they let us see. The only thing we ever do with them is apply them. We never ask anything else of a function (as Stephen said, we have no introspection into them). So although, yes, you can bolt anything you want onto a subclass, in this case the thing we're bolting on feels very different in character from the base class we are extending, and it feels unlikely that there would be much intersection between the use cases of functions and the use cases of things that have general equality or a predicate like isMempty.

So finally I want to come back around to the simple and precise way to write this: Write code at the value level and stop worrying classes. You don't need Monoid and you don't need Eq, all you need is an additional argument:

morSimple :: (t -> Bool) -- ^ Determine whether a value should be discarded
          -> t -> t -> t
morSimple f x y = if f x then y else x

λ> morSimple null [1] []
[1]

λ> morSimple null [1] [2]
[1]

λ> morSimple null [] [2]
[2]