Hacktoberfest 2026: los issues que los mantenedores marcaron para octubre, abiertos y aptos para principiantes. Explorar issues de Hacktoberfest

Use of (lawless) Group/monoid-subclasses/InverseSemigroup in view

Abierto
  • ¿Algo no está bien?
#37 9 comentarios 0 reacciones 0 asignados Ver en GitHub

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
5/5
Tiempo estimado
Más de una semana
Aptitud para principiantes
18/100
Tipo de issue
Refactorización
Claridad
Necesita aclaración
Estado de actividad
Estancado
Stack tecnológico
haskell
Área
tooling

Línea de trabajo

No files or tests are named. Start by inspecting the current Group and MonoidalMap instances in patch, then resolve whether the project should adopt InverseSemigroup or use monoid-subclasses; done means the chosen approach supports lawful Patch-related instances and has its laws and behavior verified.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

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.
Lenguaje dominante
Haskell
Estrellas
17
Forks
17
Merge medio
9 h 32 min
PR fusionados (30 d)
1

Preparar el entorno

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de reflex-frp/patch

Todos los issues de reflex-frp/patch

Issues similares

Más issues de Haskell

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.