Add Semigroup and Monoid instances for ZipList

[AlexandreTunstall]

Motivation

I currently find myself in need of a Semigroup (ZipList a) such that:

ghci> coerce $ ZipList [1 :: Sum Int, 2, 3] <> ZipList [1] :: [Int]
[2, 2, 3]

Semigroup (Ap ZipList a) does not fulfil this need:

ghci> coerce $ Ap (ZipList [1 :: Sum Int, 2, 3] <> Ap (ZipList [1]) :: [Int]
[2]

Surprisingly though, there does not seem to be any such instance in base yet.

Proposal

I propose adding Semigroup ZipList and Monoid ZipList instances that behave as described above.

Here's one way of implementing them:

instance Semigroup a => Semigroup (ZipList a) where
    ZipList a <> ZipList b = ZipList $ go a b
      where
        go [] ys = ys
        go xs [] = xs
        go (x:xs) (y:ys) = (x <> y) : go xs ys

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

The above implementation seems to follow the Monoid laws.

-- Right identity
ZipList x <> mempty
  = ZipList x <> ZipList []
  = ZipList $ go x []
  = ZipList x

-- Left identity
mempty <> ZipList x
  = ZipList [] <> ZipList x
  = ZipList $ go [] x
  = ZipList x

-- Associativity
go [] (go y z)
  = go y z
go (go [] y) z
  = go y z
-- Similarly, go x (go [] z) = go (go x []) z and go x (go y []) = go (go x y) []
go (x:xs) (go (y:ys) (z:zs))
  = go (x:xs) ((y<>z) : go ys zs)
  = (x<>y<>z) : go xs (go ys zs)
go (go (x:xs) (y:ys)) (z:zs)
  = go ((x<>y) : go xs ys) (z:zs)
  = (x<>y<>z) : go (go xs ys) zs
-- By induction, go x (go y z) = go (go x y) z
ZipList x <> (ZipList y <> ZipList z)
  = ZipList x <> ZipList (go y z)
  = ZipList $ go x (go y z)
(ZipList x <> ZipList y) <> ZipList z
  = ZipList (go x y) <> ZipList z
  = ZipList $ go (go x y) z

-- Concatenation holds by definition.

I'm suggesting adding these instances directly to ZipList rather than another list newtype because:

• The equally natural Semigroup for ZipList a that corresponds to zipWith (<>) already exists as Ap ZipList a.
• I can't find an Applicative instance that would give the desired Semigroup under Ap, so I doubt we'll ever want to pair this Semigroup with a different Applicative.
• This behaviour does not contradict the behaviour suggested by the name ZipList.

However, one reason to opt for another newtype is that people may confuse ZipList a and Ap ZipList a. This could be mitigated by explaining the difference in the documentation.

---

This issue was originally raised as GHC issue 22299.

[phadej]

Using semialign

Prelude Data.Align Data.Monoid Data.Coerce> coerce $ salign [1 :: Sum Int, 2, 3] [1] :: [Int]
[2,2,3]

I thought semialign had a newtype for that, but it doesn't. I'll fix that there.

That is a hint that there is no Applicative such that Ap ? a would give salign.

I will find it somewhat confusing that ZipLists Monoid instance would align instead of zipping.

[AlexandreTunstall]

Is align the common term for what I'm trying to do?

If so, then that invalidates my last reason for adding it to ZipList.

[Bodigrim]

It seems there are at least three potential instance Semigroup ZipList: one is just mirroring instance Semigroup [a], another is zipWith (<>), and the third is salign, as proposed above. Such situation suggests that to avoid confusion it's safest not to define instance Semigroup ZipList at all.

@AlexandreTunstall how do you feel about just using salign?

[AlexandreTunstall]

Yes, using salign seems to be the clearest solution to avoid confusion.

Since I'm after a Semigroup instance, I've opened an issue for adding an appropriate instance to the semialign package: haskellari/these#178.

Thanks for introducing me to semialign.