Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use Group from elsewhere #4

Open
Ericson2314 opened this issue Jan 8, 2020 · 15 comments
Open

Use Group from elsewhere #4

Ericson2314 opened this issue Jan 8, 2020 · 15 comments

Comments

@Ericson2314
Copy link
Member

Ericson2314 commented Jan 8, 2020

We should find an existing library for this

@Ericson2314
Copy link
Member Author

Ericson2314 commented Jan 10, 2020

@endgame
Copy link
Contributor

endgame commented Apr 21, 2020

Proliferation of Group classes has been a bugbear of mine for a while: cmk/magmas#1

I might have time to knock up a PR if groups needs features/operators/...

@Ericson2314
Copy link
Member Author

That would be great! There is also https://github.com/reflex-frp/patch/blob/develop/src/Data/Monoid/DecidablyEmpty.hs which....I guess can stay here for now.

@endgame
Copy link
Contributor

endgame commented Apr 22, 2020

DecidablyEmpty is MonoidNull from monoid-subclasses, isn't it?

@endgame
Copy link
Contributor

endgame commented Apr 22, 2020

Here is the mapping from patch terms to groups terms:

  • negateG -> invert
  • (~~) has no analogue. I can PR this into groups and see what @Taneb thinks. It also has no fixity; what would make sense for it?
  • class Additive -> class Abelian
  • Most of the instances present in patch will need to be ported over. (:.:) and (:*:) may be controversial since they come from GHC.Generics and groups bills itself as Haskell98. We could provide instances for Data.Functor.Product.Product as well as/instead of (:*:) but there's a note in the code that points to a massive Ed post about why instances for Data.Functor.Compose.Compose aren't provided.

Thoughts?

@Taneb
Copy link

Taneb commented Apr 23, 2020

I'm not opposed to adding instances for types in base.

I don't know what (~~) is here. Is it a group subtract? In which case I have no opposition to adding it. I'd suggest infixl 6 to match (-) but that not play nice with (<>) which associates in the opposite direction to (+).

@endgame
Copy link
Contributor

endgame commented Apr 23, 2020

@Taneb (~~) is group subtract, defined here:

patch/src/Data/Patch.hs

Lines 45 to 46 in 25f202b

(~~) :: q -> q -> q
r ~~ s = r <> negateG s

(<>) is infixr 6, and we probably want x ~~ y ~~ z to parse as (x ~~ y) ~~ z, so we want infixl of some power. Maybe we give (~~) infixl 7? That give us w <> x ~~ y <> z as w <> ((x ~~ y) <> z), which seems close enough to what we want (by analogy with numbers and w + x - y + z).

@endgame
Copy link
Contributor

endgame commented Apr 23, 2020

