# Applicative monoids by Mark Seemann

*An applicative functor containing monoidal values itself forms a monoid.*

This article is an instalment in an article series about applicative functors. An applicative functor is a data container that supports combinations. If an applicative functor contains values of a type that gives rise to a monoid, then the functor itself forms a monoid.

In a previous article you learned that lazy computations of monoids remain monoids. Furthermore, a lazy computation is an applicative functor, and it turns out that the result generalises. The result regarding lazy computation is just a special case.

### Monap #

Since version 4.11 of Haskell's *base* library, `Monoid`

is a subset of `Semigroup`

, so in order to create a `Monoid`

instance, you must first define a `Semigroup`

instance.

In order to escape the need for flexible contexts, you'll have to define a wrapper `newtype`

that'll be the instance. What should you call it? It's going to be an applicative functor of monoids, so perhaps something like *ApplicativeMonoid?* Nah, that's too long. *AppMon*, then? Sure, but how about flipping the terms: *MonApp?* That's better. Let's drop the last *p* and dispense with the Pascal case: *Monap*.

*Monap* almost looks like *Monad*, only with the last letter rotated half a revolution. This should allow for maximum confusion.

To be clear, I normally don't advocate for droll word play when writing production code, but I occasionally do it in articles and presentations. The *Monap* in this article exists only to illustrate a point. It's not intended to be used. Furthermore, this article doesn't discuss monads at all, so the risk of confusion should, hopefully, be minimised. I may, however, regret this decision...

### Applicative semigroup #

First, introduce the wrapper `newtype`

:

newtype Monap f a = Monap { runMonap :: f a } deriving (Show, Eq)

This only states that there's a type called `Monap`

that wraps some higher-kinded type `f a`

; that is, a container `f`

of values of the type `a`

. The intent is that `f`

is an applicative functor, hence the use of the letter *f*, but the type itself doesn't constrain `f`

to any type class.

The `Semigroup`

instance does, though:

instance (Applicative f, Semigroup a) => Semigroup (Monap f a) where (Monap x) <> (Monap y) = Monap $ liftA2 (<>) x y

This states that when `f`

is a `Applicative`

instance, and `a`

is a `Semigroup`

instance, then `Monap f a`

is also a `Semigroup`

instance.

Here's an example of combining two applicative semigroups:

λ> Monap (Just (Max 42)) <> Monap (Just (Max 1337)) Monap {runMonap = Just (Max {getMax = 1337})}

This example uses the `Max`

semigroup container, and `Maybe`

as the applicative functor. For `Max`

, the `<>`

operator returns the value that contains the highest value, which in this case is 1337.

It even works when the applicative functor in question is `IO`

:

λ> runMonap $ Monap (Sum <$> randomIO @Word8) <> Monap (Sum <$> randomIO @Word8) Sum {getSum = 165}

This example uses `randomIO`

to generate two random values. It uses the `TypeApplications`

GHC extension to make `randomIO`

generate `Word8`

values. Each random number is projected into the `Sum`

container, which means that `<>`

will add the numbers together. In the above example, the result is 165, but if you evaluate the expression a second time, you'll most likely get another result:

λ> runMonap $ Monap (Sum <$> randomIO @Word8) <> Monap (Sum <$> randomIO @Word8) Sum {getSum = 246}

You can also use linked list (`[]`

) as the applicative functor. In this case, the result may be surprising (depending on what you expect):

λ> Monap [Product 2, Product 3] <> Monap [Product 4, Product 5, Product 6] Monap {runMonap = [Product {getProduct = 8},Product {getProduct = 10},Product {getProduct = 12}, Product {getProduct = 12},Product {getProduct = 15},Product {getProduct = 18}]}

Notice that we get all the combinations of products: *2* multiplied with each element in the second list, followed by *3* multiplied by each of the elements in the second list. This shouldn't be that startling, though, since you've already, previously in this article series, seen several examples of how an applicative functor implies combinations.

### Applicative monoid #

With the `Semigroup`

instance in place, you can now add the `Monoid`

instance:

instance (Applicative f, Monoid a) => Monoid (Monap f a) where mempty = Monap $ pure $ mempty

This is straightforward: you take the identity (`mempty`

) of the monoid `a`

, promote it to the applicative functor `f`

with `pure`

