Exercices sur le paradigme de programmation fonctionnelle

I. Rappels sur le paradigme fonctionnel⚓︎

Pas d'effets de bord

Avec le paradigme fonctionnel, tous les objets sont immuables et il n'y a pas de variables globales, pas d'effets de bords.

Les affectations

Python permet d'écrire des scripts dans les trois paradigmes : impératif, programmation orientée objet, programmation fonctionelle. Nous allons expérimenter ici la programmation fonctionelle, donc s'interdire les affectation qui peuvent modifier l'état du programme, les utilisations d'objets mutables, les effets de bord.

Dans la plupart des langages fonctionnels il y a une commande qui permet de donner un nom à une expression avec une syntaxe comme let EXPR be NOM in ... Cela permet d’éviter que NOM reçoive une autre valeur dans le reste de la fonction, afin d’éviter les effets de bords. En Python, nous devrons "tricher" et utiliser des affectations en s’assurant qu’une variable ne recevra qu’une seule valeur lors de l’exécution de la fonction.

Les boucles

En programmation fonctionelle, on n'utise pas de boucles forni while. On utilise des fonctions récursives.

Les fonctions sont des données

Les fonctions peuvent être passées en paramètres d'autres fonctions.
Les fonctions peuvent renvoyer d'autres fonctions. C'est ce qu'on appelle l'ordre supérieur.

II. Exercices sur la structure abstraite de Liste⚓︎

Implémentation des listes utilisée dans tous les exercices

Un exemple d'interface fonctionnelle pour le type abstrait Liste

La valeur d'une liste est un tuple de tuple ce qui est une structure immuable en Python.

Exécuter le code ci-dessous (sinon les exercices ne fonctionneront pas). Il sera toujours présent (caché) dans les exercices de ce paragraphe

###

def creerpy-undliste():bksl-nl return ()bksl-nlbksl-nldef cons(valeur, liste):bksl-nl return (valeur, liste)bksl-nlbksl-nldef tete(liste):bksl-nl return liste[0]bksl-nlbksl-nldef queue(liste):bksl-nl return liste[1]bksl-nlbksl-nldef estpy-undvide(liste):bksl-nl return liste == ()bksl-nl bksl-nl

Exemple d'utilisation

🐍 Console Python

>>> ma_liste = creer_liste()  # (1)
>>> ma_liste
()
>>> cons(1, ma_liste)
(1, ())
>>> ma_liste
()

Ce sera la seule affectation de tous les exercices de cette page. Voir le paragraphe ci-dessus.

Cliquer sur le + pour lire le commentaire

Pas d'effet de bord

L'exemple précédent montre qu'on n'a pas d'effet de bord.

Contrainte

👉 Dans tous les exercices, il faudra utiliser des fonctions données ci-dessus dans l'implémentation de la structure abstraite liste.

Exercice 0 :⚓︎

Créer une liste

Ecrire l'instruction qui permet de créer la liste : (4, (3, (2, (1, ())))) sans utiliser aucune affectation. Faire l'affichage de la liste pour vérifier.

###

#--- HDR ---#bksl-nlbksl-nldef creerpy-undliste():bksl-nl return ()bksl-nlbksl-nldef cons(valeur, liste):bksl-nl return (valeur, liste)bksl-nlbksl-nldef tete(liste):bksl-nl return liste[0]bksl-nlbksl-nldef queue(liste):bksl-nl return liste[1]bksl-nlbksl-nldef estpy-undvide(liste):bksl-nl return liste == ()bksl-nl bksl-nlbksl-nl#--- HDR ---#bksl-nlbksl-nl# A vousbksl-nlbksl-nlbksl-nl# pour vérifier :bksl-nlprint(...)bksl-nlbksl-nl

Solution

🐍 Script Python

cons(4, cons(3, cons(2, cons(1, creer_liste()))))
print(cons(4, cons(3, cons(2, cons(1, creer_liste())))))

Exercice 1 :⚓︎

Longueur d'une liste

Compléter la fonction récursive longueur qui prend en paramètre une liste implémentée comme ci-dessus liste, et renvoie la longueur de cette liste.

###

# Tests :bksl-nlassert longueur(creerpy-undliste()) == 0bksl-nlassert longueur(cons(4, cons(3, cons(2, cons(1, creerpy-undliste()))))) == 4bksl-nlbksl-nl# Autres testsbksl-nlassert longueur(cons(5, cons(4, cons(3, cons(2, cons(1, creerpy-undliste())))))) == 5bksl-nlbksl-nl 5/5

