free-algebras-0.0.4.0: Free algebras in Haskell.

Safe Haskell Safe Haskell2010

Data.Group.Free

Synopsis

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

Instances
 Source # Instance detailsDefined 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 # Source # Instance detailsDefined in Data.Group.Free Methodsfmap :: (a -> b) -> FreeGroup a -> FreeGroup b #(<\$) :: a -> FreeGroup b -> FreeGroup a # Source # Instance detailsDefined in Data.Group.Free Methodspure :: 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 # Source # Instance detailsDefined in Data.Group.Free MethodsreturnFree :: a -> FreeGroup a Source #foldMapFree :: (AlgebraType FreeGroup d, AlgebraType0 FreeGroup a) => (a -> d) -> FreeGroup a -> d Source # Eq a => Eq (FreeGroup a) Source # Instance detailsDefined in Data.Group.Free Methods(==) :: FreeGroup a -> FreeGroup a -> Bool #(/=) :: FreeGroup a -> FreeGroup a -> Bool # Ord a => Ord (FreeGroup a) Source # Instance detailsDefined in Data.Group.Free Methodscompare :: 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 detailsDefined in Data.Group.Free MethodsshowsPrec :: Int -> FreeGroup a -> ShowS #show :: FreeGroup a -> String #showList :: [FreeGroup a] -> ShowS # Eq a => Semigroup (FreeGroup a) Source # Instance detailsDefined 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 detailsDefined in Data.Group.Free Methodsmappend :: FreeGroup a -> FreeGroup a -> FreeGroup a #mconcat :: [FreeGroup a] -> FreeGroup a # Eq a => Group (FreeGroup a) Source # Instance detailsDefined in Data.Group.Free Methodsinvert :: FreeGroup a -> FreeGroup a #pow :: Integral x => FreeGroup a -> x -> FreeGroup a # type AlgebraType0 FreeGroup (a :: *) Source # Instance detailsDefined in Data.Group.Free type AlgebraType0 FreeGroup (a :: *) = Eq a type AlgebraType FreeGroup (g :: *) Source # Instance detailsDefined in Data.Group.Free type AlgebraType FreeGroup (g :: *) = (Eq g, Group g)

fromList :: Eq a => [Either a a] -> FreeGroup a Source #

Smart constructor which normalizes a list.

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

Normalize a list, i.e. remove adjusten inverses from a word, i.e. ab⁻¹ba⁻¹c = c

Complexity: O(n)