Semigroup and Monoid instances for ZipList
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
forZipList a
that corresponds tozipWith (<>)
already exists asAp ZipList a
. - I can't find an
Applicative
instance that would give the desiredSemigroup
underAp
, so I doubt we'll ever want to pair thisSemigroup
with a differentApplicative
. - 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.