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 (ShowEq)

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

Tyson Williams
It seems that any applicative functor that contains monoidal values itself forms a monoid.

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

2019-05-13 11:28 UTC

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 not an 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?

public static Tuple<GuidTResult> Apply<TResultT>(
    this Tuple<GuidFunc<TTResult>> selector,
    Tuple<GuidT> source)
{
    throw new NotImplementedException("What would you write here?");
}

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?

public static Tuple<Guidint> Add(this Tuple<Guidint> x, Tuple<Guidint> y)
{
    throw new NotImplementedException("What would you write here?");
}

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:

public static Tuple<stringTResult> Apply<TResultT>(
    this Tuple<stringFunc<TTResult>> selector,
    Tuple<stringT> source)
{
    return Tuple.Create(
        selector.Item1 + source.Item1,
        selector.Item2(source.Item2));
}
 
public static Tuple<stringint> Add(this Tuple<stringint> x, Tuple<stringint> y)
{
    return Tuple.Create(x.Item1 + y.Item1, x.Item2 + y.Item2);
}

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.

2019-05-14 20:44 UTC


Wish to comment?

You can add a comment to this post by sending me a pull request. Alternatively, you can discuss this post on Twitter or somewhere else with a permalink. Ping me with the link, and I may respond.

Published

Monday, 22 April 2019 05:36:00 UTC

Tags



"Our team wholeheartedly endorses Mark. His expert service provides tremendous value."
Hire me!
Published: Monday, 22 April 2019 05:36:00 UTC