Modifying `Monoid (Generically a)`'s `mconcat`.

[L0neGamer]

TLDR: Monoid (Generically a) does not derive its methods from a's Semigroup instance, so produces incongruous methods when used to derive instances

background: #324

Introduction

The Monoid instance for Generically a can result in an incorrect implementation if the Semigroup instance wasn't also Generically derived.

Here is the current implementation of Monoid (Generically a):

-- | @since base-4.17.0.0
instance (Generic a, Monoid (Rep a ())) => Monoid (Generically a) where
  mempty :: Generically a
  mempty = Generically (to (mempty :: Rep a ()))

  mappend :: Generically a -> Generically a -> Generically a
  mappend = (<>)

Here is an example where it goes awry:

newtype L a = L [a]
  deriving (Generic, Show, Eq)
  deriving Monoid via (Generically (L a))

instance Semigroup (L a) where
  L [] <> l = l
  l <> _ = l

> L [1] <> L [2]
L [1]
> L [1] `mappend` L [2]
L [1,2]

The important thing to note is that as per my Monad of No Return proposal, we will be removing mappend as a method instance, so this particular case will be solved.

However, the same problem crops up for mconcat:

> mconcat [L [1], L [2]]
L [1,2]

Proposed Change

This proposal suggests that we change the definition of Monoid (Generically a) to

