Correction Programmation Fonctionnelle Devoir Surveillé

Exercice 1 - Évaluation des expressions

Pour cet exercice, il faut appliquer les règles d'évaluation du langage Lisp pour différentes primitives de manipulation de listes (cons, car, append, list) ainsi que la fonction d'ordre supérieur mapcar.

Voici le détail de l'évaluation pour chaque expression :

Numéro	Expression	Résultat	Explication
1	(cons '(1 2) '(4))	((1 2) 4)	La primitive cons ajoute son premier argument en tant que premier élément (la tête) de la liste passée en second argument.
2	(cons '(1 2) 4)	((1 2) . 4)	Le second argument n'étant pas une liste mais un atome (4), cons crée une "paire pointée" (dotted pair).
3	(car '(((1) 2) 3 4))	((1) 2)	car retourne le premier élément de la liste. Ici, le premier élément de la liste globale est lui-même la liste ((1) 2).
4	(append '(1 2) nil '(4))	(1 2 4)	append concatène le contenu de toutes les listes fournies. La liste vide nil est ignorée lors de la fusion.
5	(list '(1 2) '(4))	((1 2) (4))	list crée une nouvelle liste dont les éléments sont exactement les arguments fournis.
6	(list '(1 2) 4)	((1 2) 4)	Identique au précédent : la fonction list regroupe les deux arguments au sein d'une même liste.
7	(list '(1 2) nil '(4))	((1 2) () (4))	Contrairement à append, list préserve nil (qui s'affiche sous la forme de la liste vide ()) comme un élément à part entière.
8	(mapcar (lambda (x) (- 10 x)) '(1 3 5 7 9))	(9 7 5 3 1)	mapcar applique la fonction (qui soustrait x à 10) à chaque élément de la liste, générant une nouvelle liste avec les résultats.
9	(mapcar (lambda (x y) (+ x y)) '(1 2 3) '(4 5 6))	(5 7 9)	mapcar peut prendre plusieurs listes. La fonction lambda effectue ici l'addition élément par élément (1+4, 2+5, 3+6).
10	(mapcar (lambda (x) (if (evenp x) 0 x)) '(1 2 3 4 5))	(1 0 3 0 5)	Le prédicat evenp teste si le nombre est pair. Si oui, il est remplacé par 0, sinon il est conservé tel quel.

Exercice 2 - La fonction strict-doublons

L'objectif est d'extraire d'une liste les éléments qui y apparaissent exactement deux fois. Pour y parvenir proprement en Lisp, la solution fournie décompose le problème en utilisant deux fonctions utilitaires avant d'écrire la fonction principale.

Note sur la correction : Le code source issu de l'énoncé comportait une erreur de syntaxe à la dernière ligne de la fonction principale (une condition t manquante dans le cond). Le code ci-dessous a été réparé pour être syntaxiquement valide.

Fonctions utilitaires

La première étape consiste à pouvoir compter les occurrences d'un élément, puis à pouvoir supprimer toutes ses occurrences.

; Fonction qui retourne le nombre d’occurrences d’un élément dans une liste
(de nbocc (e l)
  (cond
    ((null l) 0)
    ((eq e (car l)) (+ 1 (nbocc e (cdr l))))
    (t (nbocc e (cdr l)))))

; Fonction qui supprime toutes les occurrences d’un élément dans une liste
(de omettre (e l)
  (cond
    ((null l) ())
    ((eq e (car l)) (omettre e (cdr l)))
    (t (cons (car l) (omettre e (cdr l))))))

Fonction principale

La logique de la fonction strict-doublons est particulièrement astucieuse :

1. Si l'élément de tête apparait plus de 2 fois : on supprime absolument toutes ses occurrences dans le reste de la liste grâce à omettre, et on continue.
2. Si l'élément de tête apparait exactement 2 fois : on le conserve dans le résultat avec cons. On continue l'analyse sur (cdr l). Plus tard dans le parcours, le programme croisera la seconde occurrence de cet élément. À ce moment-là, son décompte sera de 1, il basculera donc dans le cas par défaut (le dernier) et sera ignoré.
3. Si l'élément apparait moins de 2 fois (donc 1 fois, ou 0 si on analyse une liste vide) : on l'ignore et on passe à la suite.

(de strict-doublons (l)
  (cond
    ((null l) ())
    ((> (nbocc (car l) l) 2) (strict-doublons (omettre (car l) l)))
    ((= (nbocc (car l) l) 2) (cons (car l) (strict-doublons (cdr l))))
    (t (strict-doublons (cdr l)))))

Exercice 3 - Dérivation de polynômes

Un polynôme est modélisé par une liste de couples (coefficient puissance). Ainsi, 1 + x + 3x² + 2x⁵ correspond à la liste ((1 0) (1 1) (3 2) (2 5)). La dérivée de cx^p est (c × p)x^(p-1).

Solution demandée (avec mapcar et lambda)

L'énoncé demande explicitement l'utilisation de mapcar et lambda. Pour chaque couple x, le nouveau coefficient est le produit du coefficient (car x) et de la puissance (cadr x). La nouvelle puissance est (1- (cadr x)).

L'astuce de la solution officielle pour gérer la constante (puissance 0 dont la dérivée disparait) est d'appliquer un cdr sur le résultat global du mapcar.

(de derive (l)
  (cdr (mapcar (lambda (x) (list (* (car x) (cadr x)) (1- (cadr x)))) l)))

Attention au piège : Cette version suppose formellement que le polynôme débute toujours par le terme constant (puissance 0), car le cdr global supprimera de toute façon le premier élément de la liste résultante.

Solution alternative (récursive)

L'énoncé fournit également une solution récursive classique (bien que non demandée) qui est beaucoup plus robuste, car elle filtre spécifiquement le terme dont la puissance est 0, peu importe sa position dans la liste.

; Le calcul mathématique de la dérivée pour un couple de valeurs
(de op (cl)
  (list (* (car cl) (cadr cl)) (1- (cadr cl))))

; Fonction récursive robuste
(de derive (l)
  (cond
    ((null l) ())
    ((= (cadar l) 0) (derive (cdr l)))
    (t (cons (op (car l)) (derive (cdr l))))))

Note : (cadar l) est équivalent à (car (cdr (car l))), ce qui permet d'extraire directement la puissance du premier couple de la liste.

Exercice 4 - La fonction split

Il s'agit de scinder une liste en deux à partir d'un index n. Le document propose plusieurs approches. Note sur la correction : Le code source original comportait de nombreuses erreurs de parenthésage et d'omission de conditions t dans les cond. Les versions ci-dessous sont corrigées pour être fonctionnelles.

Approche 1 : Fonctions auxiliaires séparées

Cette méthode est la plus lisible. On délègue le travail à deux fonctions distinctes : une qui récupère les n premiers éléments, l'autre qui récupère le reste.

; npremier retourne les n premiers éléments d’une liste
(de npremier (l n)
  (cond
    ((null l) nil)
    ((= n 0) nil)
    (t (cons (car l) (npremier (cdr l) (- n 1))))))

; dernier retourne la liste sans les n premiers éléments
(de dernier (l n)
  (cond
    ((null l) nil)
    ((= n 0) l)
    (t (dernier (cdr l) (- n 1))))))

; Fonction principale
(de split (l n)
  (cond
    ((null l) nil)
    (t (list (npremier l n) (dernier l n)))))

Approche 2 : Récursivité en une passe (avec redondance)

Cette version effectue le découpage en une seule fonction. L'inconvénient majeur de cette version est sa complexité algorithmique : elle calcule (split (cdr l) (- n 1)) deux fois par itération, ce qui est très inefficace.

(de split (l n)
  (cond
    ((null l) nil)
    ((> n (length l)) (list l '())) ; cas spécifique : n > taille de la liste
    ((= n 0) (list '() l))          ; condition d’arrêt
    (t (append 
         (list (cons (car l) (car (split (cdr l) (- n 1))))) 
         (cdr (split (cdr l) (- n 1)))))))

Approche 3 : Récursivité optimisée (utilisation de let)

Pour corriger l'inefficacité de l'approche précédente, on mémorise le résultat de l'appel récursif dans une variable locale aux grâce à la construction let. C'est la solution la plus élégante et performante des trois.

(de split (l n)
  (cond
    ((null l) nil)
    ((> n (length l)) (list l '()))
    ((= n 0) (list '() l))
    (t (let ((aux (split (cdr l) (- n 1)))) 
         (append 
           (list (cons (car l) (car aux))) 
           (cdr aux))))))

Exercice 5 - La fonction remove-if

La fonction remove-if parcourt une liste et reconstruit une nouvelle liste en ignorant les éléments qui valident un prédicat (une fonction qui retourne vrai ou faux).

En Le_Lisp, on utilise la fonction funcall pour appliquer la fonction contenue dans la variable pred à l'élément courant (car l).

(de remove-if (pred l)
  (cond
    ((null l) nil)
    ((funcall pred (car l)) (remove-if pred (cdr l)))
    (t (cons (car l) (remove-if pred (cdr l))))))

Si (funcall pred (car l)) retourne vrai, on ignore (car l) et on lance l'appel récursif sur le reste de la liste. Sinon (le cas t), on conserve (car l) avec un cons et on construit la suite.

Méthode

Pour réussir ce type d'épreuve d'algorithmique fonctionnelle et de Lisp, voici les principes à intégrer :

1. Maîtriser la forme globale d'une fonction récursive : Presque tous les exercices demandent de traiter une liste. Votre premier réflexe dans un cond doit toujours être de traiter le cas d'arrêt (généralement ((null l) ...)), puis d'isoler la tête avec car et de relancer la récursivité sur le reste avec cdr.
2. Ne pas avoir peur de créer des fonctions auxiliaires : Comme démontré dans l'exercice 2 (pour extraire les doublons), découper un problème complexe en petites fonctions simples (nbocc, omettre) rend la fonction principale triviale à écrire.
3. Tracer le code mentalement sur des petits exemples : Face à des expressions imbriquées d'appels récursifs, il est facile de s'y perdre, ou d'oublier des parenthèses. Testez toujours votre algorithme sur une liste de un ou deux éléments, ou sur une liste vide, pour vérifier si vos appels à cons ou list n'ajoutent pas un niveau d'imbrication indésirable.
4. Comprendre la nuance des constructeurs : L'exercice 1 est un classique qu'il faut connaître par coeur. La différence entre cons (qui modifie la tête de la liste de droite), list (qui crée un contenant pour ses arguments) et append (qui fusionne les contenus) est le socle de toute la programmation Lisp.