Safe Haskell	Safe
Language	Haskell2010

Data.Group.Free

Description

Free groups

Synopsis

data FreeGroup a
fromDList :: Eq a => DList (Either a a) -> FreeGroup a
toDList :: FreeGroup a -> DList (Either a a)
normalize :: Eq a => DList (Either a a) -> DList (Either a a)
data FreeGroupL a
consL :: Eq a => Either a a -> FreeGroupL a -> FreeGroupL a
fromList :: Eq a => [Either a a] -> FreeGroupL a
toList :: FreeGroupL a -> [Either a a]
normalizeL :: Eq a => [Either a a] -> [Either a a]

Documentation

data FreeGroup a Source #

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 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 # fail :: String -> 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 #
FreeAlgebra FreeGroup Source #
Instance details Defined in Data.Group.Free Methods returnFree :: a -> FreeGroup a Source # foldMapFree :: (AlgebraType FreeGroup d, AlgebraType0 FreeGroup a) => (a -> d) -> FreeGroup a -> d Source # codom :: AlgebraType0 FreeGroup a => Proof (AlgebraType FreeGroup (FreeGroup a)) (FreeGroup a) Source # forget :: AlgebraType FreeGroup a => Proof (AlgebraType0 FreeGroup a) (FreeGroup 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 #
Eq a => 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 #
Eq 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 #
Eq a => Group (FreeGroup a) Source #
Instance details Defined in Data.Group.Free Methods invert :: FreeGroup a -> FreeGroup a # pow :: Integral x => FreeGroup a -> x -> FreeGroup a #
type AlgebraType0 FreeGroup (a :: Type) Source #
Instance details Defined in Data.Group.Free type AlgebraType0 FreeGroup (a :: Type) = Eq a
type AlgebraType FreeGroup (g :: Type) Source #
Instance details Defined in Data.Group.Free type AlgebraType FreeGroup (g :: Type) = (Eq g, Group g)

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

Smart constructor which normalizes a dlist.

Complexity: O(n)

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

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

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

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

undefined <> a = undefined

Instances

FreeAlgebra FreeGroupL Source #
Instance details Defined in Data.Group.Free Methods returnFree :: a -> FreeGroupL a Source # foldMapFree :: (AlgebraType FreeGroupL d, AlgebraType0 FreeGroupL a) => (a -> d) -> FreeGroupL a -> d Source # codom :: AlgebraType0 FreeGroupL a => Proof (AlgebraType FreeGroupL (FreeGroupL a)) (FreeGroupL a) Source # forget :: AlgebraType FreeGroupL a => Proof (AlgebraType0 FreeGroupL a) (FreeGroupL a) Source #
Eq a => Eq (FreeGroupL a) Source #
Instance details Defined in Data.Group.Free Methods (==) :: FreeGroupL a -> FreeGroupL a -> Bool # (/=) :: FreeGroupL a -> FreeGroupL a -> Bool #
Ord a => Ord (FreeGroupL a) Source #
Instance details 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) Source #
Instance details Defined in Data.Group.Free Methods showsPrec :: Int -> FreeGroupL a -> ShowS # show :: FreeGroupL a -> String # showList :: [FreeGroupL a] -> ShowS #
Eq a => Semigroup (FreeGroupL a) Source #
Instance details 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) Source #
Instance details 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) Source #
Instance details Defined in Data.Group.Free Methods invert :: FreeGroupL a -> FreeGroupL a # pow :: Integral x => FreeGroupL a -> x -> FreeGroupL a #
type AlgebraType0 FreeGroupL (a :: Type) Source #
Instance details Defined in Data.Group.Free type AlgebraType0 FreeGroupL (a :: Type) = Eq a
type AlgebraType FreeGroupL (g :: Type) Source #
Instance details Defined in Data.Group.Free type AlgebraType FreeGroupL (g :: Type) = (Eq g, Group g)

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

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

Smart constructor which normalizes a list.

Complexity: O(n)

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

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

Like normalize but for lists.

Complexity: O(n)