“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 126 — #136
i
i
i
i
i
i
i
i
126
3
• Techniques de programmation déclarative
– Construire des programmes en suivant le type. Une fonction qui calcule avec un
type a presque toujours une structure récursive qui reflète de près la structure
récursive du type.
Nous finissons cette section avec un exemple plus grand, l’algorithme de tri par fusion.
Les sections ultérieures montrerons comment rendre plus systématique le développement de fonctions itératives en utilisant des accumulateurs. Ceux-ci nous permettent
d’écrire des fonctions qui sont itératives dès le départ. Notre expérience montre que
ces techniques fonctionnent bien aussi pour les grands programmes déclaratifs.
a) Penser récursivement
Une liste est une structure de données récursive, c’est-à-dire qu’elle est définie par
rapport à une version plus petite d’elle-même. Pour écrire une fonction qui calcule avec
des listes il faut suivre cette structure récursive. La fonction a donc deux parties :
– Un cas de base. Pour les petites listes (par exemple de zéro, un ou deux éléments)
la fonction calcule la réponse directement.
– Un cas récursif. Pour les listes plus grandes, la fonction calcule le résultat en
utilisant les résultats d’une ou plusieurs listes plus petites.
Comme premier exemple, nous prenons une fonction récursive qui calcule la longueur
d’une liste :
fun {Length Ls}
case Ls of nil then 0
[] _|Lr then 1+{Length Lr} end
end
{Browse {Length [a b c]}}
Sa signature de type est fun {$ List} : Int : une fonction qui prend une liste
et qui renvoie un entier. Le cas de base est la liste vide nil, pour laquelle la fonction
renvoie 0. Le cas récursif couvre les listes non vides. Pour une liste avec longueur n,
sa queue a une longueur n − 1. Comme elle est plus petite que la liste originale, le
programme terminera.
Notre deuxième exemple est la fonction Append qui fait la concaténation de deux
listes Ls et Ms pour construire une troisième liste. Sur quel argument faisons-nous
l’induction, le premier ou le deuxième ? On peut démontrer que l’induction doit être
faite sur le premier argument. Voici la fonction Append :
fun {Append Ls Ms}
case Ls of nil then Ms
[] X|Lr then X|{Append Lr Ms} end
end
i
i
i
i
i
i
i
i
126
3
• Techniques de programmation déclarative
– Construire des programmes en suivant le type. Une fonction qui calcule avec un
type a presque toujours une structure récursive qui reflète de près la structure
récursive du type.
Nous finissons cette section avec un exemple plus grand, l’algorithme de tri par fusion.
Les sections ultérieures montrerons comment rendre plus systématique le développement de fonctions itératives en utilisant des accumulateurs. Ceux-ci nous permettent
d’écrire des fonctions qui sont itératives dès le départ. Notre expérience montre que
ces techniques fonctionnent bien aussi pour les grands programmes déclaratifs.
a) Penser récursivement
Une liste est une structure de données récursive, c’est-à-dire qu’elle est définie par
rapport à une version plus petite d’elle-même. Pour écrire une fonction qui calcule avec
des listes il faut suivre cette structure récursive. La fonction a donc deux parties :
– Un cas de base. Pour les petites listes (par exemple de zéro, un ou deux éléments)
la fonction calcule la réponse directement.
– Un cas récursif. Pour les listes plus grandes, la fonction calcule le résultat en
utilisant les résultats d’une ou plusieurs listes plus petites.
Comme premier exemple, nous prenons une fonction récursive qui calcule la longueur
d’une liste :
fun {Length Ls}
case Ls of nil then 0
[] _|Lr then 1+{Length Lr} end
end
{Browse {Length [a b c]}}
Sa signature de type est fun {$ List} : Int : une fonction qui prend une liste
et qui renvoie un entier. Le cas de base est la liste vide nil, pour laquelle la fonction
renvoie 0. Le cas récursif couvre les listes non vides. Pour une liste avec longueur n,
sa queue a une longueur n − 1. Comme elle est plus petite que la liste originale, le
programme terminera.
Notre deuxième exemple est la fonction Append qui fait la concaténation de deux
listes Ls et Ms pour construire une troisième liste. Sur quel argument faisons-nous
l’induction, le premier ou le deuxième ? On peut démontrer que l’induction doit être
faite sur le premier argument. Voici la fonction Append :
fun {Append Ls Ms}
case Ls of nil then Ms
[] X|Lr then X|{Append Lr Ms} end
end