“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 133 — #143
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
133
NestedList2 T : := nil
| |NestedList2 T ´|´ NestedList2 T
| T
De nouveau, il faut ajouter la condition que T n’est ni nil ni une paire de liste.
Remarquez la différence subtile entre NestedList T et NestedList2 T ! En suivant
la définition de NestedList2 T nous obtenons une autre fonction LengthL2 plus
simple :
fun {LengthL2 Xs}
case Xs of nil then 0
[] X|Xr then {LengthL2 X}+{LengthL2 Xr}
else 1 end
end
Quelle est la différence entre LengthL et LengthL2 ? Nous la déduisons en comparant les types NestedList T et NestedList2 T. Une NestedList T est toujours une
liste mais une NestedList2 T peut aussi avoir le type T. Donc l’appel {LengthL2
foo} est légal (il renvoie 1), mais {LengthL foo} est illégal (il lève une exception).
Du point de vue du comportement désiré (l’entrée doit être une liste), nous concluons
qu’il est raisonnable de considérer LengthL2 comme erronée et LengthL comme
correcte.
Il y a une leçon importante à retenir ici. La définition d’un type récursif doit être
faite avant d’écrire la fonction qui l’utilise. Sinon il est facile de se laisser tromper
par une fonction qui semble simple mais qui est erronée. C’est vrai aussi dans les
langages fonctionnels qui font de l’inférence de types, comme Standard ML et Haskell.
L’inférence de types peut vérifier qu’un type récursif est utilisé correctement, mais la
conception d’un type récursif reste sous la responsabilité du programmeur.
g) Le tri par fusion
Nous définissons une fonction qui prend une liste de nombres ou atomes et qui renvoie
une nouvelle liste triée en ordre croissant. Elle utilise l’opérateur de comparaison
<, tous les éléments doivent donc être du même type (tous des entiers, flottants ou
atomes). Nous utilisons l’algorithme de tri par fusion (« mergesort »), qui est efficace
et qui peut être programmé facilement dans un modèle déclaratif. L’algorithme de tri
par fusion est basé sur une stratégie simple qui s’appelle diviser pour régner :
– Découpez la liste en deux listes d’environ la même longueur.
– Utilisez le tri par fusion pour trier les deux listes.
– Fusionnez les deux listes triées pour obtenir le résultat final.
La figure 3.9 montre la structure récursive de cette stratégie. Le tri par fusion est
efficace parce que les opérations de découpe et de fusion sont toutes les deux itératives
© Dunod – La photocopie non autorisée est un délit
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
133
NestedList2 T : := nil
| |NestedList2 T ´|´ NestedList2 T
| T
De nouveau, il faut ajouter la condition que T n’est ni nil ni une paire de liste.
Remarquez la différence subtile entre NestedList T et NestedList2 T ! En suivant
la définition de NestedList2 T nous obtenons une autre fonction LengthL2 plus
simple :
fun {LengthL2 Xs}
case Xs of nil then 0
[] X|Xr then {LengthL2 X}+{LengthL2 Xr}
else 1 end
end
Quelle est la différence entre LengthL et LengthL2 ? Nous la déduisons en comparant les types NestedList T et NestedList2 T. Une NestedList T est toujours une
liste mais une NestedList2 T peut aussi avoir le type T. Donc l’appel {LengthL2
foo} est légal (il renvoie 1), mais {LengthL foo} est illégal (il lève une exception).
Du point de vue du comportement désiré (l’entrée doit être une liste), nous concluons
qu’il est raisonnable de considérer LengthL2 comme erronée et LengthL comme
correcte.
Il y a une leçon importante à retenir ici. La définition d’un type récursif doit être
faite avant d’écrire la fonction qui l’utilise. Sinon il est facile de se laisser tromper
par une fonction qui semble simple mais qui est erronée. C’est vrai aussi dans les
langages fonctionnels qui font de l’inférence de types, comme Standard ML et Haskell.
L’inférence de types peut vérifier qu’un type récursif est utilisé correctement, mais la
conception d’un type récursif reste sous la responsabilité du programmeur.
g) Le tri par fusion
Nous définissons une fonction qui prend une liste de nombres ou atomes et qui renvoie
une nouvelle liste triée en ordre croissant. Elle utilise l’opérateur de comparaison
<, tous les éléments doivent donc être du même type (tous des entiers, flottants ou
atomes). Nous utilisons l’algorithme de tri par fusion (« mergesort »), qui est efficace
et qui peut être programmé facilement dans un modèle déclaratif. L’algorithme de tri
par fusion est basé sur une stratégie simple qui s’appelle diviser pour régner :
– Découpez la liste en deux listes d’environ la même longueur.
– Utilisez le tri par fusion pour trier les deux listes.
– Fusionnez les deux listes triées pour obtenir le résultat final.
La figure 3.9 montre la structure récursive de cette stratégie. Le tri par fusion est
efficace parce que les opérations de découpe et de fusion sont toutes les deux itératives
© Dunod – La photocopie non autorisée est un délit