{-# LANGUAGE NoImplicitPrelude #-}
{- |
Copyright : (c) Henning Thielemann 2006
Maintainer : numericprelude@henning-thielemann.de
Stability : provisional
Portability : requires multi-parameter type classes
-}
module MathObj.Permutation.CycleList.Check where
import qualified MathObj.Permutation.CycleList as PermCycle
import qualified MathObj.Permutation.Table as PermTable
import qualified MathObj.Permutation as Perm
{-
import qualified Algebra.Ring as Ring
import qualified Algebra.Additive as Additive
import Algebra.Ring((*),one,fromInteger)
import Algebra.Additive((+))
-}
import Algebra.Monoid((<*>))
import qualified Algebra.Monoid as Monoid
import Data.Array((!), Ix)
import qualified Data.Array as Array
-- import NumericPrelude (Integer)
import PreludeBase hiding (cycle)
{- |
We shall make a little bit of a hack here, enabling us to use additive
or multiplicative syntax for groups as we wish by simply instantiating
Num with both operations corresponding to the group operation of the
permutation group we're studying
-}
{- |
There are quite a few way we could represent elements of permutation
groups: the images in a row, a list of the cycles, et.c. All of these
differ highly in how complex various operations end up being.
-}
newtype Cycle i = Cycle { cycle :: [i] } deriving (Read,Eq)
data T i = Cons { range :: (i, i), cycles :: [Cycle i] }
{- |
Does not check whether the input values are in range.
-}
fromCycles :: (i, i) -> [[i]] -> T i
fromCycles rng = Cons rng . map Cycle
toCycles :: T i -> [[i]]
toCycles = map cycle . cycles
toTable :: (Ix i) => T i -> PermTable.T i
toTable x = PermTable.fromCycles (range x) (toCycles x)
fromTable :: (Ix i) => PermTable.T i -> T i
fromTable x =
let rng = Array.bounds x
in fromCycles rng (PermCycle.fromFunction rng (x!))
errIncompat :: a
errIncompat = error "Permutation.CycleList: Incompatible domains"
liftCmpTable2 :: (Ix i) =>
(PermTable.T i -> PermTable.T i -> a) -> T i -> T i -> a
liftCmpTable2 f x y =
if range x == range y
then f (toTable x) (toTable y)
else errIncompat
liftTable2 :: (Ix i) =>
(PermTable.T i -> PermTable.T i -> PermTable.T i) -> T i -> T i -> T i
liftTable2 f x y = fromTable (liftCmpTable2 f x y)
closure :: (Ix i) => [T i] -> [T i]
closure = map fromTable . PermTable.closure . map toTable
instance Perm.C T where
domain = range
apply p = ((toCycles p) PermCycle.*>)
inverse p = fromCycles (range p) (PermCycle.inverse (toCycles p))
instance Show i => Show (Cycle i) where
show c = "(" ++
(unwords $
map show $
cycle c) ++ ")"
instance Show i => Show (T i) where
show p =
case cycles p of
[] -> "Id"
cyc -> concatMap show cyc
{- |
These instances may need more work
They involve converting a permutation to a table.
-}
instance Ix i => Eq (T i) where
(==) = liftCmpTable2 (==)
instance Ix i => Ord (T i) where
compare = liftCmpTable2 compare
{- Better: Group class and instances
instance Additive.C (T i) where
p + q = p * q
negate = inverse
zero = one
instance Ring.C (T i) where
(Cons op cp) * (Cons oq cq) = reduceCycles $
Cons (max op oq) (cp ++ cq)
one = Cons 1 []
-}
instance Ix i => Monoid.C (T i) where
(<*>) = liftTable2 PermTable.compose
idt = error "There is no generic unit element"