[SOLVED] Is there a class that models "patches"?

Is there a class that models "patches"?

I'm looking for a class in like the following in a Haskell library (or at least to know the mathematical name for such a thing):

class Monoid patch => MyThing patch t where
  applyPatch :: t -> patch -> t

I can have instances like this:

instance MyThing (Last t) t where
  applyPatch x patch = case getLast patch of
    Just y => y
    Nothing => x

But I could also have instances like this:

instance MyThing (Dual (Map key value)) (Map key value) where
  applyPatch x patch = ...

Where the patch essentially adds and/or replaces key/value pairs from the map.

One could go further if you wanted to do deletions:

instance MyThing (Dual (Map key (Maybe value))) (Map key value) where
  applyPatch x patch = ...

Aside from patch being a monoid, the main law I want this class to follow is associativity, concretely:

forall (x :: t, y :: patch, z :: patch). 
  (x `applyPatch` y) `applyPatch` z == x `applyPatch` (y <> z)

My thought (well, actually ChatGPTs thought) that this was an "Affine Space", but the issue is that my underlying "patch" type, whilst a monoid, is not an additive group, because it doesn't have inverses.

So basically I think I want an affine space without inverses. Does this exist, either mathematically or in a Haskell library?

Solution

What you have described amounts to a monoid (or semigroup) action. One place where a class for that can be found is Data.Monoid.Action from monoid-extras:

class Action m s where
    act :: m -> s -> s

Paraphrasing the documentation, the laws are:

act (m1 <> m2) = act m1 . act m2
-- Also, if m is a monoid:
act mempty = id
-- Additionally, if s has some algebraic structure then act m preserves it.
-- For instance, if s is a monoid, then act m should be a monoid homomorphism.