```-- Copyright (c) 2010-2012, David Amos. All rights reserved.

{-# LANGUAGE  MultiParamTypeClasses, FlexibleInstances, TypeSynonymInstances #-}
-- ScopedTypeVariables

-- |A module for doing arithmetic in the group algebra.
--
-- Group elements are represented as permutations of the integers, and are entered and displayed
-- using a Haskell-friendly version of cycle notation. For example, the permutation (1 2 3)(4 5)
-- would be entered as @p [[1,2,3],[4,5]]@, and displayed as [[1,2,3],[4,5]].
--
-- Given a field K and group G, the group algebra KG is the free K-vector space over the elements of G.
-- Elements of the group algebra consists of arbitrary K-linear combinations of elements of G.
-- For example, @p [[1,2,3]] + 2 * p [[1,2],[3,4]]@
module Math.Algebras.GroupAlgebra where

import Math.Core.Field
import Math.Core.Utils

import Math.Algebras.VectorSpace
import Math.Algebras.TensorProduct
import Math.Algebras.Structures

import Math.Algebra.Group.PermutationGroup hiding (p, action)
import qualified Math.Algebra.Group.PermutationGroup as P

import Math.Algebra.LinearAlgebra hiding (inverse, (*>) )

import Math.CommutativeAlgebra.Polynomial
import Math.CommutativeAlgebra.GroebnerBasis

instance Mon (Permutation Int) where
munit = 1
mmult = (*)

type GroupAlgebra k = Vect k (Permutation Int)

-- Monoid Algebra instance
instance (Eq k, Num k) => Algebra k (Permutation Int) where
unit 0 = zero -- V []
unit x = V [(munit,x)]
mult = nf . fmap (\(a,b) -> a `mmult` b)

-- Set Coalgebra instance
-- instance SetCoalgebra (Permutation Int) where {}

instance (Eq k, Num k) => Coalgebra k (Permutation Int) where
counit (V ts) = sum [x | (m,x) <- ts] -- trace
comult = fmap (\m -> (m,m)) -- diagonal

instance (Eq k, Num k) => Bialgebra k (Permutation Int) where {}
-- should check that the algebra and coalgebra structures are compatible

instance (Eq k, Num k) => HopfAlgebra k (Permutation Int) where
antipode (V ts) = nf \$ V [(g^-1,x) | (g,x) <- ts]

-- |Construct a permutation, as an element of the group algebra, from a list of cycles.
-- For example, @p [[1,2],[3,4,5]]@ constructs the permutation (1 2)(3 4 5), which is displayed
-- as [[1,2],[3,4,5]].
p :: [[Int]] -> GroupAlgebra Q
p cs = return \$ P.p cs

instance (Eq k, Num k) => Module k (Permutation Int) Int where
action = nf . fmap (\(g,x) -> x .^ g)

-- r *> m = action (r `te` m)

newtype X a = X a deriving (Eq,Ord,Show)

-- Find the inverse of a group algebra element using Groebner basis techniques
-- This is overkill, but it was what I had to hand at first
inv x@(V ts) =
let gs = P.elts \$ map fst \$ terms x -- all elements in the group generated by the terms
cs = map (glexvar . X) gs
x' = V \$ map (\(g,c) -> (g, unit c)) ts
one = x' * (V \$ zip gs cs)
oneEquations = (coeff 1 one - 1) : [coeff g one - 0 | g <- tail gs]
zeroEquations = [coeff g one - 0 | g <- gs]
solution = gb oneEquations
in if solution == [1]
then Left (gb zeroEquations) -- it's a zero divisor
else Right solution
-- sum [-c *> p g | V [ (Glex (M 1 [(X g, 1)]), 1), (Glex (M 0 []), c) ] <- solution]
-- should extract the solution into a group algebra element, but having trouble getting types right

-- The following code can be made to work over an arbitrary field by uncommenting the commented code
-- However, we should then probably also change the signature of p to p :: Fractional k => [[Int]] -> GroupAlgebra k
-- instance Fractional k => HasInverses (GroupAlgebra k) where

-- |Note that the inverse of a group algebra element can only be efficiently calculated
-- if the group generated by the non-zero terms is very small (eg \<100 elements).
instance HasInverses (GroupAlgebra Q) where
inverse x@(V ts) =
let gs = P.elts \$ map fst \$ terms x -- all elements in the group generated by the terms
-- cs = map (var . X) gs :: [Vect k (Glex (X (Permutation Int)))]
cs = map (glexvar . X) gs
x' = V \$ map (\(g,c) -> (g, unit c)) ts
one = x' * (V \$ zip gs cs)
m = [ [coeff (mvar (X j)) c | j <- gs] | i <- gs, let c = coeff i one]
b = 1 : replicate (length gs - 1) 0
in case solveLinearSystem m b of
Just v -> nf \$ V \$ zip gs v
Nothing -> error "GroupAlgebra.inverse: not invertible"

maybeInverse x@(V ts) =
let gs = P.elts \$ map fst \$ terms x -- all elements in the group generated by the terms
cs = map (glexvar . X) gs
x' = V \$ map (\(g,c) -> (g, unit c)) ts
one = x' * (V \$ zip gs cs)
m = [ [coeff (mvar (X j)) c | j <- gs] | i <- gs, let c = coeff i one]
b = 1 : replicate (length gs - 1) 0
in fmap (\v -> nf \$ V \$ zip gs v) (solveLinearSystem m b)
{-
in case solveLinearSystem m b of
Just v -> Just \$ nf \$ V \$ zip gs v
Nothing -> Nothing
-}
```