“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 5 — #15
i
i
i
i
i
i
i
i
1.4 Les listes
5
L’abstraction fonctionnelle
La définition de Comb utilise la fonction existante Fact. Il est toujours possible
d’utiliser les fonctions existantes pour définir de nouvelles fonctions. L’utilisation de
fonctions pour construire de nouvelles fonctions s’appelle l’abstraction fonctionnelle.
De cette façon, un programme a une structure d’oignon, avec des couches successives
de fonctions qui appellent des fonctions. Ce style de programmation est étudié dans le
chapitre 3.
1.4 LES LISTES
Nous pouvons maintenant calculer des fonctions des entiers. Mais un entier n’est pas
vraiment grand chose. Supposons que nous voulions effectuer un calcul avec beaucoup
d’entiers. Par exemple, si nous voulons calculer le triangle de Pascal
1 :
1
1
1
1
2
1
1
3
3
1
1
4
6
4
1
. . . . . . . . . . .
La première rangée contient l’entier 1. Chaque élément est la somme des deux éléments
directement au-dessus à gauche et à droite. (S’il n’y a pas d’élément, comme sur les
bords, alors on prend zéro.) Nous voulons définir une fonction qui calcule la nième
rangée en une fois. La nième rangée contient n entiers. Nous pouvons résoudre le
problème en utilisant des listes d’entiers.
Une liste est une séquence d’éléments, avec une syntaxe délimitée à gauche et à
droite par des crochets, comme [5 6 7 8]. Pour des raisons historiques, la liste
vide est écrite nil (et non []). Une liste peut être affichée comme un nombre :
{Browse [5 6 7 8]}
La notation [5 6 7 8] est un raccourci. Une liste est en réalité une chaîne de liens,
où chaque lien contient deux choses : un élément de liste et une référence vers le reste
de la chaîne. Les listes sont toujours créées élément par élément, en commençant avec
nil et en ajoutant des liens un à un. Un nouveau lien est écrit H|T, où H est le nouvel
élément et T est l’ancienne chaîne. Construisons une liste. Nous commençons avec
1. Le triangle de Pascal est un concept important de l’analyse combinatoire. Les éléments de la nième
rangée de ce triangle sont les combinaisons
n
k
, où k va de 0 à n. Il y a un rapport fort avec le binôme de
Newton, qui dit (x + y)
n =
n
k=0
n
k
x
k y
(n−k) pour tout entier n 0.
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
1.4 Les listes
5
L’abstraction fonctionnelle
La définition de Comb utilise la fonction existante Fact. Il est toujours possible
d’utiliser les fonctions existantes pour définir de nouvelles fonctions. L’utilisation de
fonctions pour construire de nouvelles fonctions s’appelle l’abstraction fonctionnelle.
De cette façon, un programme a une structure d’oignon, avec des couches successives
de fonctions qui appellent des fonctions. Ce style de programmation est étudié dans le
chapitre 3.
1.4 LES LISTES
Nous pouvons maintenant calculer des fonctions des entiers. Mais un entier n’est pas
vraiment grand chose. Supposons que nous voulions effectuer un calcul avec beaucoup
d’entiers. Par exemple, si nous voulons calculer le triangle de Pascal
1 :
1
1
1
1
2
1
1
3
3
1
1
4
6
4
1
. . . . . . . . . . .
La première rangée contient l’entier 1. Chaque élément est la somme des deux éléments
directement au-dessus à gauche et à droite. (S’il n’y a pas d’élément, comme sur les
bords, alors on prend zéro.) Nous voulons définir une fonction qui calcule la nième
rangée en une fois. La nième rangée contient n entiers. Nous pouvons résoudre le
problème en utilisant des listes d’entiers.
Une liste est une séquence d’éléments, avec une syntaxe délimitée à gauche et à
droite par des crochets, comme [5 6 7 8]. Pour des raisons historiques, la liste
vide est écrite nil (et non []). Une liste peut être affichée comme un nombre :
{Browse [5 6 7 8]}
La notation [5 6 7 8] est un raccourci. Une liste est en réalité une chaîne de liens,
où chaque lien contient deux choses : un élément de liste et une référence vers le reste
de la chaîne. Les listes sont toujours créées élément par élément, en commençant avec
nil et en ajoutant des liens un à un. Un nouveau lien est écrit H|T, où H est le nouvel
élément et T est l’ancienne chaîne. Construisons une liste. Nous commençons avec
1. Le triangle de Pascal est un concept important de l’analyse combinatoire. Les éléments de la nième
rangée de ce triangle sont les combinaisons
n
k
, où k va de 0 à n. Il y a un rapport fort avec le binôme de
Newton, qui dit (x + y)
n =
n
k=0
n
k
x
k y
(n−k) pour tout entier n 0.
© Dunod – La photocopie non autorisée est un délit