Data.Group.Free

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

Free groups

newtype FreeGroup a

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

• runFreeGroup :: [Either a a]

Instances

Monad FreeGroup

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

Defined in Data.Group.Free

Methods

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

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

Applicative FreeGroup

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

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]

Cancelative FreeGroup

Defined in Control.Applicative.Cancelative

Methods

cancel :: FreeGroup a -> FreeGroup a

GroupFoldable FreeGroup

Defined in Data.Group.Foldable

Methods

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

toFG :: FreeGroup a -> FG a

Eq a => Eq (FreeGroup a)

Defined in Data.Group.Free

Methods

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

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

Ord a => Ord (FreeGroup a)

Defined in Data.Group.Free

Methods

compare :: 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)

Defined in Data.Group.Free

Methods

showsPrec :: Int -> FreeGroup a -> ShowS

show :: FreeGroup a -> String

showList :: [FreeGroup a] -> ShowS

Semigroup (FreeGroup a)

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)

Defined in Data.Group.Free

Methods

mempty :: FreeGroup a

mappend :: FreeGroup a -> FreeGroup a -> FreeGroup a

mconcat :: [FreeGroup a] -> FreeGroup a

Group (FreeGroup a)

Defined in Data.Group.Free

Methods

invert :: FreeGroup a -> FreeGroup a

gtimes :: Integral n => n -> FreeGroup a -> FreeGroup a

minus :: FreeGroup a -> FreeGroup a -> FreeGroup a

Free group combinators

simplify :: Eq a => FreeGroup a -> FreeGroup a

O(n) Simplifies a word in a free group.

Examples:

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

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

O(n) Strict variant of interpret.

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

Present a Group as a FreeGroup modulo relations.

Free abelian groups

newtype FreeAbelianGroup a

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.

Constructors

FreeAbelianGroup

Fields

• runFreeAbelian :: Map a Int

Instances

Eq a => Eq (FreeAbelianGroup a)

Defined in Data.Group.Free

Methods

(==) :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool

(/=) :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool

Ord a => Ord (FreeAbelianGroup a)

Defined in Data.Group.Free

Methods

compare :: FreeAbelianGroup a -> FreeAbelianGroup a -> Ordering

(<) :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool

(<=) :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool

(>) :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool

(>=) :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool

max :: FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a

min :: FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a

Show a => Show (FreeAbelianGroup a)

Defined in Data.Group.Free

Methods

showsPrec :: Int -> FreeAbelianGroup a -> ShowS

show :: FreeAbelianGroup a -> String

showList :: [FreeAbelianGroup a] -> ShowS

Ord a => Semigroup (FreeAbelianGroup a)

Defined in Data.Group.Free

Methods

(<>) :: FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a

sconcat :: NonEmpty (FreeAbelianGroup a) -> FreeAbelianGroup a

stimes :: Integral b => b -> FreeAbelianGroup a -> FreeAbelianGroup a

Ord a => Monoid (FreeAbelianGroup a)

Defined in Data.Group.Free

Methods

mempty :: FreeAbelianGroup a

mappend :: FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a

mconcat :: [FreeAbelianGroup a] -> FreeAbelianGroup a

Ord a => Group (FreeAbelianGroup a)

Defined in Data.Group.Free

Methods

invert :: FreeAbelianGroup a -> FreeAbelianGroup a

gtimes :: Integral n => n -> FreeAbelianGroup a -> FreeAbelianGroup a

minus :: FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a

Free abelian group combinators

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

Functorial fmap for a FreeAbelianGroup.

abjoin :: Ord a => FreeAbelianGroup (FreeAbelianGroup a) -> FreeAbelianGroup a

Monadic join for a FreeAbelianGroup.

singleton :: a -> FreeAbelianGroup a

Lift a singular value into a FreeAbelianGroup. Analogous to pure.

abInterpret :: Group g => FreeAbelianGroup g -> g

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