ZipList Monoid haskell

Question

The default monoid for lists in the GHC Prelude is concatenation.

[1,2,3] <> [4,5,6] becomes [1,2,3] ++ [4,5,6] and thus [1,2,3,4,5,6]

I want to write a ZipList Monoid instance that behaves like this:

[
  1 <> 4
, 2 <> 5
, 3 <> 6
]

The result is [5,7,9] assuming I am using the sum monoid. Note this behaves like zipWith (+)

Potentially it would behave like this:

[
  Sum 1 <> Sum 4
, Sum 2 <> Sum 5
, Sum 3 <> Sum 6
]

I need to create a newtype around the ZipList newtype and the Sum newtype in order to create an instance for Monoid, Arbitrary, and EqProp. Thus avoiding orphan instances. This is how both the ZipList and the Sum looks like in the Prelude:

newtype ZipList a = ZipList { getZipList :: [a] }
newtype Sum a = Sum { getSum :: a }

This is how my newtype MyZipList looks: Does it look right?

newtype MyZipList a =
  MyZipList (ZipList [a])
  deriving (Eq, Show)

instance Monoid a => Monoid (MyZipList a) where
  mempty = MyZipList (ZipList [])

  mappend (MyZipList z) (MyZipList z') =
    MyZipList $ liftA2 mappend z z'

instance Arbitrary a => Arbitrary (MyZipList a) where
  arbitrary = MyZipList <$> arbitrary

instance Eq a => EqProp (MyZipList a) where
  (=-=) = eq

This is how my newtypeMySum looks like: Does this look right?

newtype MySum a =
  MySum (Sum a)
  deriving (Eq, Show)

 instance (Num a, Monoid a) => Monoid (MySum a) where
   mempty = MySum mempty

   mappend (MySum s) (MySum s') = MySum $ s <> s'

 instance Arbitrary a => Arbitrary (MySum a) where
   arbitrary = MySum <$> arbitrary

I would like assistance in finding out where I went wrong.

But x <> mempty == mempty <> x == x (that is one of the properties of a monoid), in your case mempty <> x == mempty. I think in case of a ZipList, the mappend should be equal to an infinite list of memptys (of the a type). — Willem Van Onsem
Why do you create a new newtype instead of just adding a Monoid instance for ZipList a? — Dominique Devriese
@DominiqueDevriese "I need to create a newtype ... Thus avoiding orphan instances." — luqui
If your goal was for MySum to behave exactly like Sum then that at least looks right. Although I'm not sure why you're wrapping Sum and ZipList if you're going to re-implement their behaviour anyway - you might as well just build MySum and MyZipList directly. That being said, you said you want assistance but you didn't actually say what your problem was. You explained pretty well what you actually did, but your question is missing a description of what's actually going wrong. — Cubic

Benjamin Hodgson Benjamin Hodgson · Accepted Answer · 2018-05-02T10:54:29

First note that ZipList’s Applicative instance already has the zippy behaviour you want.

ghci> liftA2 (<>) (Sum <$> ZipList [1,2,3]) (Sum <$> ZipList [4,5,6]) :: ZipList Int
ZipList [Sum 5, Sum 7, Sum 9]

Then use the fact that any Applicative gives rise to a Monoid by lifting the monoidal behaviour of its contents through the monoidal functor itself. The plan is to abstract the liftA2 (<>) pattern from the expression I wrote above.

newtype Ap f a = Ap { getAp :: f a }
instance (Applicative f, Monoid a) => Monoid (Ap f a) where
    mempty = Ap $ pure mempty
    Ap xs `mappend` Ap ys = Ap $ liftA2 mappend xs ys

(As far as I know this newtype is missing from base, which seems like an oversight to me, though there may be a good reason for it. In fact, I’d argue that ZipList should have a zippy Monoid instance out of the box, but, alas, it doesn’t.)

Your desired Monoid is then just Ap ZipList (Sum Int). This is equivalent to the MyZipList Monoid you wrote by hand (except for the mistake in your mempty - it should be MyZipList $ ZipList $ repeat mempty), but composing it out of reusable newtypes like this is less ad-hoc and requires less boilerplate.

ZipList Monoid haskell

1 Answers