Applicative instance trying to use monoidal functors

Question

I'm learning Haskell and trying to do exercises from book Haskell Programming from first principles and I'm stack trying to write applicative for Pair type

 data Pair a = Pair a a deriving Show

I have seen some other examples on web but I'm trying somewhat different applicative functor, I'm trying to utilize monoidal structure of this type. Here is what I have

data Pair a = Pair a a deriving (Show, Eq)

instance Functor Pair where
     fmap f (Pair x y) = Pair (f x) (f y)

instance Semigroup a => Semigroup (Pair a) where
    (Pair x y) <> (Pair x' y') = Pair (x <> x') (y <> y')

instance Applicative Pair where
    pure x = Pair x x 
    (Pair f g) <*> p = fmap f p <> fmap g p

Unfortunately this will not compile:

* No instance for (Semigroup b) arising from a use of `<>'
  Possible fix:
    add (Semigroup b) to the context of
      the type signature for:
        (<*>) :: forall a b. Pair (a -> b) -> Pair a -> Pair b
* In the expression: fmap f p <> fmap g p
  In an equation for `<*>': (Pair f g) <*> p = fmap f p <> fmap g p
  In the instance declaration for `Applicative Pair'

And this is where I'm stack; I don't see how can I add typeclass constraint to Applicative definition and I thought that making type Pair instance of Semigroup is enough.

Other solutions that I have seen are like

Pair (f g) <*> Pair x y = Pair (f x) (g y)

but these solutions don't utilize monoidal part of Pair type

Is it even possible to make this applicative the way I't trying?

I could be wrong, but I think you are using the term "monoidal functor" to mean something other than its [actual definition](https://en.wikipedia.org/wiki/Monoidal_functor). — chepner, Aug 03 '18 at 12:24
You're running into the same problem that means `Set` can't be a `Monad` (or `Applicative`), so the many discussions around that problem floating around the web should also be interesting to you. Consider googling "constrained monad" for many, many starting points. — Daniel Wagner, Aug 03 '18 at 13:35

score 5 · Accepted Answer · answered Aug 03 '18 at 13:24

Although it's true that Applicative is the class representing monoidal functors (specifically, Hask endofunctors which are monoidal), Allen&Moronuki present this unfortunately in a way that seems to suggest a direct relation between the Monoid and Applicative classes. There is, in general, no such relation! (The Writer type does define one particular Applicative instance based on the Monoid class, but that's an extremely special case.)
This spawned a rather extended discussion at another SO question.

What the “monoidal” in “monoidal functor” refers to is a monoidal structure on the category's objects, i.e. on Haskell types. Namely, you can combine any two types to a tuple-type. This has per se nothing whatsoever to do with the Monoid class, which is about combining two values of a single type to a value of the same type.

Pair does allow an Applicative instance, but you can't base it on the Semigroup instance, although the definition actually looks quite similar:

instance Applicative Pair where
  pure x = Pair x x
  Pair f g <*> Pair p q = Pair (f p) (g q)

However, you can now define the Semigroup instance in terms of this:

instance Semigroup a => Semigroup (Pair a) where
  (<>) = liftA2 (<>)

That, indeed, is a valid Semigroup instance for any applicative, but it's usually not the definition you want (often, containers have a natural combination operation that never touches the contained elements, e.g. list concatenation).

Thanks! Being beginner it is somewhat hard to follow discussions but I think I understood part of it: applicative instance should work for all types that implement it while my implementation depended on fact that type should implement instance of Semigroup (all the types regardless how deep they are in structure) and second the "monoidal" part should be about structure (in my case it is Pair constructor) not the values which I was trying to combine (this is what Monoid is doing) — simkestuff, Aug 03 '18 at 16:56

score 1 · Answer 2 · answered Aug 03 '18 at 11:54

I don't think that Pair is an Applicative the way you want it to be, Applicative states that

(<*>) :: f (a -> b) -> f a -> f b

should work for all functions in first position whereas you want

(<*>) :: Semigroup b => f (a -> b) -> f a -> f b.

If Pair was always a Semigroup (like Maybe or List for example) your reasoning would be sound, but you need the pre-requisite of the Pair-containee to be Semigroup.

score 1 · Answer 3 · answered Aug 03 '18 at 13:52

Correct: Pair can't be made an Applicative in the way you want, because Applicative f demands that f a "feel applicative-y" for any a, even non-Semigroup as. Consider writing an alternative class and implementing it:

class CApplicative f where
    type C f
    pure :: C f a => a -> f a
    app  :: C f b => f (a -> b) -> f a -> f b

instance CApplicative Pair where
    type C Pair = Semigroup
    pure x = Pair x x
    app (Pure f g) p = fmap f p <> fmap g p

score 0 · Answer 4 · answered Apr 26 '22 at 08:51

This can be derive since base 4.17.0.0, which includes the via types Generically and Generically1. This will derive the same instances as leftaroundabout writes:

{-# Language DeriveGeneric      #-}
{-# Language DerivingStrategies #-}
{-# Language DerivingVia        #-}

import Data.Monoid
import GHC.Generics

data Pair a = Pair a a
  deriving
  stock (Generic, Generic1)

  deriving (Semigroup, Monoid)
  via Generically (Pair a)

  deriving (Functor, Applicative)
  via Generically1 Pair

Alternatively you can lift Semigroup and Monoid through the Applicative

  deriving (Semigroup, Monoid, Num)
  via Ap Pair a

Applicative instance trying to use monoidal functors

4 Answers4