def longueur(liste):bksl-nl ...bksl-nlbksl-nlbksl-nl# Tests :bksl-nlassert longueur(creerpy-undliste()) == 0bksl-nlassert longueur(cons(4, cons(3, cons(2, cons(1, creerpy-undliste()))))) == 4bksl-nlbksl-nldef longueur(liste):bksl-nl if estpy-undvide(liste):bksl-nl return 0bksl-nl return 1 + longueur(queue(liste))bksl-nlbksl-nl

Solution en écriture fonctionnelle :

🐍 Script Python

longueur = lambda liste: 0 if est_vide(liste) else 1 + longueur(queue(liste))

Exercice 2 :⚓︎

Minimum d'une liste

Compléter la fonction récursive minimum qui prend en paramètre une liste non vide implémentée comme ci-dessus liste, et renvoie le plus petit élément de cette liste.

👉 il faudra utiliser la fonction min de python

###

# Testsbksl-nlbksl-nlassert minimum(cons(4, cons(13, cons(1, cons(5, creerpy-undliste()))))) == 1bksl-nlbksl-nl# Autres testsbksl-nlbksl-nlassert minimum(cons(1, cons(13, cons(1, cons(5, creerpy-undliste()))))) == 1bksl-nlassert minimum(cons(14, cons(13, cons(6, cons(5, creerpy-undliste()))))) == 5bksl-nlassert minimum(cons(4, cons(13, cons(2, cons(1, creerpy-undliste()))))) == 1bksl-nlbksl-nl 5/5

def minimum(liste):bksl-nl if ...: # dernier élément de la listebksl-nl return ...bksl-nl else:bksl-nl return min(..., minimum(...))bksl-nlbksl-nlbksl-nl# Testsbksl-nlbksl-nlassert minimum(cons(4, cons(13, cons(1, cons(5, creerpy-undliste()))))) == 1bksl-nlbksl-nldef minimum(liste):bksl-nl if estpy-undvide(queue(liste)): # dernier élément de la listebksl-nl return tete(liste)bksl-nl else:bksl-nl return min(tete(liste), minimum(queue(liste)))bksl-nlbksl-nl

Solution en écriture fonctionnelle :

🐍 Script Python

minimum = lambda liste: tete(liste) if est_vide(queue(liste)) else min(tete(liste), minimum(queue(liste)))

Exercice 3 :⚓︎

Une liste contient-elle un élément ?

Compléter la fonction récursive contient qui prend en paramètre une liste implémentée comme ci-dessus liste, et un élément v. Cette fonction doit renvoyer un booléen indiquant si v est dans liste.

###

# Testsbksl-nlbksl-nlassert contient(cons(4, cons(13, cons(1, cons(5, creerpy-undliste())))), 8) is Falsebksl-nlassert contient(cons(4, cons(13, cons(1, cons(5, creerpy-undliste())))), 13) is Truebksl-nlassert contient(creerpy-undliste(), 13) is Falsebksl-nlbksl-nl# Autres testsbksl-nlbksl-nlassert contient(cons(4, cons(13, cons(1, cons(5, creerpy-undliste())))), 5) is Truebksl-nlassert contient(cons(4, cons(13, cons(1, cons(5, creerpy-undliste())))), 4) is Truebksl-nlbksl-nl 5/5

def contient(liste, v):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlbksl-nlassert contient(cons(4, cons(13, cons(1, cons(5, creerpy-undliste())))), 8) is Falsebksl-nlassert contient(cons(4, cons(13, cons(1, cons(5, creerpy-undliste())))), 13) is Truebksl-nlassert contient(creerpy-undliste(), 13) is Falsebksl-nlbksl-nlbksl-nldef contient(liste, v):bksl-nl if estpy-undvide(liste):bksl-nl return Falsebksl-nl elif tete(liste) == v:bksl-nl return Truebksl-nl else:bksl-nl return contient(queue(liste), v)bksl-nl bksl-nl

Solution en écriture fonctionnelle :

🐍 Script Python

contient = lambda liste, v: False if est_vide(liste) else True if v == tete(liste) else contient(queue(liste), v)

Exercice 4 :⚓︎

Fonction d'ordre supérieur

Compléter applique(f, liste) qui renvoie une nouvelle liste correspondant aux images des éléments de liste par la fonction f.

Exemple :