, and finally put that value into the `Monap`

wrapper.

This works fine as well:

λ> mempty :: Monap Maybe (Sum Integer) Monap {runMonap = Just (Sum {getSum = 0})} λ> mempty :: Monap [] (Product Word8) Monap {runMonap = [Product {getProduct = 1}]}

The identity laws also seem to hold:

λ> Monap (Right mempty) <> Monap (Right (Sum 2112)) Monap {runMonap = Right (Sum {getSum = 2112})} λ> Monap ("foo", All False) <> Monap mempty Monap {runMonap = ("foo",All {getAll = False})}

The last, right-identity example is interesting, because the applicative functor in question is a tuple. Tuples are `Applicative`

instances when the first, or left, element is a `Monoid`

instance. In other words, `f`

is, in this case, `(,) String`

. The `Monoid`

instance that `Monap`

sees as `a`

, on the other hand, is `All`

.

Since tuples of monoids are themselves monoids, however, I can get away with writing `Monap mempty`

on the right-hand side, instead of the more elaborate template the other examples use:

λ> Monap ("foo", All False) <> Monap ("", mempty) Monap {runMonap = ("foo",All {getAll = False})}

or perhaps even:

λ> Monap ("foo", All False) <> Monap (mempty, mempty) Monap {runMonap = ("foo",All {getAll = False})}

Ultimately, all three alternatives mean the same.

### Associativity #

As usual, I'm not going to do the work of formally proving that the monoid laws hold for the `Monap`

instances, but I'd like to share some QuickCheck properties that indicate that they do, starting with a property that verifies associativity:

assocLaw :: (Eq a, Show a, Semigroup a) => a -> a -> a -> Property assocLaw x y z = (x <> y) <> z === x <> (y <> z)

This property is entirely generic. It'll verify associativity for any `Semigroup a`

, not only for `Monap`

. You can, however, run it for various `Monap`

types, as well. You'll see how this is done a little later.

### Identity #

Likewise, you can write two properties that check left and right identity, respectively.

leftIdLaw :: (Eq a, Show a, Monoid a) => a -> Property leftIdLaw x = x === mempty <> x rightIdLaw :: (Eq a, Show a, Monoid a) => a -> Property rightIdLaw x = x === x <> mempty

Again, this is entirely generic. These properties can be used to test the identity laws for any monoid, including `Monap`

.

### Properties #

You can run each of these properties multiple time, for various different functors and monoids. As `Applicative`

instances, I've used `Maybe`

, `[]`

, `(,) Any`

, and `Identity`

. As `Monoid`

instances, I've used `String`

, `Sum Integer`

, `Max Int16`

, and `[Float]`

. Notice that a list (`[]`

) is both an applicative functor as well as a monoid. In this test set, I've used it in both roles.

tests = [ testGroup "Properties" [ testProperty "Associativity law, Maybe String" (assocLaw @(Monap Maybe String)), testProperty "Left identity law, Maybe String" (leftIdLaw @(Monap Maybe String)), testProperty "Right identity law, Maybe String" (rightIdLaw @(Monap Maybe String)), testProperty "Associativity law, [Sum Integer]" (assocLaw @(Monap [] (Sum Integer))), testProperty "Left identity law, [Sum Integer]" (leftIdLaw @(Monap [] (Sum Integer))), testProperty "Right identity law, [Sum Integer]" (rightIdLaw @(Monap [] (Sum Integer))), testProperty "Associativity law, (Any, Max Int8)" (assocLaw @(Monap ((,) Any) (Max Int8))), testProperty "Left identity law, (Any, Max Int8)" (leftIdLaw @(Monap ((,) Any) (Max Int8))), testProperty "Right identity law, (Any, Max Int8)" (rightIdLaw @(Monap ((,) Any) (Max Int8))), testProperty "Associativity law, Identity [Float]" (assocLaw @(Monap Identity [Float])), testProperty "Left identity law, Identity [Float]" (leftIdLaw @(Monap Identity [Float])), testProperty "Right identity law, Identity [Float]" (rightIdLaw @(Monap Identity [Float])) ] ]

All of these properties pass.

### Summary #

It seems that any applicative functor that contains monoidal values itself forms a monoid. The `Monap`

type presented in this article only exists to demonstrate this conjecture; it's not intended to be *used*.

