Abelian could merely require Semigroup

[Ericson2314]

Right now it requires Group.

Thanks to @endgame for fixing most of the incompatabilities between this package's Group and reflex-frp's patch library's in #3. I think this is the one that remains.

[Taneb]

I think that if this change is made, theAbelian class won't belong in this library. I'm not happy making this change here.

[endgame]

What about deprecating in favour of https://hackage.haskell.org/package/monoid-subclasses-1.0.1/docs/Data-Semigroup-Cancellative.html#t:Commutative ?

[Taneb]

What about deprecating in favour of https://hackage.haskell.org/package/monoid-subclasses-1.0.1/docs/Data-Semigroup-Cancellative.html#t:Commutative ?

I'd rather not do that either: monoids-subclasses is a significantly larger package that wouldn't necessarily be appropriate to depend on in cases where groups would be OK.

To me, there's two possibilities that would be better than the status quo for groups: a CommutativeSemigroup class in a small package (I have no interest in creating or maintaining this right now), or that class in base.

[emilypi]

It's not quite true that you get an Abelian group from cancellative semigroups. You also need a unit. If you come from the other side via commutative monoids, you also need a quotient via the grothendieck construction on monoids: https://en.wikipedia.org/wiki/Grothendieck_group. If you meant turning Abelian into just a class for commutativity, I would disagree, since it changes the thrust of this package considerably.

For a more fine-grained algebraic hierarchy, I suggest you look into magmas. I would want groups to change. It derives most of its utility for me from being foundational: no dep footprint, just the base classes and a few relevant combinators. I do not want to think about implementing 6 instances every time I want a group, for little to no value in the vast majority of cases.

[Ericson2314]

@emilypi

It's not quite true that you get an Abelian group from cancellative semigroups.

I missed this at first too, but that's a plain commutative semigroup class that just happens to be in a module called Data.Semigroup.Cancellative.

I would want groups to change

I assume you meant "wouldn't"?

---

So to be clear, I absolutely think that there is value distinguishing a "small, light, useful" hierarchy from the "zomg every algebra ever" hierarchy.

But I was thinking

class Semigroup m => Abelian m

or

class Semigroup m => Additive m
type Abelian m = (Group m, Additive m)

is sort of a finer-grained hierarchy "for free", since their a no net increase in classes or dependencies.

Still, what I can do is keep Additive in the patch library now and just use this library's group, which is still better than the status quo.

[Ericson2314]

@Taneb to make this a bit more concrete, we today use https://github.com/reflex-frp/patch/blob/develop/src/Data/Semigroup/Additive.hs . This module certainly doesn't belong in patch. If you don't want it in groups, would you be happy to depend on 3rd library that provides it?

[emilypi]

group-theory provides it for Group

[Ericson2314]

@emilypi that is still with the Group superclass though? Or am I missing something?

[Ericson2314]

@cgibbard should be able to confirm, but I think our Additive is merely for commutativity, and not hinting at + overloading, were-there-be-a-ring-which-part-would-we-be--ness, or any such other thing.

We do stuff with communitive groups, and with mere communitive semigroups. We simply want to be able to share the "communitive" part between both parts so we aren't stuck writing instances two separate methodless type classes.

[endgame]

As does https://hackage.haskell.org/package/monoid-subclasses-1.1.2/docs/Data-Semigroup-Cancellative.html#t:Commutative

The other problem is that patch uses a Group class with an unlawful pointwise instance (Ord k, Group g) => Group (Map k g). (let x = fromList [(1, y)] in x ~~ x evaluates to fromList [(1, mempty)] instead of mempty.)

patch's DecidablyEmpty is also MonoidNull from monoid-subclasses.

I can't find any code in patch that relies on the Group class, so I would suggest (I haven't checked revdeps) that patch wants either:

• an InverseSemigroup class somewhere, as this lets us define good instances for Map etc (but makes Group a law-only subclass :S); or
• to see if you can build out of the stuff in monoid-subclasses (probably the Reductive/Cancellative classes).

[Ericson2314]

Yeah we might want to end up depending on monoid-subclasses anways, but then I would in turn ask that package to depend on whatever provides the communitive semigroup package (just as group-theory depends on group).

Trying to both deduplicate and respect people's wishes not to be "pushed" into far finer-grained hierarchies.

[Ericson2314]

Also I didn't know we had that sort of unlawfulness, I won't advocate foisting that on others!

[endgame]

Some kind of tiny commutative package providing class Semigroup g => Commutative g might get you what you want, but law-only subclasses are awkward to work with because type inference can lie to you. Perhaps there's no better alternative.

I suspect that most of the time the patchy things can be written against an InverseSemigroup class, which gives you the following conditions on the inverse (stolen from https://www.youtube.com/watch?v=HGi5AxmQUwU circa 18:30):

• x <> inv x <> x = x
• inv x <> x <> inv x = inv x
• Each element has a unique inverse
• All idempotents are of the form y = x <> inv x for some x
• All idempotents commute

[Ericson2314]

@endgame I am not sure whether we "use" commutativity at all. I think we just wanted to avoid having separate Left vs Right notions of semigroup self-patching.

[Ericson2314]

@Taneb are you comfortable doing e.g.

import Data.Semigroup.<NameTBD> -- from other tiny package with just that

class (Group a, <NameTBD> a) => Abelian
instance (Group a, <NameTBD> a) => Abelian

?

I would like to know to decide whether it is worth factoring out that module from patch to the new library at this point :).

