Copyright	(c) 2020-2021 Reed Mullanix Emily Pillmore
License	BSD-style
Maintainer	Reed Mullanix <reedmullanix@gmail.com>, Emily Pillmore <emilypi@cohomolo.gy>
Stability	stable
Portability	non-portable
Safe Haskell	Safe
Language	Haskell2010

Data.Group.Free.Church

Contents

Church-encoded free groups
- Church-encoded free group combinators
Church-encoded free abelian groups
- Church-encoded free abelian group combinators

Description

This module provides definitions for Church-encoded FreeGroups, FreeAbelianGroups, along with useful combinators.

Synopsis

newtype FG a = FG {
- runFG :: forall g. Group g => (a -> g) -> g
}
interpretFG :: Group g => FG g -> g
reifyFG :: FG a -> FreeGroup a
reflectFG :: FreeGroup a -> FG a
presentFG :: Group g => FG g -> (FG g -> g) -> g
newtype FA a = FA {
- runFA :: forall g. Abelian g => (a -> Integer -> g) -> g
}
forgetFA :: Ord a => FA a -> FG a
interpretFA :: Abelian g => FA g -> g
reifyFA :: Ord a => FA a -> FreeAbelianGroup a
reflectFA :: FreeAbelianGroup a -> FA a

Church-encoded free groups

newtype FG a Source #

The Church-encoding of a FreeGroup.

This datatype represents the "true" free group in Haskell on some a-valued generators. For more information on why this encoding is preferred, see Dan Doel's article in the Comonad Reader.

While FreeGroup et al are free in a strict language, and are more intuitive, they are not associative wtih respect to bottoms. FG and FA however, are, and should be preferred when working with possibly undefined data.

Constructors

FG
Fields runFG :: forall g. Group g => (a -> g) -> g

Instances

Instances details

Monad FG Source #
Instance details Defined in Data.Group.Free.Church Methods (>>=) :: FG a -> (a -> FG b) -> FG b # (>>) :: FG a -> FG b -> FG b # return :: a -> FG a #
Functor FG Source #
Instance details Defined in Data.Group.Free.Church Methods fmap :: (a -> b) -> FG a -> FG b # (<$) :: a -> FG b -> FG a #
Applicative FG Source #
Instance details Defined in Data.Group.Free.Church Methods pure :: a -> FG a # (<>) :: FG (a -> b) -> FG a -> FG b # liftA2 :: (a -> b -> c) -> FG a -> FG b -> FG c # (>) :: FG a -> FG b -> FG b # (<*) :: FG a -> FG b -> FG a #
Alternative FG Source #
Instance details Defined in Data.Group.Free.Church Methods empty :: FG a # (<\|>) :: FG a -> FG a -> FG a # some :: FG a -> FG [a] # many :: FG a -> FG [a] #
Cancellative FG Source #
Instance details Defined in Control.Applicative.Cancellative Methods cancel :: FG a -> FG a Source #
GroupFoldable FG Source #
Instance details Defined in Data.Group.Foldable Methods goldMap :: Group g => (a -> g) -> FG a -> g Source # toFG :: FG a -> FG a Source #
Semigroup (FG a) Source #
Instance details Defined in Data.Group.Free.Church Methods (<>) :: FG a -> FG a -> FG a # sconcat :: NonEmpty (FG a) -> FG a # stimes :: Integral b => b -> FG a -> FG a #
Monoid (FG a) Source #
Instance details Defined in Data.Group.Free.Church Methods mempty :: FG a # mappend :: FG a -> FG a -> FG a # mconcat :: [FG a] -> FG a #
Group (FG a) Source #
Instance details Defined in Data.Group.Free.Church Methods invert :: FG a -> FG a # (~~) :: FG a -> FG a -> FG a # pow :: Integral x => FG a -> x -> FG a #

Church-encoded free group combinators

interpretFG :: Group g => FG g -> g Source #

Interpret a Church-encoded free group as a concrete FreeGroup.

reifyFG :: FG a -> FreeGroup a Source #

Convert a Church-encoded free group to a concrete FreeGroup.

reflectFG :: FreeGroup a -> FG a Source #

Convert a concrete FreeGroup to a Church-encoded free group.

presentFG :: Group g => FG g -> (FG g -> g) -> g Source #

Present a Group as a FG modulo relations.

Church-encoded free abelian groups

newtype FA a Source #

The Church-encoding of a FreeAbelianGroup.

This datatype represents the free group on some a-valued generators, along with their exponents in the group.

Constructors

FA
Fields runFA :: forall g. Abelian g => (a -> Integer -> g) -> g

Instances

Instances details

Monad FA Source #
Instance details Defined in Data.Group.Free.Church Methods (>>=) :: FA a -> (a -> FA b) -> FA b # (>>) :: FA a -> FA b -> FA b # return :: a -> FA a #
Functor FA Source #
Instance details Defined in Data.Group.Free.Church Methods fmap :: (a -> b) -> FA a -> FA b # (<$) :: a -> FA b -> FA a #
Applicative FA Source #
Instance details Defined in Data.Group.Free.Church Methods pure :: a -> FA a # (<>) :: FA (a -> b) -> FA a -> FA b # liftA2 :: (a -> b -> c) -> FA a -> FA b -> FA c # (>) :: FA a -> FA b -> FA b # (<*) :: FA a -> FA b -> FA a #
Alternative FA Source #
Instance details Defined in Data.Group.Free.Church Methods empty :: FA a # (<\|>) :: FA a -> FA a -> FA a # some :: FA a -> FA [a] # many :: FA a -> FA [a] #
Cancellative FA Source #
Instance details Defined in Control.Applicative.Cancellative Methods cancel :: FA a -> FA a Source #
Semigroup (FA a) Source #
Instance details Defined in Data.Group.Free.Church Methods (<>) :: FA a -> FA a -> FA a # sconcat :: NonEmpty (FA a) -> FA a # stimes :: Integral b => b -> FA a -> FA a #
Monoid (FA a) Source #
Instance details Defined in Data.Group.Free.Church Methods mempty :: FA a # mappend :: FA a -> FA a -> FA a # mconcat :: [FA a] -> FA a #
Group (FA a) Source #
Instance details Defined in Data.Group.Free.Church Methods invert :: FA a -> FA a # (~~) :: FA a -> FA a -> FA a # pow :: Integral x => FA a -> x -> FA a #
Abelian (FA a) Source #
Instance details Defined in Data.Group.Free.Church

Church-encoded free abelian group combinators

forgetFA :: Ord a => FA a -> FG a Source #

Forget the commutative structure of a Church-encoded free abelian group, turning it into a standard free group.

interpretFA :: Abelian g => FA g -> g Source #

Interpret a Church-encoded free abelian group as a concrete FreeAbelianGroup.

reifyFA :: Ord a => FA a -> FreeAbelianGroup a Source #

Convert a Church-encoded free abelian group to a concrete FreeAbelianGroup.

reflectFA :: FreeAbelianGroup a -> FA a Source #

Convert a concrete FreeAbelianGroup to a Church-encoded free abelian group.