Data.Group.Free

Free groups

• https://en.wikipedia.org/wiki/Free_group
• https://ncatlab.org/nlab/show/Nielsen-Schreier+theorem

Documentation

data FreeGroup a

Free group generated by a type a. Internally it's represented by a list [Either a a] where inverse is given by:

 inverse (FreeGroup [a]) = FreeGroup [either Right Left a]

It is a monad on a full subcategory of Hask which constists of types which satisfy the Eq constraint.

FreeGroup a is isomorphic with Free Group a (but the latter does not require Eq constraint, hence is more general).

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

FreeAlgebra FreeGroup

Defined in Data.Group.Free

Methods

returnFree :: a -> FreeGroup a

foldMapFree :: (AlgebraType FreeGroup d, AlgebraType0 FreeGroup a) => (a -> d) -> FreeGroup a -> d

codom :: AlgebraType0 FreeGroup a => Proof (AlgebraType FreeGroup (FreeGroup a)) (FreeGroup a)

forget :: AlgebraType FreeGroup a => Proof (AlgebraType0 FreeGroup a) (FreeGroup 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

Eq a => 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

Eq 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

Eq a => Group (FreeGroup a)

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

type AlgebraType0 FreeGroup (a :: Type)

Defined in Data.Group.Free

type AlgebraType0 FreeGroup (a :: Type) = Eq a

type AlgebraType FreeGroup (g :: Type)

Defined in Data.Group.Free

type AlgebraType FreeGroup (g :: Type) = (Eq g, Group g)

fromDList :: Eq a => DList (Either a a) -> FreeGroup a

Smart constructor which normalizes a dlist.

Complexity: O(n)

toDList :: FreeGroup a -> DList (Either a a)

normalize :: Eq a => DList (Either a a) -> DList (Either a a)

Normalize a Dlist, i.e. remove adjacent inverses from a word, i.e. ab⁻¹ba⁻¹c = c. Note that this function is implemented using normalizeL, implemnting it directly on DLists would be O(n^2) instead of O(n).

Complexity: O(n)

data FreeGroupL a

Free group in the class of groups which multiplication is strict on the left, i.e.

undefined <> a = undefined

Instances

FreeAlgebra FreeGroupL

Defined in Data.Group.Free

Methods

returnFree :: a -> FreeGroupL a

foldMapFree :: (AlgebraType FreeGroupL d, AlgebraType0 FreeGroupL a) => (a -> d) -> FreeGroupL a -> d

codom :: AlgebraType0 FreeGroupL a => Proof (AlgebraType FreeGroupL (FreeGroupL a)) (FreeGroupL a)

forget :: AlgebraType FreeGroupL a => Proof (AlgebraType0 FreeGroupL a) (FreeGroupL a)

Eq a => Eq (FreeGroupL a)

Defined in Data.Group.Free

Methods

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

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

Ord a => Ord (FreeGroupL a)

Defined in Data.Group.Free

Methods

compare :: FreeGroupL a -> FreeGroupL a -> Ordering

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

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

(>) :: FreeGroupL a -> FreeGroupL a -> Bool

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

max :: FreeGroupL a -> FreeGroupL a -> FreeGroupL a

min :: FreeGroupL a -> FreeGroupL a -> FreeGroupL a

Show a => Show (FreeGroupL a)

Defined in Data.Group.Free

Methods

showsPrec :: Int -> FreeGroupL a -> ShowS

show :: FreeGroupL a -> String

showList :: [FreeGroupL a] -> ShowS

Eq a => Semigroup (FreeGroupL a)

Defined in Data.Group.Free

Methods

(<>) :: FreeGroupL a -> FreeGroupL a -> FreeGroupL a

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

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

Eq a => Monoid (FreeGroupL a)

Defined in Data.Group.Free

Methods

mempty :: FreeGroupL a

mappend :: FreeGroupL a -> FreeGroupL a -> FreeGroupL a

mconcat :: [FreeGroupL a] -> FreeGroupL a

Eq a => Group (FreeGroupL a)

Defined in Data.Group.Free

Methods

invert :: FreeGroupL a -> FreeGroupL a

(~~) :: FreeGroupL a -> FreeGroupL a -> FreeGroupL a

pow :: Integral x => FreeGroupL a -> x -> FreeGroupL a

type AlgebraType0 FreeGroupL (a :: Type)

Defined in Data.Group.Free

type AlgebraType0 FreeGroupL (a :: Type) = Eq a

type AlgebraType FreeGroupL (g :: Type)

Defined in Data.Group.Free

type AlgebraType FreeGroupL (g :: Type) = (Eq g, Group g)

consL :: Eq a => Either a a -> FreeGroupL a -> FreeGroupL a

Cons a generator (Right x) or its inverse (Left x) to the left hand side of a FreeGroupL.

Complexity: O(1)

fromList :: Eq a => [Either a a] -> FreeGroupL a

Smart constructor which normalizes a list.

Complexity: O(n)

toList :: FreeGroupL a -> [Either a a]

normalizeL :: Eq a => [Either a a] -> [Either a a]

Like normalize but for lists.

Complexity: O(n)