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