One thing I just noticed: patch has Additive as a subclass of Semigroup, whereas groups has Abelian as a subclass of Group. Will this be a problem? (i.e., does there exist places in the reflex ecosystem where Additive semigroups are depended upon, that are not groups?

@endgame
Copy link
Contributor

endgame commented Aug 17, 2020

CC: @3noch @Ericson2314 @maralorn who have been doing recent work on patch and because it would be cool to fix this, and @Taneb because I may need to PR groups again.

PR Taneb/groups#3 just landed, which adds operations to class Group and instances for base types that are used by the patch library. However, I am concerned that some of the other instances that patch uses are not lawful. In particular, it tries to lift instances for Group over MonoidalMaps:

patch/src/Data/Patch.hs

Lines 58 to 59 in 7551cf1

instance (Ord k, Group q) => Group (MonoidalMap k q) where
negateG = fmap negateG

instance (Ord k, Group q) => Group (MonoidalMap k q) where
  negateG = fmap negateG

The laws of Group require that a <> invert a === mempty, but that's not true for MonoidalMaps. If m = fromList [(k, v)] is a MonoidalMap, then:

  m <> invert m
= fromList [(k, v)] <> invert (fromList [(k, v)])
= fromList [(k, v)] <> fromList [(k, invert v)]
= fromList [(k, mempty)]

You'll get all these extra keys mapping to mempty, so it's not a real inverse. We do have the properties m <> invert m <> m === m and invert m <> m <> invert m === m, so the instance could belong to RegularSemigroup, but because I can keep adding as many (k', mempty) pairs as I want when returning inverses, they aren't unique so it can't be an InverseSemigroup.

I had PR Taneb/groups#2 sitting in WIP state for a while, because I couldn't justify introducing new superclasses of Group without having a justification for them.

So, what to do here? I see a few options:

  1. Keep using Group. I don't like this because then we have to upstream unlawful instances to monoidal-containers.
  2. Introduce class RegularSemigroup => Group, and make patch use RegularSemigroup. This might be okay, depending on whether patch is demanding real groups or is okay with pseudoinverses. We can then upstream instance (Ord k, RegularSemigroup g) => RegularSemigroup (Map k g), etc.
  3. Introduce classes RegularSemigroup => InverseSemigroup => Group. Adds yet another subclass with laws but no methods. InverseSemigroup adds the additional requirement that inverses are unique (which doesn't apply for the MonoidalMap case), which also means that all idempotents are of the form x <> invert x and all idempotents commute. Unclear yet if this is useful or whether in practice most people will get by with the RegularSemigroup instance alone. Ed was playing with these at one point but I haven't seen much come from that.
  4. Switch to monoid-subclasses, which I think has the things we need. It provides:
-- | Class of Abelian semigroups with a partial inverse for the Semigroup '<>' operation. The inverse operation '</>' must
-- satisfy the following laws:
-- 
-- > maybe a (b <>) (a </> b) == a
-- > maybe a (<> b) (a </> b) == a
--
-- The '</>' operator is a synonym for both 'stripPrefix' and 'stripSuffix', which must be equivalent as '<>' is both
-- associative and commutative.
--
-- > (</>) = flip stripPrefix
-- > (</>) = flip stripSuffix
class (Commutative m, LeftReductive m, RightReductive m) => Reductive m where
   (</>) :: m -> m -> Maybe m

-- | Subclass of 'Reductive' where '</>' is a complete inverse of the Semigroup '<>' operation. The class
-- instances must satisfy the following additional laws:
--
-- > (a <> b) </> a == Just b
-- > (a <> b) </> b == Just a
class (LeftCancellative m, RightCancellative m, Reductive m) => Cancellative m

This is probably enough machinery to support the AdditivePatch type, and this lib gets us something closer to canonical classes for Additive (which it calls Commutative) and DecidablyEmpty (which it calls MonoidNull).

Since I can't find many explicit uses of Group within the patch library, I'm assuming that most real-world use of Group-ish machinery is through newtype AdditivePatch? It should be easy to rewrite it in terms of monoid-subclasses types.

I think I like 4 > 2 > 3 > 1, but I'd need to know that it's actually usable where patch is used.

@Ericson2314
Copy link
Member Author

Ericson2314 commented Dec 7, 2020

@endgame We don't like the MonoidalMap instance either. Maybe we can just remove it. In fact, I don't think any of this library relies on Group. Maybe it should, but until it does I say just:

  1. Remove Group from this library.
  2. Reexport https://github.com/Taneb/groups + this sketchy instance, deprecated, as an orphan in reflex.

We can hopefully banish it from the whole ecosystem thereafter.

Ericson2314 added a commit that referenced this issue Dec 7, 2020
This is a breaking change here, but need not be a breaking change for Reflex.

The version in the cabal file is bumped to remind whoever does the
future release that this is breaking change.

Closes #4 as far as this library is concerned, though work is still
needed on the Reflex side when supported the new patch version to fix
this issue for real.
Ericson2314 added a commit that referenced this issue Dec 7, 2020
This is a breaking change here, but need not be a breaking change for Reflex.

The version in the cabal file is bumped to remind whoever does the
future release that this is breaking change.

Closes #4 as far as this library is concerned, though work is still
needed on the Reflex side when supported the new patch version to fix
this issue for real.
@endgame
Copy link
Contributor

endgame commented Dec 7, 2020

I just woke up and haven't thought about this a whole lot recently, but I suspect that maps will be hard to banish, because they're such a useful idea. I do still want to explore using monoid-subclasses (at the very least, would replace Additive and DecidablyEmpty with more well-known versions), but there's a multi-step process there:

  1. Add any missing instances for types in base to monoid-subclasses
  2. Make monoidal-containers depend on monoid-subclasses and add instances
  3. Fix up patch/reflex.

Until I get more time to think about this, not having a home-grown Group is a step forward.

@Ericson2314
Copy link
Member Author

Ericson2314 commented Dec 8, 2020

Until I get more time to think about this, not having a home-grown Group is a step forward.

Yeah exactly, we "purifies" patch, and then "purify" reflex by successively pushing the bad instance further down the dependency graph until they aren't needed at all.

I suspect that maps will be hard to banish, because they're such a useful idea.

I should write about this more somewhere, but I want to make a TotalMap abstraction where the idea is every key has a value, and we secretly store a a v' which is missing mempty so as not to waste space / denormalize storing (k, mempty) pairs. This isn't a Functor (in Hask), but is much nicer algebraically. A type familiy would map v to v' so that it can safely be an opaque newtype.

It's a big yak-shave to get here, including needing haskell/containers#616 to be the v' for nested maps, but once we do a big "impurity" (in the crystal sense) of our abstractions will be eradicated.

@endgame
Copy link
Contributor

endgame commented Dec 8, 2020

I've seen a few "total map" packages on hackage, but none of them satisfied me. Looking forward to seeing another take on the idea. Bonus points if you can generalise over monoids (probably MonoidNull, so you can do the "don't store mempty" optimisation) and non-monoids in your value type (build the map from a function universe -> a).

@Ericson2314
Copy link
Member Author

Ericson2314 commented Dec 8, 2020

Yeah the thing I am thinking of is more like

class HasNonNull a where
  type NonNull a

newtype TotalMap k v = TotalMap (Map k (NonNull v))

Which is a rather more severe, breaking Functor as I mentioned, but actually reliably does the optimization.

@Ericson2314
Copy link
Member Author

One thing I just noticed: patch has Additive as a subclass of Semigroup, whereas groups has Abelian as a subclass of Group. Will this be a problem? (i.e., does there exist places in the reflex ecosystem where Additive semigroups are depended upon, that are not groups?

Oh I just noticed this. Yeah I think it would be better to be cautious and make the superclass match.

Also I deleted AdditivePatch by mistake in the PR, 🤦.

Ericson2314 added a commit that referenced this issue Dec 9, 2020
TODO group's abelian should have Semigroup superclass.

The MonoidalMap instance was deleted because it is not lawful. But it
might need to be added to reflex.

The version in the cabal file is bumped to remind whoever does the
future release that this is breaking change.

Closes #4.
Ericson2314 added a commit that referenced this issue Dec 10, 2020
TODO group's abelian should have Semigroup superclass.

The MonoidalMap instance was deleted because it is not lawful. But it
might need to be added to reflex.

The version in the cabal file is bumped to remind whoever does the
future release that this is breaking change.

Closes #4.
Ericson2314 added a commit that referenced this issue Dec 10, 2020
TODO group's abelian should have Semigroup superclass.

The MonoidalMap instance was deleted because it is not lawful. But it
might need to be added to reflex.

The version in the cabal file is bumped to remind whoever does the
future release that this is breaking change.

Closes #4.
Ericson2314 added a commit that referenced this issue Dec 11, 2020
TODO group's abelian should have Semigroup superclass.

The MonoidalMap instance was deleted because it is not lawful. But it
might need to be added to reflex.

The version in the cabal file is bumped to remind whoever does the
future release that this is breaking change.

Closes #4.
Ericson2314 added a commit that referenced this issue Dec 12, 2020
Keep `Additive`, however. See ChangeLog for more details.

The version in the cabal file is bumped to remind whoever does the
future release that this is breaking change.

Closes #4.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants