group-theory-0.2.1.0: The theory of groups
Copyright (c) 2020-2021 Reed Mullanix Emily Pillmore BSD-style Reed Mullanix , Emily Pillmore stable non-portable Trustworthy Haskell2010

Data.Group.Free

Description

This module provides definitions for FreeGroups and FreeAbelianGroups, along with useful combinators.

Synopsis

Free groups

newtype FreeGroup a Source #

A representation of a free group over an alphabet a.

The intuition here is that Left a represents a "negative" a, whereas Right a represents "positive" a.

Note: This does not perform simplification upon multiplication or construction. To do this, one should use simplify.

Constructors

 FreeGroup FieldsrunFreeGroup :: [Either a a]

Instances

Instances details
 Source # Instance detailsDefined in Data.Group.Free Methods(>>=) :: FreeGroup a -> (a -> FreeGroup b) -> FreeGroup b #(>>) :: FreeGroup a -> FreeGroup b -> FreeGroup b #return :: a -> FreeGroup a # Source # Instance detailsDefined in Data.Group.Free Methodsfmap :: (a -> b) -> FreeGroup a -> FreeGroup b #(<$) :: a -> FreeGroup b -> FreeGroup a # Source # Instance detailsDefined in Data.Group.Free Methodspure :: a -> FreeGroup a #(<*>) :: FreeGroup (a -> b) -> FreeGroup a -> FreeGroup b #liftA2 :: (a -> b -> c) -> FreeGroup a -> FreeGroup b -> FreeGroup c #(*>) :: FreeGroup a -> FreeGroup b -> FreeGroup b #(<*) :: FreeGroup a -> FreeGroup b -> FreeGroup a # Source # Instance detailsDefined in Data.Group.Free Methods(<|>) :: FreeGroup a -> FreeGroup a -> FreeGroup a #some :: FreeGroup a -> FreeGroup [a] #many :: FreeGroup a -> FreeGroup [a] # Source # Instance detailsDefined in Control.Applicative.Cancellative Methods Source # Instance detailsDefined in Data.Group.Foldable MethodsgoldMap :: Group g => (a -> g) -> FreeGroup a -> g Source #toFG :: FreeGroup a -> FG a Source # Eq a => Eq (FreeGroup a) Source # Instance detailsDefined in Data.Group.Free Methods(==) :: FreeGroup a -> FreeGroup a -> Bool #(/=) :: FreeGroup a -> FreeGroup a -> Bool # Ord a => Ord (FreeGroup a) Source # Instance detailsDefined in Data.Group.Free Methodscompare :: FreeGroup a -> FreeGroup a -> Ordering #(<) :: FreeGroup a -> FreeGroup a -> Bool #(<=) :: FreeGroup a -> FreeGroup a -> Bool #(>) :: FreeGroup a -> FreeGroup a -> Bool #(>=) :: FreeGroup a -> FreeGroup a -> Bool #max :: FreeGroup a -> FreeGroup a -> FreeGroup a #min :: FreeGroup a -> FreeGroup a -> FreeGroup a # Show a => Show (FreeGroup a) Source # Instance detailsDefined in Data.Group.Free MethodsshowsPrec :: Int -> FreeGroup a -> ShowS #show :: FreeGroup a -> String #showList :: [FreeGroup a] -> ShowS # Source # Instance detailsDefined in Data.Group.Free Methods(<>) :: FreeGroup a -> FreeGroup a -> FreeGroup a #sconcat :: NonEmpty (FreeGroup a) -> FreeGroup a #stimes :: Integral b => b -> FreeGroup a -> FreeGroup a # Source # Instance detailsDefined in Data.Group.Free Methodsmappend :: FreeGroup a -> FreeGroup a -> FreeGroup a #mconcat :: [FreeGroup a] -> FreeGroup a # Source # Instance detailsDefined in Data.Group.Free Methodsinvert :: FreeGroup a -> FreeGroup a #(~~) :: FreeGroup a -> FreeGroup a -> FreeGroup a #pow :: Integral x => FreeGroup a -> x -> FreeGroup a # Eq a => GroupOrder (FreeGroup a) Source # Instance detailsDefined in Data.Group.Free Methods Free group combinators simplify :: Eq a => FreeGroup a -> FreeGroup a Source # O(n) Simplifies a word in a free group. Examples: Expand >>> simplify$ FreeGroup [Right 'a', Left 'b', Right 'c', Left 'c', Right 'b', Right 'a']
FreeGroup {runFreeGroup = [Right 'a',Right 'a']}


interpret :: Group g => FreeGroup g -> g Source #

O(n) Interpret a word in a free group over some group g as an element in a group g.

interpret' :: Group g => FreeGroup g -> g Source #

O(n) Strict variant of interpret.

present :: Group g => FreeGroup g -> (FreeGroup g -> g) -> g Source #

Present a Group as a FreeGroup modulo relations.

Free abelian groups

A representation of a free abelian group over an alphabet a.

The intuition here is group elements correspond with their positive or negative multiplicities, and as such are simplified by construction.

Examples:

>>> let single a = MkFreeAbelianGroup $Map.singleton a 1 >>> a = single 'a' >>> b = single 'b' >>> a FreeAbelianGroup$ fromList [('a',1)]
>>> a <> b
FreeAbelianGroup $fromList [('a',1),('b',1)] >>> a <> b == b <> a True >>> invert a FreeAbelianGroup$ fromList [('a',-1)]
>>> a <> b <> invert a
FreeAbelianGroup $fromList [('b',1)] >>> gtimes 5 (a <> b) FreeAbelianGroup$ fromList [('a',5),('b',5)]


Instances

Instances details
 Eq a => Eq (FreeAbelianGroup a) Source # Instance detailsDefined in Data.Group.Free.Internal Methods Ord a => Ord (FreeAbelianGroup a) Source # Instance detailsDefined in Data.Group.Free.Internal Methods(<) :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool #(>) :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool # Show a => Show (FreeAbelianGroup a) Source # Instance detailsDefined in Data.Group.Free.Internal MethodsshowList :: [FreeAbelianGroup a] -> ShowS # Ord a => Semigroup (FreeAbelianGroup a) Source # Instance detailsDefined in Data.Group.Free.Internal Methodsstimes :: Integral b => b -> FreeAbelianGroup a -> FreeAbelianGroup a # Ord a => Monoid (FreeAbelianGroup a) Source # Instance detailsDefined in Data.Group.Free.Internal Methodsmconcat :: [FreeAbelianGroup a] -> FreeAbelianGroup a # Ord a => Group (FreeAbelianGroup a) Source # Instance detailsDefined in Data.Group.Free.Internal Methodspow :: Integral x => FreeAbelianGroup a -> x -> FreeAbelianGroup a # Ord a => Abelian (FreeAbelianGroup a) Source # Instance detailsDefined in Data.Group.Free.Internal Source # Instance detailsDefined in Data.Group.Free.Internal Methods

pattern FreeAbelianGroup :: Ord a => Map a Integer -> FreeAbelianGroup a Source #

Bidirectional pattern synonym for the construction of FreeAbelianGroups.

O(n) Constructs a FreeAbelianGroup from a finite Map from the set of generators (a) to its multiplicities.

O(1) Gets a representation of FreeAbelianGroup as Map. The returned map contains no records with multiplicity 0 i.e. lookup a on the returned map never returns Just 0.

Free abelian group combinators

abfoldMap :: Abelian g => (a -> g) -> FreeAbelianGroup a -> g Source #

Given a function from generators to an abelian group g, lift that function to a group homomorphism from FreeAbelianGroup to g.

In other words, it's a function analogus to foldMap for Monoid or goldMap for Group.

abmap :: Ord b => (a -> b) -> FreeAbelianGroup a -> FreeAbelianGroup b Source #

Functorial fmap for a FreeAbelianGroup.

Examples:

>>> singleton 'a' <> singleton 'A'
FreeAbelianGroup $fromList [('A',1),('a',1)] >>> import Data.Char (toUpper) >>> abmap toUpper$ singleton 'a' <> singleton 'A'
FreeAbelianGroup $fromList [('A',2)]  Monadic join for a FreeAbelianGroup. singleton :: a -> FreeAbelianGroup a Source # Lift a singular value into a FreeAbelianGroup. Analogous to pure. Examples: >>> singleton "foo" FreeAbelianGroup$ fromList [("foo",1)]


abInterpret :: Abelian g => FreeAbelianGroup g -> g Source #

Interpret a free group as a word in the underlying group g.