How to write a monad instance for a pair where both arguments have the same type?

Question

Suppose I have a type Pair:

data Pair a = Pair a a

What is the right way to write a monad instance for it? My idea is roughly this:

instance Semigroup a => Semigroup (Pair a) where
  Pair a1 a2 <> Pair b1 b2 = Pair (a1 <> b1)(a2 <> b2)

instance Monad Pair where
  return = pure
  (Pair a b) >>= f = f a <> f b

Is it correct? If so then where to specify that b-type in the Pair b is a semigroup?

Answer 1

Actually, the only correct monad instance of Pair is as follows.

instance Monad Pair where
    m >>= f = joinPair (f <$> m)

joinPair :: Pair (Pair a) -> Pair a
joinPair (Pair (Pair x _) (Pair _ y)) = Pair x y

The reason this is the correct monad instance is because Pair is a representable functor.

instance Representable Pair where
    type Rep Pair = Bool

    index (Pair x _) False = x
    index (Pair _ y) True  = y

    tabulate f = Pair (f False) (f True)

Turns out, for every representable functor (>>=) is equivalent to the following bindRep function.

bindRep :: Representable f => f a -> (a -> f b) -> f b
bindRep m f = tabulate (\a -> index (f (index m a)) a)

If we specialize the bindRep function to Pair we get the following.

bindRep :: Pair a -> (a -> Pair b) -> Pair b
bindRep (Pair x y) f = tabulate (\a -> index (f (index (Pair x y) a)) a)
                     = Pair (index (f x) False) (index (f y) True)
--                          |_________________| |________________|
--                                   |                   |
--                           (1st elem of f x)   (2nd elem of f y)

The following blog post by Adelbert Chang explains it better. Reasoning with representable functors.

---

Here's another way to prove uniqueness. Consider the left and right identity monad instance laws.

return a >>= k = k a -- left identity law

m >>= return = m     -- right identity law

Now, for the Pair data type return x = Pair x x. Hence, we can specialize these laws.

Pair a a >>= k = k a     -- left identity law

m >>= \x -> Pair x x = m -- right identity law

So, what should the definition of >>= be in order to satisfy these two laws?

Pair x y >>= f = Pair (oneOf [x1, x2, y1, y2]) (oneOf [x1, x2, y1, y2])
    where Pair x1 y1 = f x
          Pair x2 y2 = f y

The oneOf function returns one of the elements of the list non-deterministically.

Now, if our >>= function is to satisfy the left identity law then when x = y then x1 = x2 and y1 = y2 and the result must be Pair (oneOf [x1, x2]) (oneOf [y1, y2]).

Similarly, if our >>= function is to satisfy the right identity law then x1 = y1 = x and x2 = y2 = y and the result must be Pair (oneOf [x1, y1]) (oneOf [x2, y2]).

Hence, if you want to satisfy both laws then the only valid result is Pair x1 y2.

Answer 2

Functor and applicative instances are easy. The monad instance has taken a while to me.

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

instance Functor Pair where 
  fmap f (Pair a b) = Pair (f a) (f b)

instance Applicative Pair where 
  pure a = Pair a a
  (Pair f g) <*> (Pair a b) = Pair (f a) (g b)

instance Monad Pair where 
  return = pure
  (Pair a b) >>= f = let Pair a' _ = f a 
                         Pair _ b' = f b
                     in  Pair a' b'

The way I've come to this solution is by applying the monad laws. Easily you can check with an example that identity law doesn't hold if you take Pair a' a'' or Pair b' b'' or Pair a' b' nor Pair a'' b''. So the only solutions must be in the diagonals. Defining

(m >>= f) = Pair (first . f . first $ m) (second . f . second $ m)

where first and second are the obvious ones, you can proof all of the laws.

Answer 3

It is possible to make Pair into Monad by having join that takes the diagonal.of the 2×2 square. return has no other choice but replicate its argument. This turns Pair into essentially a fixed length ZipList.

Of course this definition of join discards some data. This may or may not be important.