Safe Haskell | None |
---|---|

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

constraint, hence is more general).

#### Instances

Monad FreeGroup Source # | |

Functor FreeGroup Source # | |

Applicative 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 => Eq (FreeGroup a) Source # | |

Ord a => Ord (FreeGroup a) Source # | |

Defined in Data.Group.Free | |

Show a => Show (FreeGroup a) Source # | |

Eq a => Semigroup (FreeGroup a) Source # | |

Eq a => Monoid (FreeGroup a) Source # | |

Eq a => Group (FreeGroup a) Source # | |

type AlgebraType0 FreeGroup (a :: Type) Source # | |

Defined in Data.Group.Free | |

type AlgebraType FreeGroup (g :: 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`

x`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 #