group-theory-0.2.2: The theory of groups
Copyright(c) 2020-2021 Reed Mullanix Emily Pillmore
LicenseBSD-style
MaintainerReed Mullanix <reedmullanix@gmail.com>, Emily Pillmore <emilypi@cohomolo.gy>
Stabilitystable
Portabilitynon-portable
Safe HaskellTrustworthy
LanguageHaskell2010

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 

Fields

Instances

Instances details
Monad FreeGroup Source # 
Instance details

Defined in Data.Group.Free

Methods

(>>=) :: FreeGroup a -> (a -> FreeGroup b) -> FreeGroup b #

(>>) :: FreeGroup a -> FreeGroup b -> FreeGroup b #

return :: a -> FreeGroup a #

Functor FreeGroup Source # 
Instance details

Defined in Data.Group.Free

Methods

fmap :: (a -> b) -> FreeGroup a -> FreeGroup b #

(<$) :: a -> FreeGroup b -> FreeGroup a #

Applicative FreeGroup Source # 
Instance details

Defined in Data.Group.Free

Methods

pure :: 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 #

Alternative FreeGroup Source # 
Instance details

Defined in Data.Group.Free

Methods

empty :: FreeGroup a #

(<|>) :: FreeGroup a -> FreeGroup a -> FreeGroup a #

some :: FreeGroup a -> FreeGroup [a] #

many :: FreeGroup a -> FreeGroup [a] #

Cancellative FreeGroup Source # 
Instance details

Defined in Control.Applicative.Cancellative

Methods

cancel :: FreeGroup a -> FreeGroup a Source #

GroupFoldable FreeGroup Source # 
Instance details

Defined in Data.Group.Foldable

Methods

goldMap :: Group g => (a -> g) -> FreeGroup a -> g Source #

toFG :: FreeGroup a -> FG a Source #

Eq a => Eq (FreeGroup a) Source # 
Instance details

Defined in Data.Group.Free

Methods

(==) :: FreeGroup a -> FreeGroup a -> Bool #

(/=) :: FreeGroup a -> FreeGroup a -> Bool #

Ord a => Ord (FreeGroup a) Source # 
Instance details

Defined in Data.Group.Free

Show a => Show (FreeGroup a) Source # 
Instance details

Defined in Data.Group.Free

Semigroup (FreeGroup a) Source # 
Instance details

Defined 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 #

Monoid (FreeGroup a) Source # 
Instance details

Defined in Data.Group.Free

Group (FreeGroup a) Source # 
Instance details

Defined in Data.Group.Free

Methods

invert :: 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 details

Defined in Data.Group.Free

Methods

order :: FreeGroup a -> Order Source #

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

data FreeAbelianGroup a Source #

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 details

Defined in Data.Group.Free.Internal

Ord a => Ord (FreeAbelianGroup a) Source # 
Instance details

Defined in Data.Group.Free.Internal

Show a => Show (FreeAbelianGroup a) Source # 
Instance details

Defined in Data.Group.Free.Internal

Ord a => Semigroup (FreeAbelianGroup a) Source # 
Instance details

Defined in Data.Group.Free.Internal

Ord a => Monoid (FreeAbelianGroup a) Source # 
Instance details

Defined in Data.Group.Free.Internal

Ord a => Group (FreeAbelianGroup a) Source # 
Instance details

Defined in Data.Group.Free.Internal

Ord a => Abelian (FreeAbelianGroup a) Source # 
Instance details

Defined in Data.Group.Free.Internal

Ord a => GroupOrder (FreeAbelianGroup a) Source # 
Instance details

Defined in Data.Group.Free.Internal

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

Bidirectional pattern synonym for the construction of FreeAbelianGroups.

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

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

runFreeAbelianGroup :: FreeAbelianGroup a -> Map a Integer Source #

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)]

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.