🐍 Console Python

>>> applique(lambda x: x*x, cons(4, cons(13, cons(1, cons(5, creer_liste())))))
(16, (169, (1, (25, ()))))

###

# Testsbksl-nlassert applique(lambda x: xpy-strx, cons(4, cons(13, cons(1, cons(5, creerpy-undliste()))))) == (16, (169, (1, (25, ()))))bksl-nlassert estpy-undvide(applique(lambda x: xpy-strx, creerpy-undliste()))bksl-nlbksl-nl# Autres testsbksl-nlassert applique(lambda x: x%2, cons(4, cons(13, cons(1, cons(6, creerpy-undliste()))))) == (0, (1, (1, (0, ()))))bksl-nlbksl-nl 5/5

def applique(f, liste):bksl-nl if estpy-undvide(liste):bksl-nl return ...bksl-nl else:bksl-nl return cons(f(...), ...)bksl-nlbksl-nl# Testsbksl-nlbksl-nlassert applique(lambda x: xpy-strx, cons(4, cons(13, cons(1, cons(5, creerpy-undliste()))))) == (16, (169, (1, (25, ()))))bksl-nlassert estpy-undvide(applique(lambda x: xpy-strx, creerpy-undliste()))bksl-nlbksl-nldef applique(f, liste):bksl-nl if estpy-undvide(liste):bksl-nl return creerpy-undliste()bksl-nl else:bksl-nl return cons(f(tete(liste)), applique(f, queue(liste)))bksl-nlbksl-nl

III. Exercices sur la structure abstraite d'arbre binaire⚓︎

On représentera dans tous les exercices qui suivent les arbres binaires ainsi :

l'arbre vide est représenté par None,
un arbre non vide est représenté par un tuple (sous-arbre gauche, valeur, sous-arbre droit).

Ainsi le tuple ((None, 6, None), 15, None) représente l'arbre suivant :

graph TD
    R(15) --> A(6)
    R -.-x B( )
    A -.-x C( )
    A -.-x D( )
    style B display:none;
    style C display:none;
    style D display:none;

Exercice 5 :⚓︎

Fonctions de base à réutiliser dans les autres exercices

Compléter les fonctions est_vide, gauche, droite, racine qui prennent en paramètre un arbre binaire implémenté comme ci-dessus, et renvoient respectivement un booléen indiquant si l'arbre est vide, le sous arbre gauche, le sous arbre droit, la racine de arbre

###

# Testsbksl-nlassert estpy-undvide(None) is Truebksl-nlassert estpy-undvide(((None, 6, None), 15, None)) is Falsebksl-nlassert gauche(((None, 6, None), 15, None)) == (None, 6, None)bksl-nlassert droite(((None, 6, None), 15, None)) is Nonebksl-nlassert droite((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))) == ((None, 7, None), 11, (None, 4, None))bksl-nlassert racine((((None, 6, None), 15, None))) == 15bksl-nlbksl-nl# Autres testsbksl-nlassert gauche((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))) == ((None, 3, None), 8, (None, 5, None))bksl-nlassert racine((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))) == 19bksl-nlbksl-nl 5/5

def estpy-undvide(arbre):bksl-nl ...bksl-nlbksl-nldef gauche(arbre):bksl-nl ...bksl-nlbksl-nldef droite(arbre):bksl-nl ...bksl-nlbksl-nldef racine(arbre):bksl-nl ...bksl-nlbksl-nl# Testsbksl-nlassert estpy-undvide(None) is Truebksl-nlassert estpy-undvide(((None, 6, None), 15, None)) is Falsebksl-nlassert gauche(((None, 6, None), 15, None)) == (None, 6, None)bksl-nlassert droite(((None, 6, None), 15, None)) is Nonebksl-nlassert droite((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))) == ((None, 7, None), 11, (None, 4, None))bksl-nlassert racine((((None, 6, None), 15, None))) == 15bksl-nlbksl-nlbksl-nldef estpy-undvide(arbre):bksl-nl return arbre is Nonebksl-nlbksl-nldef gauche(arbre):bksl-nl return arbre[0]bksl-nlbksl-nldef droite(arbre):bksl-nl return arbre[2]bksl-nlbksl-nldef racine(arbre):bksl-nl return arbre[1]bksl-nlbksl-nlbksl-nl

Exercice 6 :⚓︎

Taille d'un arbre binaire

Compléter la fonction récursive taille qui prend en paramètre arbre, un arbre binaire implémenté comme ci-dessus, et renvoie sa taille.