If it holds, I think it's an interesting result, because it further enables you to reason about the properties of complex systems, based on the properties of simpler systems.

**Next: ** Bifunctors.

## Comments

Is it necessary for the functor to be applicative? Do you know of a functor that contains monoidal values for which itself does

notform a monoid?Tyson, thank you for writing. Yes, it's necessary for the functor to be applicative, because you need the applicative combination operator

`<*>`

in order to implement the combination. In C#, you'd need an`Apply`

method as shown here.Technically, the monoidal

`<>`

operator for`Monap`

is, as you can see, implemented with a call to`liftA2`

. In Haskell, you can implement an instance of`Applicative`

by implementing either`liftA2`

or`<*>`

, as well as`pure`

. You usually see`Applicative`

described by`<*>`

, which is what I've done in my article series on applicative functors. If you do that, you can define`liftA2`

by a combination of`<*>`

and`fmap`

(the`Select`

method that defines functors).If you want to put this in C# terms, you need both

`Select`

and`Apply`

in order to be able to lift a monoid into a functor.Is there a functor that contains monoidal values that itself doesn't form a monoid?

Yes, indeed. In order to answer that question, we 'just' need to identify a functor that's

notan applicative functor. Tuples are good examples.A tuple forms a functor, but in general nothing more than that. Consider a tuple where the first element is a

`Guid`

. It's a functor, but can you implement the following function?You can pull the

`T`

value out of`source`

and project it to a`TResult`

value with`selector`

, but you'll need to put it back in a`Tuple<Guid, TResult>`

. Which`Guid`

value are you going to use for that tuple?There's no clear answer to that question.

More specifically, consider

`Tuple<Guid, int>`

. This is a functor that contains monoidal values. Let's say that we want to use the addition monoid over integers. How would you implement the following method?Again, you run into the issue that while you can pull the integers out of the tuples and add them together, there's no clear way to figure out which

`Guid`

value to put into the tuple that contains the sum.The issue particularly with tuples is that there's no general way to combine the leftmost values of the tuples. If there is - that is, if leftmost values form a monoid - then the tuple is also an applicative functor. For example,

`Tuple<string, int>`

is applicative and forms a monoid over addition:You can also implement

`Add`

with`Apply`

, but you're going to need two`Apply`

overloads to make it work.Incidentally, unbeknownst to me, the

`Ap`

wrapper was added to Haskell's`Data.Monoid`

module 12 days before I wrote this article. In all but name, it's equivalent to the`Monap`

wrapper presented here.I want to add some prepositional phrases to our statements like I commented here to help claify things. I don't think that

`Tuple<string, int>`

can be applicative because there are no type parameters in which it could be applicative. Were you trying to say that`Tuple<string, B>`

is applicative in`B`

? This seems to match your`Apply`

function, which doesn't depend on`int`

.Tyson, you're quite right; good catch. My wording was incorrect (I was probably either tired or in a hurry when I wrote that), but fortunately, the code looks like it's correct.

That you for pointing out my error.

I do agree with the monoid part, where "addition" means string concatenation for the first item and integer addition for the second item.

Now I am trying to improve my understanding of this statement. In Haskell, my understanding the definition of the Applicative type class applied to

`Tuple<string, B>`

requires a function`pure`

from`B`

to`Tuple<string, B>`

. What it the definition of this funciton? Does it use the empty string in order to make an instance of`Tuple<string, B>`

? If so, what is the justification for this? Or maybe my reasoning here is mistaken.Tyson, thank you for writing. In Haskell, it's true that applicative functors must also define

`pure`

. In this article series, I've glosssed over that constraint, since I'm not aware of any data containers that can lawfully implement`<*>`

or`liftA2`

, butcan'tdefine`pure`

.The applicative instance for tuples is, however, constrained:

The construct

`((,) a)`

means any tuple where the first element has the generic type`a`

. The entire expression means that tuples are applicative functors when the first element forms a monoid; that's the restriction on`a`

. The definition of`pure`

, then, is:That is, use the monoidal identity (

`mempty`

) for the first element, and use`x`

as the second element. For strings, since the identity for string concatenation is the empty string, yes, it does exactly mean that`pure`

for`Tuple<string, B>`

would return a tuple with the empty string, and the input argument as the second element:That's the behaviour you get from Haskell as well: