haskellmonadsmonoidsalternative-functormonadplus

What can we do with Alternative but cannot do with Monoid?


I read Why MonadPlus and not Monad + Monoid? and I understand a theoretical difference, but I cannot figure out a practical difference, because for List it looks the same.

mappend [1] [2] == [1] <|> [2]

Yes. Maybe has different implementations

mappend (Just "a") (Just "b") /= (Just "a") <|> (Just "b")

But we can implement Maybe Monoid in the same way as Alternative

instance Monoid (Maybe a) where
  Nothing `mappend` m = m
  m `mappend` _ = m

So, can someone show the code example which explains a practical difference between Alternative and Monoid?

The question is not a duplicate of Why MonadPlus and not Monad + Monoid?


Solution

  • Here is a very simple example of something one can do with Alternative:

    import Control.Applicative
    import Data.Foldable
    
    data Nested f a = Leaf a | Branch (Nested f (f a))
    
    flatten :: (Foldable f, Alternative f) => Nested f a -> f a
    flatten (Leaf x) = pure x
    flatten (Branch b) = asum (flatten b)
    

    Now let's try the same thing with Monoid:

    flattenMonoid :: (Foldable f, Applicative f) => Nested f a -> f a
    flattenMonoid (Leaf x) = pure x
    flattenMonoid (Branch b) = fold (flattenMonoid b)
    

    Of course, this doesn't compile, because in fold (flattenMonoid b) we need to know that the flattening produces a container with elements that are an instance of Monoid. So let's add that to the context:

    flattenMonoid :: (Foldable f, Applicative f, Monoid (f a)) => Nested f a -> f a
    flattenMonoid (Leaf x) = pure x
    flattenMonoid (Branch b) = fold (flattenMonoid b)
    

    Ah, but now we have a problem, because we can't satisfy the context of the recursive call, which demands Monoid (f (f a)). So let's add that to the context:

    flattenMonoid :: (Foldable f, Applicative f, Monoid (f a), Monoid (f (f a))) => Nested f a -> f a
    flattenMonoid (Leaf x) = pure x
    flattenMonoid (Branch b) = fold (flattenMonoid b)
    

    Well, that just makes the problem worse, since now the recursive call demands even more stuff, namely Monoid (f (f (f a)))...

    It would be cool if we could write

    flattenMonoid :: ((forall a. Monoid a => Monoid (f a)), Foldable f, Applicative f, Monoid (f a)) => Nested f a -> f a
    

    or even just

    flattenMonoid :: ((forall a. Monoid (f a)), Foldable f, Applicative f) => Nested f a -> f a
    

    and we can: instead of writing forall a. Monoid (f a), we write Alternative f. (We can write a typeclass that expresses the first, easier-to-satisfy constraint, as well.)