I'm writing a program for representation of finite groups and simple operations on their elements. I wrote most of the functionality which I need, for example inverse elements, generators, checking if subset is subgroup etc.
Unfortunately all my functions need identity element, set and operation. I want to define the appropriate instance of the class and use it instead of this trio. And here begins my problem, I don't quite know how to go about it and all I can find on the internet contains only examples of definitions, without usage examples.
Eventually I would like to work with groups Sn, so far I've tested my code on (Zn +).
I wrote this:
data Z2 = Elm Int deriving (Show, Eq)
z2 :: Int -> Z2
z2 a = Elm (a `mod` 2)
class FiniteGroup a where
identity :: a
op :: a -> a -> a -- operation
set :: [a]
instance FiniteGroup Z2 where
identity = (Elm 0)
op (Elm x) (Elm y) = z2 (x+y)
set = [(Elm 0), (Elm 1)]
And it works fine for the function op, for example:
*Main> (Elm 1) `op` (Elm 0)
Elm 1
Unfortunately, I cant use identity and set. How do I use it?
I also can't figure out how to refactor an existing function to use my type class.
For example I have this:
cyclicGenerators :: (Eq a) => a -> [a] -> (a -> a -> a) -> [a]
and it works fine, but I want to have something like this:
cyclicGenerators :: (Eq a) => FiniteGroup a -> [a]
I cant use the identity and set, how to use it?
You must use them in a context which defines a unambiguously. E.g. providing an explicit type annotation
set :: [Z2]
identity :: Z2
Passing them to some function requiring a Z2 also works. As long as the compiler can figure out which finite group you are talking about, you will be fine. Otherwise, you'll get an "ambiguous ..." error.
How to replace signatures in function and again how to use identity and set in function which I've already defined.
Try e.g.
cyclicGenerators :: (Eq a, FiniteGroup a) => [a]
cyclicGenerators = filter isGenerator set
where isGenerator x = ... -- a Boolean telling whether it's a generator
Above the compiler "knows" that set refers to the finite group a, since we must return an [a] and filter doesn't change the type of the input list, hence the set must be of type [a] as well. Here type inference works very well in propagating types so that the correct finite group instance is selected.
Edit: the OP proposes the code
cyclicGenerators :: (FiniteGroup a) => [a]
cyclicGenerators = filter isGenerator set
where isGenerator = (\x -> groupOrder set == elemOrder x)
which triggers an ambiguity error. Indeed, the last set is not forced to belong to the same group -- it would make sense to compare the group order of another group to the order of x. E.g. groupOrder (set :: [Z5]) == elemOrder (identity :: [Z2]) would type check, since both are integers.
So we need to state that the type of that set is [a]. The plain Haskell way is
where isGenerator = (\x -> groupOrder (set `asTypeOf` [x]) == elemOrder x)
where asTypeOf is a library function which simply returns its first argument, but requires it shares its type with the second argument. It is defined in the libraries as:
asTypeOf :: t -> t -> t
asTypeOf x y = x
Alternatively, we can exploit a very commonly used extension of GHC Haskell. First, we need to enable it by adding
{-# LANGUAGE ScopedTypeVariables #-}
at the top of the module file. Then, we can simply write
cyclicGenerators :: forall a . (FiniteGroup a) => [a]
-- ^^^^^^^^^^ added
cyclicGenerators = filter isGenerator set
where isGenerator = (\x -> groupOrder (set :: [a]) == elemOrder x)
where we explicit state that set is of type [a], so it belongs to the same group.