###

# Testsbksl-nlassert taille(((None, 6, None), 15, None)) == 2bksl-nlassert taille(None) == 0bksl-nlbksl-nl# Autres testsbksl-nlassert taille((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))) == 7bksl-nlbksl-nl 5/5

def taille(arbre):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert taille(((None, 6, None), 15, None)) == 2bksl-nlassert taille(None) == 0bksl-nlbksl-nldef taille(arbre):bksl-nl if estpy-undvide(arbre):bksl-nl return 0bksl-nl else :bksl-nl return 1 + taille(gauche(arbre)) + taille(droite(arbre))bksl-nlbksl-nl

Exercice 7 :⚓︎

Hauteur d'un arbre binaire

On convient que la hauteur d'un arbre ne contenant qu'un élément est 1.

Compléter la fonction récursive hauteur qui prend en paramètre arbre, un arbre binaire implémenté comme ci-dessus, et renvoie sa hauteur.

👉 il faudra utiliser la fonction max de python

###

# Testsbksl-nlassert hauteur(((None, 6, None), 15, None)) == 2bksl-nlassert hauteur((None, 6, None)) == 1bksl-nlassert hauteur(None) == 0bksl-nlbksl-nl# Autres testsbksl-nlassert hauteur((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))) == 3bksl-nlbksl-nl 5/5

def hauteur(arbre):bksl-nl ...bksl-nlbksl-nl# Testsbksl-nlassert hauteur(((None, 6, None), 15, None)) == 2bksl-nlassert hauteur((None, 6, None)) == 1bksl-nlassert hauteur(None) == 0bksl-nlbksl-nldef hauteur(arbre):bksl-nl if estpy-undvide(arbre):bksl-nl return 0bksl-nl else : bksl-nl return 1 + max(hauteur(gauche(arbre)), hauteur(droite(arbre)))bksl-nl bksl-nl

Exercice 8 :⚓︎

Un arbre contient-il un élément ?

Compléter la fonction récursive appartient qui prend en paramètres arbre, un arbre binaire implémenté comme ci-dessus, et un élément valeur. Cette fonction doit renvoyer un booléen indiquant si l'élément valeur est dans l'arbre.

###

# Testsbksl-nlassert appartient(None, 3) is Falsebksl-nlassert appartient(((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))), 2) is Falsebksl-nlassert appartient(((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))), 3) is Truebksl-nlbksl-nl# Autres testsbksl-nlassert appartient(((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))), 12) is Falsebksl-nlassert appartient(((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))), 4) is Truebksl-nlbksl-nl 5/5

def appartient(arbre, valeur):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert appartient(None, 3) is Falsebksl-nlassert appartient(((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))), 2) is Falsebksl-nlassert appartient(((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None)))), 3) is Truebksl-nlbksl-nldef appartient(arbre, valeur):bksl-nl if estpy-undvide(arbre):bksl-nl return Falsebksl-nl elif racine(arbre) == valeur:bksl-nl return Truebksl-nl return appartient(gauche(arbre), valeur) or appartient(droite(arbre), valeur)bksl-nl bksl-nl

Exercice 9:⚓︎

Maximum d'une arbre

Compléter la fonction récursive maximum qui prend en paramètre un arbre binaire non vide implémentée comme ci-dessus arbre, et renvoie le plus grand élément de cet arbre.

👉 il faudra utiliser la fonction max de python. Vous pourrez utiliser la fonction taille vue plus haut.

###

# Testsbksl-nlassert maximum(((None, 6, None), 15, None)) == 15bksl-nlbksl-nl# Autres testsbksl-nlassert maximum(((((None, 3, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None))))) == 19bksl-nlassert maximum(((((None, 23, None), 8, (None, 5, None)), 19, ((None, 7, None), 11, (None, 4, None))))) == 23bksl-nlbksl-nl 5/5

def maximum(arbre):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert maximum(((None, 6, None), 15, None)) == 15bksl-nlbksl-nldef maximum(arbre):bksl-nl if estpy-undvide(arbre):bksl-nl return 0bksl-nl elif taille(arbre) == 1:bksl-nl return racine(arbre)bksl-nl return(max(racine(arbre), maximum(gauche(arbre)), max(racine(arbre), maximum(droite(arbre)))))bksl-nlbksl-nl

Crédits⚓︎

Frédéric Junier, Romain Janvier