patch

patch copied to clipboard

Continuing https://github.com/Taneb/groups/issues/7#issuecomment-1006968329 in a more appropriate place:

Context: patch currently provides (but does not directly use) a Group class with lawless instance (Ord k, Group g) => Group (MonoidalMap k g). (let x = fromList [(1, y)] in x ~~ x evaluates to fromList [(1, mempty)] instead of mempty.) I'm sure that something downstream is using this class to provide efficient Patch instances or something.

Context: patch, groups, group-theory (via reexport from groups), and monoid-subclasses all provide a class that requires (<>) to be commutative. Some as a subclass of Semigroup, some as a subclass of their Group.

There are two options:

Option 1 - Create (here or elsewhere) and use an InverseSemigroup class

Since it can have lawful instance (Ord k, InverseSemigroup g) => InverseSemigroup (MonoidalMap k g):

class Semigroup g => InverseSemigroup g where
  -- Laws:
  -- x <> inv x <> x = x
  -- inv x <> x <> inv x = x
  -- inverses are unique
  -- All idempotents commute
  -- All idempotents have the from y = x <> inv x for some x
  inv :: g -> g

  (~~) :: g -> g -> g
  pow :: Integral n => g -> n -> g

-- For -XDerivingVia
newtype ViaGroup g = ViaGroup g
instance Group g => InverseSemigroup (ViaGroup g)

Option 2 - Write Patch instances using monoid-subclasses instead

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.

CC @cgibbard @Ericson2314

A bit off-topic, but @endgame you might be interested in https://github.com/obsidiansystems/finite-support-normal-form/blob/main/src/Data/Map/Total/FSNF.hs . It's a bit heavyweight --- using a type family like that is definitely a smell --- but by making it impossible to have a mempty in the values it avoids a lot of trouble.

Note that it requires https://github.com/mstksg/nonempty-containers/pull/13/files to build.

That is indeed heavyweight, but I think that if you want to ban memptys from your map, you have to use a newtype of some sort - normalising after applying (<>) is not enough. I suspect newtype Normalized c = Normalized c with the following instances would probably be lawful, and may be a better option than adding another niche, law-only algebra class:

instance (Ord k, MonoidNull m) => Semigroup (Normalized (MonoidalMap k v))
instance (Ord k, MonoidNull m) => Monoid (Normalized (MonoidalMap k v))
instance (Ord k, MonoidNull g, Group g) => Group (Normalized (MonoidalMap k g))

Here, "normalisation" means "there are no mempty values" in the map. Though such a structure (even if you use newtype NormalizedMap k v = ...) cannot be a Functor, as map g . map f /= map (g . f) if f returns mempty.

Thinking about this again: would putting Group instances on Defaultable.Map.Generalized.Defaultable Map give us what we want? Holding that default value of mempty means it's no longer possible to distinguish k |-> mempty from "k is not present", which was the edge case that broke the Group instance.

Though you lose MonoidNull/DecidablyEmpty, and risk carrying around a bunch of junk k |-> mempty elements; there should probably be some way to aggressively prune "present-but-default" values from a defaultable map when you know that Eq is cheap.

Since nothing in patch itself actually uses this, it is very hard to make a decision. I think we should just delete the instance, see what breaks, and deal with it downstream.

The main downstream thing I'm aware of is QueryT in reflex: https://hackage.haskell.org/package/reflex-0.8.2.1/docs/Reflex-Query-Base.html#t:QueryT

Here, "normalisation" means "there are no mempty values" in the map. Though such a structure (even if you use newtype NormalizedMap k v = ...) cannot be a Functor, as map g . map f /= map (g . f) if f returns mempty.

@endgame Not sure if you're still interested in this topic (as the last comment was from some time ago), but I did recently create a similar type to the one you describe:

• API documentation: Data.Total.MonoidMap
• source: Data/Total/MonoidMap/Internal.hs
• repository: https://github.com/jonathanknowles/total-monoidal-maps

Features:

• models a total relation from keys to monoidal values.
• automatic canonicalisation of mempty values (i.e., there should be no mempty values in the internal data structure).
• full support for most the type classes in the monoid-subclasses library.
• lawful Group instance.
• uses MonoidNull for internal comparisons with mempty, to avoid requiring an Eq instance.

I haven't released it to hackage yet, as I'm still reviewing the API.

Not sure if you're interested in taking a look, but I'd be very interested to hear any feedback that you might have!

All the best Jonathan

Very cool, thanks for pinging me. I think that in many cases I want a non-total map with a valid grouplike structure, so I think eventually I might write a package that provides class Monoid g => InverseSemigroup g, along with a deriving via helper newtype ViaGroup g; instance Group g => InverseSemigroup (ViaGroup g). But for total monoidal maps, your code looks pretty nice.

I probably won't have time to go over it thoroughly, but it's good that you're exploring this design space. You might also want to look at packages defaultable-map and total-map — since your map is total, you can probably do what they do to get at least an Applicative instance. If you want to ask me specific questions, file an issue against your package and @-me there so we don't derail this thread?

I probably won't have time to go over it thoroughly, but it's good that you're exploring this design space.

No worries. Thanks for looking!

You might also want to look at packages defaultable-map and total-map

Definitely -- these are two packages whose design I'm studying very carefully.

since your map is total, you can probably do what they do to get at least an Applicative instance.

I'm not sure it's possible to build a lawful Applicative instance, at least with the current design, as mempty values are never included in the internal data structure, and AFAIK this restriction prevents a lawful Functor instance. But I'm open to suggestions! (I believe the solution used by total-map is to never cull mempty values unless the trim operation is called, which allows it to satisfy the composition law.)

If you want to ask me specific questions, file an issue against your package and @-me there so we don't derail this thread?

Sure, thanks for looking! I'll try to avoid creating further noise in this thread. 😄