4

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?

cafce25
  • 15,907
  • 4
  • 25
  • 31
Clinton
  • 22,361
  • 15
  • 67
  • 163
  • You say it performs additions and replacements - but not deletions ("tombstones")? – Dai Aug 22 '23 at 01:31
  • In the base case, if you just replace `t` with `Maybe t` you've got deletions. In the map case, I've added an extra instance which models deletions to the question body. Just need to add `Maybe` to the patch `value` – Clinton Aug 22 '23 at 01:49
  • My Haskell is very rusty, but it's idiomatic in Haskell to use immutable data, rather than mutate structures in-place (and annoyingly, Haskell lacks _ergonomic_ record types) - in the case where data is immutable then I'd describe [this as a "projection"](https://en.wikipedia.org/wiki/Projection_(mathematics)) rather than a "patch". – Dai Aug 22 '23 at 01:51
  • Kudos to ChatGPT for suggesting affine space! Indeed, an affine space can be considered as a manifold upon which a symmetry group acts, which is just another special case of a monoid action. – leftaroundabout Aug 22 '23 at 09:27

1 Answers1

7

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.
duplode
  • 33,731
  • 7
  • 79
  • 150
  • Spot on, exactly what I was looking for. Thanks! – Clinton Aug 22 '23 at 02:10
  • 1
    It's worth noting that this is a functor: `Action m a` = `FunctorOf (Basically m) (->) (Const a)` and the laws are an example of the Functor laws! – Iceland_jack Aug 22 '23 at 10:00
  • Where [`newtype Basically m a b = Basically m`](https://www.reddit.com/r/haskell/comments/gf54o6/monoids_as_oneobject_categories_or_not/) lifts a Monoid to a Category: `instance Monoid m => Category (Basically m)`. – Iceland_jack Aug 22 '23 at 10:01
  • 1
    You know what `act mempty = id` wears on a first date? A class action law suit. – Daniel Wagner Aug 22 '23 at 20:12
  • @Iceland_jack Yup -- the action as a functor from the single-object category to Hask (and then made to fit `Category`/`FunctorOf` through phantoms). Also, a homomorphisms are functors as well (phrasing it in this style, from `Basically m` to `Basically n`), and in particular an action is a homomorphism to `Endo s`. – duplode Aug 22 '23 at 23:22