[cgibbard]

@cgibbard should be able to confirm, but I think our Additive is merely for commutativity, and not hinting at + overloading, were-there-be-a-ring-which-part-would-we-be--ness, or any such other thing.

Yeah, it's just to indicate commutativity of a semigroup.

[cgibbard]

@endgame I am not sure whether we "use" commutativity at all. I think we just wanted to avoid having separate Left vs Right notions of semigroup self-patching.

We absolutely rely on commutativity: you don't want the view selector in your frontend to rely on the order in which the watches are done! (Also, the optimisation we do to aggregate the view selectors wouldn't work without commutativity: rather than appending all the individual selectors, and having to re-append them constantly whenever any leaf changes, we compute local deltas and apply them to the aggregate, which implicitly commutes everything past everything else.)

[Ericson2314]

(Note that that specific example is downstream of patch itself. @cgibbard and I are discussing, so @Taneb the question above still stands.)

[Taneb]

@Taneb are you comfortable doing e.g.

import Data.Semigroup.<NameTBD> -- from other tiny package with just that

class (Group a, <NameTBD> a) => Abelian
instance (Group a, <NameTBD> a) => Abelian

?

I would like to know to decide whether it is worth factoring out that module from patch to the new library at this point :).

I think I would be

[Ericson2314]

Great, thank you!

[endgame]

@cgibbard @Ericson2314 monoid-subclasses has class (Commutative m, LeftReductive m, RightReductive m) => Reductive m (and similar for Cancellative), and they may get you what you want. Some thoughts:

• Reductive provides an operator (</>) :: Reductive m => m -> m -> Maybe m;
• Cancellative adds two additional laws to (</>):
  • (a <> b) </> a == Just b
  • (a <> b) </> b == Just a
• You can't recover an inversion operation from Cancellative alone, as you can't be certain of isJust (mempty </> x). (Consider instance Cancellative Natural.)
  • Every finite cancellative monoid is a group, but this might not be useful.
• Instance Cancellative m => Cancellative (MonoidalMap k m) smells like it would be lawful:

  instance (Ord k, Commutative m) => Commutative (MonoidalMap k m)
  
  instance (Ord k, LeftReductive m) => LeftReductive (MonoidalMap k m) where
    stripPrefix (MonoidalMap prefix) (MonoidalMap m) =
      MonoidalMap
        <$> mergeA
          (traverseMissing $ \_ _ -> Nothing)
          (traverseMissing $ const pure)
          (zipWithAMatched $ \_ pf v -> stripPrefix pf v)
          prefix
          m
  
  instance (Ord k, RightReductive m) => RightReductive (MonoidalMap k m) where
    stripSuffix (MonoidalMap suffix) (MonoidalMap m) =
      MonoidalMap
        <$> mergeA
          (traverseMissing $ \_ _ -> Nothing)
          (traverseMissing $ const pure)
          (zipWithAMatched $ \_ sf v -> stripSuffix sf v)
          suffix
          m
  
  instance (Ord k, Reductive m) => Reductive (MonoidalMap k m) where
    MonoidalMap x </> MonoidalMap y =
      MonoidalMap
        <$> mergeA
          (traverseMissing $ \_ _ -> Nothing)
          (traverseMissing $ \_ _ -> Nothing)
          (zipWithAMatched $ const (</>))
          x
          y
  
  instance (Ord k, LeftCancellative m) => LeftCancellative (MonoidalMap k m)
  instance (Ord k, RightCancellative m) => RightCancellative (MonoidalMap k m)
  instance (Ord k, CancellativeMonoid m) => Cancellative (MonoidalMap k m)

• This may be enough for your uses of patch - instead of computing the inverse of a patch, instead attempt to unapply it directly?
• If you need to send data structures across a network boundary, you could do this using [Either m m], like the free group in free-algebras.
• If that's not enough, then I think you probably need to build your patch-using stuff atop a new InverseSemigroup class.
• I'm very interested to hear what you end up doing here, and if you do make a minimal package providing class Semigroup m => Commutative m, let me know so I can help PR monoid-subclasses, monoidal-containers, etc.

[Ericson2314]

@endgame it would be better to take this up in reflex where the view stuff @cgibbard is referring to takes place, I think?

[Ericson2314]

@Taneb I have made https://github.com/obsidiansystems/commutative-semigroups by forking this repo and giving you attribution. It doesn't have any base-orphan or anything else, but is doing exactly what this repo did modulo the super class constraint. I will make a PR for groups after I post that to Hackage.

[endgame]

@endgame it would be better to take this up in reflex where the view stuff @cgibbard is referring to takes place, I think?

I figure the root problem is the lawless instance in patch and what do do about it, so I filed it there: reflex-frp/patch#37