Copyright	(c) 2020 Reed Mullanix Emily Pillmore
License	BSD-style
Maintainer	Reed Mullanix <reedmullanix@gmail.com>, Emily Pillmore <emilypi@cohomolo.gy>
Stability	stable
Portability	non-portable
Safe Haskell	Safe
Language	Haskell2010

Data.Group.Free

Contents

Free groups
- Free group combinators
Free abelian groups
- Free abelian group combinators

Description

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

Synopsis

newtype FreeGroup a = FreeGroup {
- runFreeGroup :: [Either a a]
}
simplify :: Eq a => FreeGroup a -> FreeGroup a
interpret :: Group g => FreeGroup g -> g
interpret' :: Group g => FreeGroup g -> g
present :: Group g => FreeGroup g -> (FreeGroup g -> g) -> g
newtype FreeAbelianGroup a = FreeAbelianGroup {
- runFreeAbelian :: Map a Int
}
abmap :: Ord b => (a -> b) -> FreeAbelianGroup a -> FreeAbelianGroup b
abjoin :: Ord a => FreeAbelianGroup (FreeAbelianGroup a) -> FreeAbelianGroup a
singleton :: a -> FreeAbelianGroup a
abInterpret :: Group g => FreeAbelianGroup g -> g

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 runFreeGroup :: [Either a a]

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] #
Cancelative FreeGroup Source #
Instance details Defined in Control.Applicative.Cancelative 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 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) Source #
Instance details Defined in Data.Group.Free Methods showsPrec :: Int -> FreeGroup a -> ShowS # show :: FreeGroup a -> String # showList :: [FreeGroup a] -> ShowS #
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 Methods mempty :: FreeGroup a # mappend :: FreeGroup a -> FreeGroup a -> FreeGroup a # mconcat :: [FreeGroup a] -> FreeGroup a #
Group (FreeGroup a) Source #
Instance details Defined in Data.Group.Free Methods invert :: FreeGroup a -> FreeGroup a Source # gtimes :: Integral n => n -> FreeGroup a -> FreeGroup a Source # minus :: FreeGroup a -> FreeGroup a -> FreeGroup a 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

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

Constructors

FreeAbelianGroup
Fields runFreeAbelian :: Map a Int

Instances

Instances details

Eq a => Eq (FreeAbelianGroup a) Source #
Instance details Defined in Data.Group.Free Methods (==) :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool # (/=) :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool #
Ord a => Ord (FreeAbelianGroup a) Source #
Instance details 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) Source #
Instance details Defined in Data.Group.Free Methods showsPrec :: Int -> FreeAbelianGroup a -> ShowS # show :: FreeAbelianGroup a -> String # showList :: [FreeAbelianGroup a] -> ShowS #
Ord a => Semigroup (FreeAbelianGroup a) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details Defined in Data.Group.Free Methods invert :: FreeAbelianGroup a -> FreeAbelianGroup a Source # gtimes :: Integral n => n -> FreeAbelianGroup a -> FreeAbelianGroup a Source # minus :: FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a Source #

Free abelian group combinators

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

Functorial fmap for a FreeAbelianGroup.

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

Monadic join for a FreeAbelianGroup.

singleton :: a -> FreeAbelianGroup a Source #

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

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

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