Math et Info1 : une histoire d'amour

Voici le tout nouveau, tout beau cours d'initiation conjointe à la programmation fonctionnelle, à Haskell et aux mathématiques en 1ère année.
Le poly et ses sources TEX, le diaporama et ses sources TEX.

Le corrigé du travail demandé sur les Aliens est ICI

TP semaine 40 : construction d'un type récursif Mot

Voici ce que nous aurions dû arriver à créer :

Haskell
module TDmots where
 
    infixr :+
 
    data Mot = MotVide | Char :+ Mot
             deriving (Show, Eq)
 
    taille :: Mot                -> Int
    taille    MotVide             = 0
    taille    (_ :+ resteCouloir) = 1 + taille resteCouloir
 
 
    colle :: Mot       -> Mot   -> Mot
    colle    MotVide      m'    =  m'
    colle    (t :+ reste) m'    =  t :+ (colle reste m')
    
 
    appartient :: Char -> Mot       -> Bool
    appartient    _       MotVide    = False
    appartient    x       (c:+reste) = if c == x
                                       then True
                                       else appartient x reste   
                                            
 
    filtre :: (Char -> Bool) -> Mot         -> Mot
    filtre    _                 MotVide      = MotVide
    filtre    predi             (c :+ reste) = if predi c
                                               then c :+ (filtre predi reste)
                                               else filtre predi reste
                                               
    renverse :: Mot -> Mot
    renverse    mot =
        let transvase MotVide      sac      = sac
            transvase (c :+ reste) sac      = transvase reste (c :+ sac)
        in  transvase mot          MotVide
 
    versString :: Mot          -> String
    versString    MotVide       = []
    versString    (t :+ reste)  = t : (versString reste)
 
    depuisString  :: String       -> Mot
    depuisString     []           =  MotVide
    depuisString     (t : reste)  =  t :+ (depuisString reste)
 
 
    {-
      Dans Prelude,       les constructeurs des listes sont []      et :
      Dans notre module, les constructeurs des Mots   sont MotVide et :+
     -}

Opérateurs logiques en Haskell

Voici une proposition issue du 3e TP de la semaine 39 :

Haskell
module Logique where
 
    -- type : crée un type synonyme pour rendre le code plus clair à lire 
    type OpBinaire = (Bool -> Bool -> Bool)
 
    -- fonction identité
    identité :: Bool -> Bool
    identité =  \x   ->  x
    
    -- ET logique
    et :: OpBinaire
    et    True = identité
    et    _    = \ _   -> False
                    
    -- OU INCLUSIF
    ou :: OpBinaire
    ou    False = identité
    ou    True  = \ _  -> True
 
    -- NÉGATION
    non :: Bool -> Bool
    non    True  = False
    non    False = True
 
    -- OU EXCLUSIF
    ouex :: OpBinaire
    ouex    x y  = (x `et` non y) `ou` (non x `et` y)
 
    -- IMPLICATION
    (==>) :: OpBinaire
    (==>)    x y = (non x) `ou` y
                            
    -- ÉQUIVALENCE
    (<==>) :: OpBinaire
    (<==>)    x y = non (x `ouex` y)
 
 
    -- TABLES DE VÉRITÉ
 
    -- liste des booléens
    lesBool :: [Bool]
    lesBool =  [False, True]
 
    -- table de vérité d'un opérateur binaire 
    tabVer :: OpBinaire  -> [[Bool]]
    tabVer    op         =  [ [op x y | y <- lesBool] | x <- lesBool]
              
    -- deux opérateurs binaires sont égaux ssi ils ont la même table de vérité
    egalOpBin :: OpBinaire -> OpBinaire -> Bool
    egalOpBin    op1          op2       =  (tabVer op1) == (tabVer op2)
 
    
    {-
      Pour de Morgan :
      egalOpBin ( \ x y -> non (x `et` y) )  ( \ x y -> (non x) `ou` (non y) )
     -}

Ensembles par compréhension en Haskell

On définit des ensembles à partir d'un prédicat (notion de fonction caractéristique).

Haskell
module EnsembleCompréhension where
 
 
    type Element  = Int
    type Predicat = Element -> Bool
    data Ensemble = Ens (Predicat)
 
    mini,maxi  :: Element
    (mini,maxi) = (-128,127)
 
    estVide :: Ensemble -> Bool
    estVide    ens      =  listeVersEns ens == []
 
    contient :: Ensemble -> Element -> Bool
    contient    (Ens f)     e       =  f e
 
    univers :: Ensemble
    univers =  Ens (\ n -> n >= mini && n <= maxi)
 
    insere :: Element -> Ensemble -> Ensemble
    insere    e          ens      =  Ens (\x -> (x == e) || (ens `contient` x))
 
    union ::  Ensemble -> Ensemble -> Ensemble
    union     ens1        ens2     =  Ens (\x -> (ens1 `contient` x) || (ens2 `contient` x))
 
    inter ::  Ensemble -> Ensemble -> Ensemble
    inter     ens1        ens2     =  Ens (\x -> (ens1 `contient` x) && (ens2 `contient` x))
 
    filtre :: Predicat -> Ensemble -> Ensemble
    filtre    predic      ens      =  Ens (\x -> (ens `contient` x) && (predic x))
 
    complementaire :: Ensemble -> Ensemble
    complementaire    (Ens f)  =  (Ens (not . f))
 
    difference :: Ensemble -> Ensemble -> Ensemble
    difference    ens1        ens2     =  ens1 `inter` (complementaire ens2)
                          
    estInclus :: Ensemble -> Ensemble -> Bool
    estInclus    ens1        ens2     =  estVide (Ens (\x -> (ens1 `contient` x) &&  not (ens2 `contient` x)))
 
    estEgal :: Ensemble -> Ensemble -> Bool
    estEgal    ens1        ens2     =  (ens1 `estInclus` ens2) && (ens2 `estInclus` ens1)
    
    pourTous :: Predicat -> Ensemble -> Bool
    pourTous    predic      ens      =  (filtre predic ens) `estEgal` ens
 
    ilExiste :: Predicat -> Ensemble -> Bool
    ilExiste    predic      ens      =  not ( estVide (filtre predic ens) )
    
 
    -- Pour un joli afficahge et le test de vacuité
                                        
    listeUnivers :: [Element]
    listeUnivers =  [mini .. maxi]
 
    listeVersEns :: Ensemble -> [Element]
    listeVersEns    (Ens f)  =  [x | x <- listeUnivers, f x]
 
    instance  Show Ensemble where
                        show = show . listeVersEns

courtesy of webmatter.de