Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
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
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
constraint.Eq
is isomorphic with FreeGroup
a
(but the latter does not
require Free
Group aEq
constraint, hence is more general).
Instances
Applicative FreeGroup Source # | |
Functor FreeGroup Source # | |
Monad FreeGroup Source # | |
FreeAlgebra FreeGroup Source # | |
Defined in Data.Group.Free 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 => Monoid (FreeGroup a) Source # | |
Eq a => Semigroup (FreeGroup a) Source # | |
Show a => Show (FreeGroup a) Source # | |
Eq a => Eq (FreeGroup a) Source # | |
Ord a => Ord (FreeGroup a) Source # | |
Defined in Data.Group.Free | |
Eq a => Group (FreeGroup a) Source # | |
type AlgebraType FreeGroup (g :: Type) Source # | |
Defined in Data.Group.Free | |
type AlgebraType0 FreeGroup (a :: Type) Source # | |
Defined in Data.Group.Free |
fromDList :: Eq a => DList (Either a a) -> FreeGroup a Source #
Smart constructor which normalizes a dlist.
Complexity: O(n)
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
, implemnting it directly on normalizeL
DList
s 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
consL :: Eq a => Either a a -> FreeGroupL a -> FreeGroupL a Source #
Cons a generator (
) or its inverse (Right
x
) to the left
hand side of a Left
xFreeGroupL
.
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 #