Z/nZ sans arithmétique modulaire...

Voici une petite classe Haskell rigolote qui permet de travailler sur $\mathbb Z / n \mathbb Z$ avec $n$ petit sans parler d'arithmétique modulaire ni même d'addition : on fait tout, tels des Mac Gyver des mathématiques, avec une fonction successeur.

Haskell
data ClasseMod t = (Eq t, Show t, Enum t, Bounded t) => Zn t 
 
instance (Show t) => Show (ClasseMod t) where
  show (Zn x) = show x
 
succZn :: (ClasseMod t) -> (ClasseMod t) 
succZn (Zn x)        = if (x == maxBound) then (Zn minBound) else (Zn (succ x))
 
predZn :: (ClasseMod t) -> (ClasseMod t) 
predZn (Zn x)        = if (x == minBound) then (Zn maxBound) else (Zn (pred x))
 
instance (Eq t, Show t, Enum t, Bounded t) => Enum (ClasseMod t) where
  succ = succZn
  pred = predZn
  fromEnum (Zn x) = fromEnum x
  toEnum n = Zn (toEnum n)
 
instance (Eq t) => Eq (ClasseMod t) where
  (Zn x) == (Zn y) = x == y
 
 
instance (Eq t, Show t, Enum t, Bounded t) => Bounded (ClasseMod t) where
  maxBound = Zn (maxBound)
  minBound = Zn (minBound)
 
 
classeOfInt :: (Bounded t, Enum t, Eq t, Show t) => Integer -> ClasseMod t
classeOfInt n 
  |n == 0    = minBound
  |n < 0     = predZn (classeOfInt (n+1)) 
  |otherwise = succZn (classeOfInt (n-1)) 
 
plusZn  x y = 
  if (fromEnum x == 0) then y
  else
    succ (plusZn (pred x) y)
    
 
foisZn x y =
  if (fromEnum x == 0) then (toEnum 0)
  else
    if (fromEnum x == 1) then y
    else plusZn y (foisZn (pred x) y) 
         
         
instance (Eq t, Show t, Enum t, Bounded t) => Num (ClasseMod t) where
  (+) = plusZn
  (*) = foisZn
  fromInteger  = classeOfInt 
  negate x =  toEnum (- (fromEnum x) + (fromEnum (maxBound :: ClasseMod t)) + 1)
 
 
 
 
-- exemples
 
data LesZ2 = O2 | I2  deriving (Eq, Show, Bounded, Enum)
 
type Z2 = ClasseMod LesZ2
 
 
data LesZ3 = O3 | I3 | II3  deriving (Eq, Show, Bounded, Enum)
 
type Z3 = ClasseMod LesZ3
 
 
data LesZ4 = O4 | I4 | II4 | III4 deriving (Eq,Show,  Bounded, Enum)
 
type Z4 = ClasseMod LesZ4

On peut utiliser nos types ainsi:

Haskell
*StructuresFinies> 7 :: Z4
III4
*StructuresFinies> 2 * 2 :: Z4
O4
*StructuresFinies> 2 * 7 :: Z4
II4
*StructuresFinies> 2 + 7 :: Z4
I4
*StructuresFinies> 2 - 7 :: Z4
III4

Le diaporama et ses sources TEX

courtesy of webmatter.de