{-# language Safe #-}
-- |
-- Module       : Data.Group
-- Copyright    : (c) 2020 Reed Mullanix, Emily Pillmore
-- License      : BSD-style
--
-- Maintainer   : Reed Mullanix <reedmullanix@gmail.com>,
--                Emily Pillmore <emilypi@cohomolo.gy>
--
-- Stability    : stable
-- Portability  : non-portable
--
-- This module provides definitions for 'FreeGroup's and 'FreeAbelianGroup's,
-- along with useful combinators.
--
module Data.Group.Free
( -- * Free groups
  FreeGroup(..)
  -- ** Free group combinators
, simplify
, interpret
, interpret'
, present
  -- * Free abelian groups
, FreeAbelianGroup(..)
  -- ** Free abelian group combinators
, abmap
, abjoin
, singleton
, abInterpret
) where

import Control.Applicative
import Control.Monad

import Data.Bifunctor
import Data.List (foldl')
import Data.Map (Map)
import qualified Data.Map.Strict as Map
import Data.Group

-- $setup
--
-- >>> import qualified Prelude
-- >>> import Data.Group
-- >>> import Data.Monoid
-- >>> import Data.Semigroup
-- >>> import Data.Word
-- >>> :set -XTypeApplications
-- >>> :set -XFlexibleContexts

-- | A representation of a free group over an alphabet @a@.
--
-- The intuition here is that @Left a@ represents a "negative" @a@,
-- whereas @Right a@ represents "positive" @a@.
--
-- __Note:__ This does not perform simplification upon multiplication or construction.
-- To do this, one should use 'simplify'.
--
newtype FreeGroup a = FreeGroup { FreeGroup a -> [Either a a]
runFreeGroup :: [Either a a] }
    deriving (Int -> FreeGroup a -> ShowS
[FreeGroup a] -> ShowS
FreeGroup a -> String
(Int -> FreeGroup a -> ShowS)
-> (FreeGroup a -> String)
-> ([FreeGroup a] -> ShowS)
-> Show (FreeGroup a)
forall a. Show a => Int -> FreeGroup a -> ShowS
forall a. Show a => [FreeGroup a] -> ShowS
forall a. Show a => FreeGroup a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [FreeGroup a] -> ShowS
$cshowList :: forall a. Show a => [FreeGroup a] -> ShowS
show :: FreeGroup a -> String
$cshow :: forall a. Show a => FreeGroup a -> String
showsPrec :: Int -> FreeGroup a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> FreeGroup a -> ShowS
Show, FreeGroup a -> FreeGroup a -> Bool
(FreeGroup a -> FreeGroup a -> Bool)
-> (FreeGroup a -> FreeGroup a -> Bool) -> Eq (FreeGroup a)
forall a. Eq a => FreeGroup a -> FreeGroup a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FreeGroup a -> FreeGroup a -> Bool
$c/= :: forall a. Eq a => FreeGroup a -> FreeGroup a -> Bool
== :: FreeGroup a -> FreeGroup a -> Bool
$c== :: forall a. Eq a => FreeGroup a -> FreeGroup a -> Bool
Eq, Eq (FreeGroup a)
Eq (FreeGroup a)
-> (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)
-> (FreeGroup a -> FreeGroup a -> FreeGroup a)
-> (FreeGroup a -> FreeGroup a -> FreeGroup a)
-> Ord (FreeGroup a)
FreeGroup a -> FreeGroup a -> Bool
FreeGroup a -> FreeGroup a -> Ordering
FreeGroup a -> FreeGroup a -> FreeGroup a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (FreeGroup a)
forall a. Ord a => FreeGroup a -> FreeGroup a -> Bool
forall a. Ord a => FreeGroup a -> FreeGroup a -> Ordering
forall a. Ord a => FreeGroup a -> FreeGroup a -> FreeGroup a
min :: FreeGroup a -> FreeGroup a -> FreeGroup a
$cmin :: forall a. Ord a => FreeGroup a -> FreeGroup a -> FreeGroup a
max :: FreeGroup a -> FreeGroup a -> FreeGroup a
$cmax :: forall a. Ord a => FreeGroup a -> FreeGroup a -> FreeGroup a
>= :: FreeGroup a -> FreeGroup a -> Bool
$c>= :: forall a. Ord a => FreeGroup a -> FreeGroup a -> Bool
> :: FreeGroup a -> FreeGroup a -> Bool
$c> :: forall a. Ord a => FreeGroup a -> FreeGroup a -> Bool
<= :: FreeGroup a -> FreeGroup a -> Bool
$c<= :: forall a. Ord a => FreeGroup a -> FreeGroup a -> Bool
< :: FreeGroup a -> FreeGroup a -> Bool
$c< :: forall a. Ord a => FreeGroup a -> FreeGroup a -> Bool
compare :: FreeGroup a -> FreeGroup a -> Ordering
$ccompare :: forall a. Ord a => FreeGroup a -> FreeGroup a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (FreeGroup a)
Ord)

instance Semigroup (FreeGroup a) where
    (FreeGroup [Either a a]
g) <> :: FreeGroup a -> FreeGroup a -> FreeGroup a
<> (FreeGroup [Either a a]
g') = [Either a a] -> FreeGroup a
forall a. [Either a a] -> FreeGroup a
FreeGroup ([Either a a]
g [Either a a] -> [Either a a] -> [Either a a]
forall a. [a] -> [a] -> [a]
++ [Either a a]
g')

instance Monoid (FreeGroup a) where
    mempty :: FreeGroup a
mempty = [Either a a] -> FreeGroup a
forall a. [Either a a] -> FreeGroup a
FreeGroup []

instance Group (FreeGroup a) where
    invert :: FreeGroup a -> FreeGroup a
invert (FreeGroup [Either a a]
g) = [Either a a] -> FreeGroup a
forall a. [Either a a] -> FreeGroup a
FreeGroup ([Either a a] -> FreeGroup a) -> [Either a a] -> FreeGroup a
forall a b. (a -> b) -> a -> b
$ (Either a a -> Either a a) -> [Either a a] -> [Either a a]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Either a a -> Either a a
forall a. Either a a -> Either a a
inv [Either a a]
g
        where
          inv :: Either a a -> Either a a
          inv :: Either a a -> Either a a
inv (Left a
a) = a -> Either a a
forall a b. b -> Either a b
Right a
a
          inv (Right a
a) = a -> Either a a
forall a b. a -> Either a b
Left a
a

instance Functor FreeGroup where
    fmap :: (a -> b) -> FreeGroup a -> FreeGroup b
fmap a -> b
f (FreeGroup [Either a a]
g) = [Either b b] -> FreeGroup b
forall a. [Either a a] -> FreeGroup a
FreeGroup ([Either b b] -> FreeGroup b) -> [Either b b] -> FreeGroup b
forall a b. (a -> b) -> a -> b
$ (Either a a -> Either b b) -> [Either a a] -> [Either b b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> (a -> b) -> Either a a -> Either b b
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap a -> b
f a -> b
f) [Either a a]
g

instance Applicative FreeGroup where
    pure :: a -> FreeGroup a
pure a
a = [Either a a] -> FreeGroup a
forall a. [Either a a] -> FreeGroup a
FreeGroup ([Either a a] -> FreeGroup a) -> [Either a a] -> FreeGroup a
forall a b. (a -> b) -> a -> b
$ Either a a -> [Either a a]
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Either a a -> [Either a a]) -> Either a a -> [Either a a]
forall a b. (a -> b) -> a -> b
$ a -> Either a a
forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a
    <*> :: FreeGroup (a -> b) -> FreeGroup a -> FreeGroup b
(<*>) = FreeGroup (a -> b) -> FreeGroup a -> FreeGroup b
forall (m :: * -> *) a b. Monad m => m (a -> b) -> m a -> m b
ap

instance Monad FreeGroup where
    return :: a -> FreeGroup a
return = a -> FreeGroup a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
    (FreeGroup [Either a a]
g) >>= :: FreeGroup a -> (a -> FreeGroup b) -> FreeGroup b
>>= a -> FreeGroup b
f = [Either b b] -> FreeGroup b
forall a. [Either a a] -> FreeGroup a
FreeGroup ([Either b b] -> FreeGroup b) -> [Either b b] -> FreeGroup b
forall a b. (a -> b) -> a -> b
$ (Either a a -> [Either b b]) -> [Either a a] -> [Either b b]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Either a a -> [Either b b]
go [Either a a]
g
        where
          go :: Either a a -> [Either b b]
go (Left a
a)  = FreeGroup b -> [Either b b]
forall a. FreeGroup a -> [Either a a]
runFreeGroup (FreeGroup b -> [Either b b]) -> FreeGroup b -> [Either b b]
forall a b. (a -> b) -> a -> b
$ FreeGroup b -> FreeGroup b
forall a. Group a => a -> a
invert (FreeGroup b -> FreeGroup b) -> FreeGroup b -> FreeGroup b
forall a b. (a -> b) -> a -> b
$ a -> FreeGroup b
f a
a
          go (Right a
a) = FreeGroup b -> [Either b b]
forall a. FreeGroup a -> [Either a a]
runFreeGroup (FreeGroup b -> [Either b b]) -> FreeGroup b -> [Either b b]
forall a b. (a -> b) -> a -> b
$ a -> FreeGroup b
f a
a

instance Alternative FreeGroup where
    empty :: FreeGroup a
empty = FreeGroup a
forall a. Monoid a => a
mempty
    <|> :: FreeGroup a -> FreeGroup a -> FreeGroup a
(<|>) = FreeGroup a -> FreeGroup a -> FreeGroup a
forall a. Semigroup a => a -> a -> a
(<>)

-- | /O(n)/ Simplifies a word in a free group.
--
-- === __Examples:__
--
-- >>> simplify $ FreeGroup [Right 'a', Left 'b', Right 'c', Left 'c', Right 'b', Right 'a']
-- FreeGroup {runFreeGroup = [Right 'a',Right 'a']}
--
simplify :: (Eq a) => FreeGroup a -> FreeGroup a
simplify :: FreeGroup a -> FreeGroup a
simplify (FreeGroup [Either a a]
g) = [Either a a] -> FreeGroup a
forall a. [Either a a] -> FreeGroup a
FreeGroup ([Either a a] -> FreeGroup a) -> [Either a a] -> FreeGroup a
forall a b. (a -> b) -> a -> b
$ (Either a a -> [Either a a] -> [Either a a])
-> [Either a a] -> [Either a a] -> [Either a a]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Either a a -> [Either a a] -> [Either a a]
forall a. Eq a => Either a a -> [Either a a] -> [Either a a]
go [] [Either a a]
g
    where
      go :: Either a a -> [Either a a] -> [Either a a]
go (Left a
a) ((Right a
a'):[Either a a]
as) | a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
a' = [Either a a]
as
      go (Right a
a) ((Left a
a'):[Either a a]
as) | a
a a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
a' = [Either a a]
as
      go Either a a
a [Either a a]
as = Either a a
aEither a a -> [Either a a] -> [Either a a]
forall a. a -> [a] -> [a]
:[Either a a]
as

-- | /O(n)/ Interpret a word in a free group over some group @g@ as an element in a group @g@.
--
interpret :: (Group g) => FreeGroup g -> g
interpret :: FreeGroup g -> g
interpret (FreeGroup [Either g g]
g) = (Either g g -> g -> g) -> g -> [Either g g] -> g
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr Either g g -> g -> g
forall a. Group a => Either a a -> a -> a
go g
forall a. Monoid a => a
mempty [Either g g]
g
    where
      go :: Either a a -> a -> a
go (Left a
a) a
acc  = a -> a
forall a. Group a => a -> a
invert a
a a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
acc
      go (Right a
a) a
acc = a
a a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
acc

-- | /O(n)/ Strict variant of 'interpret'.
--
interpret' :: (Group g) => FreeGroup g -> g
interpret' :: FreeGroup g -> g
interpret' (FreeGroup [Either g g]
g) = (g -> Either g g -> g) -> g -> [Either g g] -> g
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' g -> Either g g -> g
forall a. Group a => a -> Either a a -> a
go g
forall a. Monoid a => a
mempty [Either g g]
g
    where
      go :: a -> Either a a -> a
go a
acc (Left a
a) = a
acc a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a -> a
forall a. Group a => a -> a
invert a
a
      go a
acc (Right a
a) = a
acc a -> a -> a
forall a. Semigroup a => a -> a -> a
<> a
a

-- | Present a 'Group' as a 'FreeGroup' modulo relations.
--
present :: Group g => FreeGroup g -> (FreeGroup g -> g) -> g
present :: FreeGroup g -> (FreeGroup g -> g) -> g
present = ((FreeGroup g -> g) -> FreeGroup g -> g)
-> FreeGroup g -> (FreeGroup g -> g) -> g
forall a b c. (a -> b -> c) -> b -> a -> c
flip (FreeGroup g -> g) -> FreeGroup g -> g
forall a b. (a -> b) -> a -> b
($)
{-# inline present #-}

-- | A representation of a free abelian group over an alphabet @a@.
--
-- The intuition here is group elements correspond with their positive
-- or negative multiplicities, and as such are simplified by construction.
--
newtype FreeAbelianGroup a = FreeAbelianGroup { FreeAbelianGroup a -> Map a Int
runFreeAbelian :: Map a Int }
    deriving (Int -> FreeAbelianGroup a -> ShowS
[FreeAbelianGroup a] -> ShowS
FreeAbelianGroup a -> String
(Int -> FreeAbelianGroup a -> ShowS)
-> (FreeAbelianGroup a -> String)
-> ([FreeAbelianGroup a] -> ShowS)
-> Show (FreeAbelianGroup a)
forall a. Show a => Int -> FreeAbelianGroup a -> ShowS
forall a. Show a => [FreeAbelianGroup a] -> ShowS
forall a. Show a => FreeAbelianGroup a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [FreeAbelianGroup a] -> ShowS
$cshowList :: forall a. Show a => [FreeAbelianGroup a] -> ShowS
show :: FreeAbelianGroup a -> String
$cshow :: forall a. Show a => FreeAbelianGroup a -> String
showsPrec :: Int -> FreeAbelianGroup a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> FreeAbelianGroup a -> ShowS
Show, FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
(FreeAbelianGroup a -> FreeAbelianGroup a -> Bool)
-> (FreeAbelianGroup a -> FreeAbelianGroup a -> Bool)
-> Eq (FreeAbelianGroup a)
forall a. Eq a => FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
$c/= :: forall a. Eq a => FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
== :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
$c== :: forall a. Eq a => FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
Eq, Eq (FreeAbelianGroup a)
Eq (FreeAbelianGroup a)
-> (FreeAbelianGroup a -> FreeAbelianGroup a -> Ordering)
-> (FreeAbelianGroup a -> FreeAbelianGroup a -> Bool)
-> (FreeAbelianGroup a -> FreeAbelianGroup a -> Bool)
-> (FreeAbelianGroup a -> FreeAbelianGroup a -> Bool)
-> (FreeAbelianGroup a -> FreeAbelianGroup a -> Bool)
-> (FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a)
-> (FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a)
-> Ord (FreeAbelianGroup a)
FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
FreeAbelianGroup a -> FreeAbelianGroup a -> Ordering
FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (FreeAbelianGroup a)
forall a. Ord a => FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
forall a.
Ord a =>
FreeAbelianGroup a -> FreeAbelianGroup a -> Ordering
forall a.
Ord a =>
FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a
min :: FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a
$cmin :: forall a.
Ord a =>
FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a
max :: FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a
$cmax :: forall a.
Ord a =>
FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a
>= :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
$c>= :: forall a. Ord a => FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
> :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
$c> :: forall a. Ord a => FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
<= :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
$c<= :: forall a. Ord a => FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
< :: FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
$c< :: forall a. Ord a => FreeAbelianGroup a -> FreeAbelianGroup a -> Bool
compare :: FreeAbelianGroup a -> FreeAbelianGroup a -> Ordering
$ccompare :: forall a.
Ord a =>
FreeAbelianGroup a -> FreeAbelianGroup a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (FreeAbelianGroup a)
Ord)

instance (Ord a) => Semigroup (FreeAbelianGroup a) where
    (FreeAbelianGroup Map a Int
g) <> :: FreeAbelianGroup a -> FreeAbelianGroup a -> FreeAbelianGroup a
<> (FreeAbelianGroup Map a Int
g') =
      Map a Int -> FreeAbelianGroup a
forall a. Map a Int -> FreeAbelianGroup a
FreeAbelianGroup (Map a Int -> FreeAbelianGroup a)
-> Map a Int -> FreeAbelianGroup a
forall a b. (a -> b) -> a -> b
$ (Int -> Int -> Int) -> Map a Int -> Map a Int -> Map a Int
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith Int -> Int -> Int
forall a. Num a => a -> a -> a
(+) Map a Int
g Map a Int
g'

instance (Ord a) => Monoid (FreeAbelianGroup a) where
    mempty :: FreeAbelianGroup a
mempty = Map a Int -> FreeAbelianGroup a
forall a. Map a Int -> FreeAbelianGroup a
FreeAbelianGroup Map a Int
forall a. Monoid a => a
mempty

instance (Ord a) => Group (FreeAbelianGroup a) where
    invert :: FreeAbelianGroup a -> FreeAbelianGroup a
invert (FreeAbelianGroup Map a Int
g) = Map a Int -> FreeAbelianGroup a
forall a. Map a Int -> FreeAbelianGroup a
FreeAbelianGroup (Map a Int -> FreeAbelianGroup a)
-> Map a Int -> FreeAbelianGroup a
forall a b. (a -> b) -> a -> b
$ (Int -> Int) -> Map a Int -> Map a Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Int -> Int
forall a. Num a => a -> a
negate Map a Int
g

-- NOTE: We can't implement Functor/Applicative/Monad here
-- due to the Ord constraint. C'est La Vie!

-- | Functorial 'fmap' for a 'FreeAbelianGroup'.
--
abmap :: (Ord b) => (a -> b) -> FreeAbelianGroup a -> FreeAbelianGroup b
abmap :: (a -> b) -> FreeAbelianGroup a -> FreeAbelianGroup b
abmap a -> b
f (FreeAbelianGroup Map a Int
g) = Map b Int -> FreeAbelianGroup b
forall a. Map a Int -> FreeAbelianGroup a
FreeAbelianGroup (Map b Int -> FreeAbelianGroup b)
-> Map b Int -> FreeAbelianGroup b
forall a b. (a -> b) -> a -> b
$ (a -> b) -> Map a Int -> Map b Int
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeys a -> b
f Map a Int
g

-- | Lift a singular value into a 'FreeAbelianGroup'. Analogous to 'pure'.
--
singleton :: a -> FreeAbelianGroup a
singleton :: a -> FreeAbelianGroup a
singleton a
a = Map a Int -> FreeAbelianGroup a
forall a. Map a Int -> FreeAbelianGroup a
FreeAbelianGroup (Map a Int -> FreeAbelianGroup a)
-> Map a Int -> FreeAbelianGroup a
forall a b. (a -> b) -> a -> b
$ a -> Int -> Map a Int
forall k a. k -> a -> Map k a
Map.singleton a
a Int
1

-- | Monadic 'join' for a 'FreeAbelianGroup'.
--
abjoin :: (Ord a) => FreeAbelianGroup (FreeAbelianGroup a) -> FreeAbelianGroup a
abjoin :: FreeAbelianGroup (FreeAbelianGroup a) -> FreeAbelianGroup a
abjoin (FreeAbelianGroup Map (FreeAbelianGroup a) Int
g) = Map a Int -> FreeAbelianGroup a
forall a. Map a Int -> FreeAbelianGroup a
FreeAbelianGroup (Map a Int -> FreeAbelianGroup a)
-> Map a Int -> FreeAbelianGroup a
forall a b. (a -> b) -> a -> b
$ (FreeAbelianGroup a -> Int -> Map a Int)
-> Map (FreeAbelianGroup a) Int -> Map a Int
forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
Map.foldMapWithKey FreeAbelianGroup a -> Int -> Map a Int
forall a. FreeAbelianGroup a -> Int -> Map a Int
go Map (FreeAbelianGroup a) Int
g
    where
      go :: FreeAbelianGroup a -> Int -> Map a Int
go (FreeAbelianGroup Map a Int
g') Int
n = (Int -> Int) -> Map a Int -> Map a Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
n) Map a Int
g'

-- | Interpret a free group as a word in the underlying group @g@.
--
abInterpret :: (Group g) => FreeAbelianGroup g -> g
abInterpret :: FreeAbelianGroup g -> g
abInterpret (FreeAbelianGroup Map g Int
g) = (g -> Int -> g) -> Map g Int -> g
forall m k a. Monoid m => (k -> a -> m) -> Map k a -> m
Map.foldMapWithKey ((Int -> g -> g) -> g -> Int -> g
forall a b c. (a -> b -> c) -> b -> a -> c
flip Int -> g -> g
forall a n. (Group a, Integral n) => n -> a -> a
gtimes) Map g Int
g