[Haskell-beginners] Type of a Group.

Rustom Mody rustompmody at gmail.com
Sat Feb 9 17:59:37 CET 2013

On Sat, Feb 9, 2013 at 6:35 PM, Robert Goss <goss.robert at gmail.com> wrote:

> Dear all,
> Looking to learn a little haskell I tried to program up a little group
> theory but feel I am stuck on what the types should be. At first it seemed
> obvious (and the algebra package does this) that the type of a group should
> be given by:
> class Group g where
>   mul :: g -> g -> g
>   inv :: g -> g
>   unit :: g
> My problem is this seems to assume that the type of group you are in is
> encoded by the type system.
> I first ran into problems with this when I wanted to define a cyclic
> group. The only way I could define the type was either to define each
> cyclic group separately so have C2, C3, C4, ... or parametrise it over the
> class Nat. So a cyclic group would have the type Cyclic (Succ(Succ( ...
> Succ(Zero)) ... )) which would consistently define all cyclic groups but is
> hardly any better. For example a computation mod a large prime p is not
> going to be pleasant.
> I came up with a partial solution by realising that a group is defined as
> a set X and some operations on it to get
> class Group g x where
>   mul :: g -> x -> x -> x
>   inv :: g-> x -> x
>   unit :: g -> x
> Making it easy to define cyclic groups and all my old groups carry over.
> But now to evaluate an expression I need to hang onto the group i am in and
> pass it around. As i am newish to haskell I wanted to know if I have missed
> a simpler more obvious way of doing things?
> All the best,
> Robert Goss
Taking your first approach I could do this much:

class Group g where
  mul :: g -> g -> g
  inv :: g -> g
  unit :: g

class Group g => CycGroup g where
  gen :: g

class CycGroup g => FiniteCycGroup g where
  baseSet :: [g]

-- I would have preferred to have order :: Int, to baseSet
-- but ghc does not like that for some reason

data G2 = A|B

instance Group G2 where
  unit = A

  inv A = A
  inv B = B

  mul A A = A
  mul A B = B
  mul B A = B
  mul B B = A

instance CycGroup G2 where
  gen = B

instance FiniteCycGroup G2  where
  baseSet = [A, B]

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130209/4771dcf0/attachment.htm>

More information about the Beginners mailing list