IE2 - Corrigé

Version PDF :

Exercice 1 - Structure de documents

Quand on y réfléchit bien, un document (même ce sujet !) peut être vu comme une structure de données récursive. Un document a toujours un titre et un contenu. Le contenu peut être simplement du texte ou bien une liste de documents.

Q1 : Décrivez la structure de données qui peut représenter ce type de document. Vous pouvez utiliser le type

data Either a b = Left a | Right b

qui permet de gérer le cas où un élément peut être soit du type a soit du type b.

Ici, les mots importants sont qu’un document a toujours un titre et un contenu, et que le contenu peut être soit du texte soit une liste de documents.

On peut donc simplement représenter un document avec le type suivant :

data Document = Document {
    title :: String,
    content :: Either [Document] String
}

Si on ne veut pas utiliser la syntaxe d’enregistrement, on peut aussi l’écrire

data Document = Document String (Either [Document] String)

Le Either est ici utilisé pour spécifier que le contenu peut être soit juste du texte, soit une liste de sous documents. On peut voir ça un peu comme un arbre où les feuilles sont des documents contenant juste du texte.

Q2 : Écrivez une fonction titres qui prend un Document en paramètre et qui renvoie la liste des titres contenus à l’intérieur.

On peut utiliser la fonction concatMap :: (a -> b) -> [a] -> [b].

La fonction prend un document et renvoie la liste des titres contenus dedans. C’est donc une fonction récursive dont le cas de base est un document qui n’a pas de sous-document.

titres :: Document -> [String]
titres (Document t (Left ds)) = t : concatMap titres ds
titres d                      = [title d]

Concrètement, si un document a des sous-documents, on va récupérer la liste des titres de tous les sous-documents de manière récursive. concatMap est important ici pour éviter que l’on se retrouve avec des listes de listes de listes…

On tire aussi parti du fait qu’on ait utilisé la syntaxe d’enregistrement pour ne pas avoir à faire de filtrage de motif sur le cas de base.

Exercice 2 - Élément maximum d’une liste - version sûre

Q1 : En utilisant un filtrage de motif, écrire une fonction qui calcule le maximum des éléments d’une liste, sans générer d’erreur quand la liste est vide.

Ici, on ne veut pas renvoyer d’erreur quand la liste est vide, donc on va renvoyer une valeur encapsulée dans un Maybe.

maxListe :: Ord a => [a] -> Maybe a
maxListe []     = Nothing
maxListe (x:xs) = case (maxListe xs) of
                    Nothing  -> Just x
                    (Just y) -> Just (max x y)

Qu’est-ce qu’on a d’important ?

Déjà, le type contient Ord a, parce qu’on a besoin que les éléments de la liste puissent être comparés les uns aux autres.

Ensuite, il faut qu’on regarde récursivement le résultat dans le reste de la liste. Si on n’a rien (Nothing), alors on n’a qu’à renvoyer l’élément courant, sinon, on renvoie un Maybe contenant la valeur maximale entre l’élément courant et le maximum qu’on a pour le moment.

Par exemple, sur la liste [4, 6, 1], on aura :

[4, 6, 1] --> on regarde le résultat [6, 1]
              --> on regarde le résultat sur [1]
                  --> on regarde le résultat sur []
                  <-- Nothing
              <-- Just 1
          <-- Just (max 6 1) = Just 6
    <-- Just (max 4, 6) = Just 6

C’est important de remarquer qu’on ne compare par une valeur de type a avec une valeur de type Maybe a directement.

Et pour le minimum ?

On remplace juste les max par des min, le principe reste le même !

Q2 : Donner une version de la fonction qui utilise un pliage.

Ici, c’est le même principe qu’au dessus, sauf qu’on va replier la liste. L’accumulateur qu’on va utiliser sera de type Maybe a puisque c’est le type de retour de notre fonction et qu’on n’a pas besoin de plus compliqué. On commencera par Nothing, ce qui gère le cas où la liste est vide.

maxListe' :: Ord a => [a] -> Maybe a
maxListe' = foldr (minM) Nothing
    where
        minM el acc = case acc of
            Nothing  -> Just el
            (Just x) -> Just (max x el)

Le type de la fonction minM correspond bien à ce qu’on attend d’une fonction de pliage, minM :: a -> Maybe a -> Maybe a.

Un fold à gauche ?

Ici, c’est tout à fait possible aussi, on commencerait juste à regarder par le premier élément et pas le dernier

Exercice 3 - Dernier élément, sous condition

Écrire une fonction qui renvoie le dernier élément d’une liste qui satisfait une propriété. Cette fonction doit être sûre, si aucune valeur n’est trouvée, elle renverra Nothing.

Ici, on aura besoin d’un prédicat (donc une fonction (a -> Bool)) et d’une liste d’éléments de type a.

findLast :: (a -> Bool) -> [a] -> Maybe a
findLast pred = foldl (\acc e -> if pred e then Just e else acc) Nothing

Ici, on fait un pliage à gauche. Pourquoi ? Parce qu’on veut le dernier élément qui satisfait la propriété. Or, à chaque fois qu’on trouve un élément qui satisfait la propriété, on écrase la valeur de l’accumulateur. Si on faisait un pliage à droite, on finirait avec la valeur la plus à gauche, soit la première.

Bien sûr l’accumulateur est initialisé à Nothing au cas où aucun élément ne satisfait la propriété (ou si la liste est vide).

Exercice 4 - Approximation de la fonction cosinus

On peut approcher la fonction cosinus avec la série entière :

\[\sum_{k=0}^\infty (-1)^k \frac{x^{2k}}{(2k)!}\]

On veut écrire une fonction cosApprox qui prend une valeur x et une valeur n et qui approxime la valeur de \(cos(x)\) au rang n.

Pour que le calcul soit efficace, on veut éviter d’effectuer intégralement les calculs de \(x^{2k}\) et de \((2k)!\) à chaque étape. Pour cela, on utilise les identités suivantes :

\[\begin{align*} x^{2(k+1)} &= x^{2k} \times x^2 \quad\text{et} \\ (2(k+1))! &= (2k)! \times (2k + 1) \times (2k + 2) \end{align*}\]

On sait que pour \(k = 0\), l’élément vaut 1. On va se servir de ça pour éviter un calcul inutile.

cosApprox :: Fractional a => a -> a -> a
cosApprox x n = somme
    where (_, _, _, somme) = foldl
        (\(pow, fac, sign, s) k) -> let pow'  = pow * x^^2
                                        fac'  = (2*k + 1)*(2*k + 2) * fac
                                        sign' = -sign
                                    in (pow', fac', sign', s + sign' * pow' / fac')
                    (1, 1, 1, 1)
                [1..n]

Ici, on utilise un accumulateur plus compliqué que d’habitude pour éviter de faire des calculs complexes à chaque étape.

On stocke donc la valeur de la puissance, de la factorielle, du signe de la fraction et de la valeur cumulée de la somme. À la fin, on renvoie juste la valeur de la somme.

On commence aux valeurs pour \(k=0\), soit (1, 1, 1, 1).

On replie sur la liste [1..n] qui sera la liste des \(k\) possibles que l’on doit traiter.

On plie à gauche, parce qu’on a besoin de faire les calculs dans l’ordre. Commencer par la fin de la liste voudrait dire qu’il faut qu’on calcule la factorielle précédente et la puissance précédente, et ces calculs pourraient être plus compliqués à déterminer.