instance (Generic a, Monoid (Rep a ()), Semigroup a) => Monoid (Generically a) where
  mempty :: Generically a
  mempty = Generically (to (mempty :: Rep a ()))

  mconcat :: [Generically a] -> Generically a
  mconcat = foldr (coerce @(a -> a -> a) (<>)) mempty
  {-# INLINE mconcat #-}

This results in:

> mconcat [L [1], L [2]]
L [1]

This means that Generically a's Monoid instance may be unlawful with respect to its Semigroup instance, but since the main use of this newtype is deriving, we want the most correct implementation for that purpose. To further this line of thought, as part of this proposal I plan to elaborate on these risks in documentation and recommend that if users do derive Monoid using Generically, they should be deriving Semigroup as well for consistency and lawfulness.

The proposer does not know if this is the best definition, and welcomes discussion. Coercions and inline pragma were used in the hopes that that helps performance, but if it seems unlikely to do so we can go with some simpler definition.

mappend is already being removed as a class method (eventually), so mconcat is the only method to fix.

Alternatives

It may be recommended to add memptyGeneric and sappendGeneric as methods for more granular defining of Monoid and Semigroup using Generic.

Using sconcat would be nice but has different strictness properties to most mconcats.

We could decide that deriving Monoid without deriving semigroup in the same way is unsupported behaviour, point that out in the documentation and possibly even wire in a warning for it.

Impact

I have had a brief rg of my local hackage download, and I cannot see any places where Monoid is defined and Semigroup isn't, which would result in someone relying on the behaviour outlined; further, I can't see any obvious uses of Generically in values, meaning it is unlikely someone is using Generically to get around having to define their own monoid and semigroup instances.

This may also mean that this adjustment is unnecessary.

Implementation

The current implementation can be found in the GHC gitlab here: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/16011

Addendum

If reviewers wish to play around themselves:

-- example.hs
-- load with ghci, and comment/uncomment lines `(1)` and `(2)`, run `main`
{-# LANGUAGE DerivingVia #-}
{-# LANGUAGE UndecidableInstances #-}

import GHC.Generics
import Data.Coerce
import Data.Semigroup
import Data.List.NonEmpty qualified as NE

main :: IO ()
main = do
  let l1 = L [1]
      l2 = L [2]
  print (l1 <> l2)
  print (l1 `mappend` l2)

  print (foldr (<>) mempty [l1, l2])
  print (mconcat [l1, l2])

newtype L a = L [a]
  deriving (Generic, Show, Eq)
  deriving Monoid via (Generically (L a)) -- (1)
  -- deriving Monoid via (Generically' (L a)) -- (2)

instance Semigroup (L a) where
  L [] <> l = l
  l <> _ = l

newtype Generically' a = Generically' a

instance (Generic a, Semigroup (Rep a ())) => Semigroup (Generically' a) where
  (<>) :: Generically' a -> Generically' a -> Generically' a
  Generically' a <> Generically' b = Generically' (to (from a <> from b :: Rep a ()))

instance (Generic a, Monoid (Rep a ()), Semigroup a) => Monoid (Generically' a) where
  mempty :: Generically' a
  mempty = Generically' (to (mempty :: Rep a ()))

  mconcat :: [Generically' a] -> Generically' a
  mconcat = foldr (coerce @(a -> a -> a) (<>)) mempty
  {-# INLINE mconcat #-}

[phadej]

So currently

mconcat :: [a] -> a
mconcat = foldr mappend mempty

mconcat = foldr (<>) mempty

Here mempty will be derived generically, but
<> will refer to Generically a instance and also be generically derived.

OP suggests that <> for a should be used instead, because it can be different.

This feels so subtle that it's one more reason I wouldn't use Generically for Monoid
when Semigroup is also not Generically derived (then (<>) @a = @(<>) @(Generically a))
If the both instances are derived this proposal doesn't change the behaviour,
AFAIU, so that is 👍
Everything else, I personally don't mind.

I also wouldn't mind if this subtelty of Generically (Monoid a) instance were
documented; and potentially the mix&match use discouraged. It feels that there are too few cases where non-generic <> and generic mempty would make a lawful instance, and IMO these cases can be written without relying on Generically (instead of needing commentary of why the methods are compatible).

[phadej]

FWIW, #324 and this changes the instance from being unlawful in one way to unlawful in another. Before #324 <> and mappend could differ; after mempty and <> can be incompatible. IMO that's another good reason to actively discourage manual Semigroup X and Monoid X via (Generically X) instance mix.

[L0neGamer]

I agree, and after I get some more feedback I'll definitely add more documentation to Generically to outline these pitfalls.

[phadej]

FWIW, if

instance Monoid X where
  mempty = genericMempty

were used, then it's clear that (<>) @X is used for mconcat implementation. base however doesn't provide genericMempty (nor genericMappend), so this is not currently an option.

IMO, this is cleaner than trying to do this via Generically, though maybe not as concice.

EDIT: semigroups has gmappend and gmempty: https://hackage-content.haskell.org/package/semigroups-0.20.1/docs/Data-Semigroup-Generic.html#v:gmappend,

[L0neGamer]

Out of interest, have we historically exposed things like genericMempty or genericMappend for other types?

[phadej]

Out of interest, have we historically exposed things lik

base doesn't really have any generic implementations, other than Monoid stuff now (after Generically were added). Other libraries do. E.g. https://hackage-content.haskell.org/package/aeson-2.2.4.1/docs/Data-Aeson-Types.html#v:genericToJSON or https://hackage-content.haskell.org/package/QuickCheck-2.18.0.0/docs/Test-QuickCheck-Arbitrary.html#v:genericShrink

I also think that it's generally good practice to have names for instance members, i.e.

fooX = ...

class C X where
  foo  = fooX

instead of just

class C X where
  foo = ...

whether it's fmap = map or default foo = genericFoo or (even) default foo = defaultFoo. That way using an instance is not mandatory, users can be more explicit if they want to.

[L0neGamer]

@TeofilC what's the next step?

I have a prototype implementation spread out throughout my monad of no return MR; I'll clean the entire thing up once the CI passes: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/15795

[TeofilC]

Once you've split out your MR, you'll also need to do an impact analysis, but I assume you have some of that done from your broader project.

Any more thoughts about this @velveteer @Daniel-Diaz @ChickenProp @noughtmare @mpscholten @doyougnu @parsonsmatt @jeltsch @rickowens ?

[jeltsch]

My opinion is that using Generically should result in all methods being derived generically. This behavior is simple and easy to remember, and it’s what the name Generically suggests. From what I understand, implementing the above proposal would result in users being able to automate implementation of mempty in some cases. That’s way to little a reason for me to make this inherently problematic change. It shouldn’t be too difficult to write an mempty implementation by hand.

[ChickenProp]

Previous comment I wrote, rewritten for the current situation, which I think is pretty similar to the one in that thread:

If someone writes

data D = ...
  deriving stock Generic
  deriving Monoid via (Generically D)

instance Semigroup D where ...

Then (assuming Monoid (Rep D ())) we have four instances. Semigroup D, Monoid D, Semigroup (Generically D) and Monoid (Generically D).

With the current state of affairs, Monoid D has mconcat derived generically, and it might be different from foldr (<>) mempty, which is unlawful.

With the proposed change, Monoid D has mconcat = foldr (<>) mempty. But the Monoid (Generically D) instance has mconcat equal (up to coercion) to foldr (<>) mempty using Semigroup Ds (<>) not using Semigroup (Generically D)'s (<>), so that instance might be unlawful.

If we have to pick one of these instances to be unlawful, I'd think it should be the Generically one, as you suggest. Dunno if this is possible, but I guess ideally there should be a warning if someone does this. (This might have been discussed in the previous thread, I don't remember.)

[L0neGamer]

I have created the initial PR: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/16011

[meooow25]

This proposal suggests that we change the definition of Monoid (Generically a) to

instance (Generic a, Monoid (Rep a ()), Semigroup a) => Monoid (Generically a) where
  mempty :: Generically a
  mempty = Generically (to (mempty :: Rep a ()))

  mconcat :: [Generically a] -> Generically a
  mconcat as = case as of
    [] -> mempty
    x : xs -> (coerce @(NonEmpty a -> a) sconcat) (x :| xs)
  {-# INLINE mconcat #-}

The proposed definition changes the strictness of the function. Depending on the monoid, it is more strict than foldr mappend mempty.

To see this with your example.hs, add

newtype LA = LA [Int] deriving (Generic, Show) deriving (Semigroup, Monoid) via (Generically LA)
newtype LB = LB [Int] deriving (Generic, Show) deriving (Semigroup, Monoid) via (Generically' LB)

Then,

> mconcat (LA [10] : LA [20] : undefined)
LA [10,20*** Exception: Prelude.undefined
> mconcat (LB [10] : LB [20] : undefined)
LB [10*** Exception: Prelude.undefined

[L0neGamer]

You are correct, do you have a suggested alternative out of interest? Originally I had that foldr coerce mess, but using sconcat makes more sense to me if we can use it.

EDIT: something like foldr (coerce @(a -> a -> a) (<>)) mempty could work

[Bodigrim]

Isn't it just because sconcat default definition is (unexpectedly) stricter than mconcat default definition?

sconcat (a :| as) = go a as where
  go b (c:cs) = b <> go c cs
  go b []     = b

mconcat :: [a] -> a
mconcat = foldr mappend mempty

[meooow25]

You are correct, do you have a suggested alternative out of interest? Originally I had that foldr coerce mess, but using sconcat makes more sense to me if we can use it.

I definitely suggest not changing the strictness of the function.

EDIT: something like foldr (coerce @(a -> a -> a) (<>)) mempty could work

That ought to work 👍

---

Overall, my 2c is that adding an unlawful instance is... questionable. But then again, I have never wanted to define Semigroup manually and derive Monoid generically.