TP3 Monoïde - INFO2

Un point sera fait en amphi. Remarque générale : vous êtes trop nombreux à arriver en TP sans note et vous persistez à frapper vos claviers aveuglément. On passe 3/4 d'heure à régler de stupides problèmes de syntaxe sans intérêt car vous n'avez pas cherché le problème sur les aliens. Cela va continuer car vous êtes encore trop nombreux à ne pas sortir de crayon pour noter les problèmes rencontrés et leurs solutions. Heureusement quelques étudiants, ayant travaillé un minimum, ont l'esprit libéré des problèmes de syntaxe et peuvent se consacrer à la résolution de problèmes intéressants.

Nous avions évoqué avec certains le module MayBe : nous le mettons de côté pour l'instant et gérons les erreurs avec error.

Nous repartirons donc la semaine prochaine du squelette suivant :

Haskell
{-# LANGUAGE TypeSynonymInstances, FlexibleInstances, GADTs,ScopedTypeVariables #-}
module StructuresFinies where
 
-- Définit un magma sur un ensemble fini (Bounded) d'objets de type t 
-- muni de la LCI <+>
class (Bounded t,Enum t) => Magma t where
  (<+>) :: t -> t -> t 
  lesElements :: [t]
  lesElements = [(minBound) .. (maxBound)]
  table :: [[t]]
  table = [[i <+> j | j <-  le ] | i <-  le] where le = lesElements
  
  
-- tous les triplets du type de variables correspondant à l'argument (pas optimum...))
lesTripletsTypeDe :: (Magma t) => t -> [(t,t,t)]
lesTripletsTypeDe x = [(a,b,c) | 
                     a <- lesElements, 
                     b <- lesElements, 
                     c <- lesElements]
 
-- test d'associativité
isTripletAssociatif :: (Eq t, Magma t) => (t,t,t) -> Bool
isTripletAssociatif    (a,b,c) = (a <+> b) <+> c == a <+> (b <+> c)
 
-- est-ce que la loi d'une instance de Magma donnée est associative ? 
isAssoTypeDe :: (Eq t, Magma t) => t -> Bool
isAssoTypeDe x = all isTripletAssociatif (lesTripletsTypeDe x)
 
 
-- exo 1.21
data Troiz = A | B | C deriving (Show, Eq, Bounded, Enum)
 
loi3 :: Troiz -> Troiz -> Troiz
loi3 A x = x
loi3 B B = C
loi3 B C = A
loi3 C C = B
loi3 x y = loi3 y x
 
instance Magma Troiz where
  (<+>) = loi3
 
 
-- (B2, xor) est un magma
instance Magma Bool where 
  (<+>) p q = if (p == q) then False else True 
 
 
-- implication de la logique des proposition
(==>) :: Bool -> Bool -> Bool 
(==>) p q = (not p) || q
 
-- a simplifiable à gauche signifie ax = ay implique x = y
isTripletSimpGauche :: (Magma t, Eq t) => (t,t,t) -> Bool
isTripletSimpGauche (a,x,y) = (a <+> x == a <+> y) ==> (x == y)
 
isTripletSimpDroite :: (Magma t, Eq t) => (t,t,t) -> Bool
isTripletSimpDroite (a,x,y) = (x <+> a == y <+> a) ==> (x == y)
 
isTripletSimp :: (Magma t, Eq t) => (t,t,t) -> Bool
isTripletSimp (a,x,y) = (isTripletSimpGauche (a,x,y)) && (isTripletSimpDroite (a,x,y))
 
isMagmaSimpTypeDe :: (Magma t, Eq t) => t -> Bool
isMagmaSimpTypeDe x = all isTripletSimp (lesTripletsTypeDe x)
 
 
-- teste si un élement e est neutre 
isNeutre :: (Magma t, Eq t) => t -> Bool
isNeutre e = all (\ x -> (x <+> e == x) && (e <+> x == x)) lesElements
 
 
-- Une fonction trouve qui trouve le premier élément qui vérifie le prédicat.
trouve :: (a -> Bool) -> [a] -> a
trouve f []    = error "Je suis désolé, je n'ai rien trouvé qui satisfasse le prédicat"
trouve f (t:q) = if (f t) then t else (trouve f q)
 
-- trouve s'il existe un élément neutre dans une liste d'éléments d'une instance de Magma
trouveNeutre ::  (Magma t, Eq t) => [t] -> t
trouveNeutre liste = trouve (\e -> isNeutre e) liste 
 
 
-- Monoïde hérite de Magma et a un zéro et on vérifie l'asso
class (Magma t, Eq t) => Monoide t where
  zero ::  t
  zero = if (isAssoTypeDe z) then z else error "Loi non associative" 
    where z = trouveNeutre lesElements
 
instance Monoide Bool

courtesy of webmatter.de