“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 128 — #138
i
i
i
i
i
i
i
i
128
3
• Techniques de programmation déclarative
Son type est fun {$ List Int} : Int. La liste d’entrée doit contenir des entiers
parce que SumList utilise l’entier 0 dans sa définition. L’appel suivant
{Browse {SumList [1 2 3]}}
affiche 6. Comme Xs a deux valeurs possibles, à savoir nil ou X|Xr, il est normal
d’utiliser une instruction case. Comme dans l’exemple Nth, ne pas utiliser une clause
else dans la case lèvera une exception si l’argument est en dehors du domaine de
la fonction. Par exemple :
{Browse {SumList 1|foo}}
lève une exception parce que 1|foo n’est pas une liste, et la définition de SumList
suppose que son entrée est une liste.
c) Les définitions naïves sont parfois lentes
Nous définissons une fonction pour inverser les éléments d’une liste. Nous commençons avec une définition récursive de l’inverse d’une liste :
– L’inverse de nil est nil.
– L’inverse de X|Xs est Z, où
l’inverse de Xs est Ys et
la concaténation de Ys et [X] est Z.
Cette définition est correcte ; on peut vérifier que le premier élément X devient le
dernier et pour les autres on utilise un argument inductif. En suivant cette définition
récursive, nous pouvons tout de suite écrire une fonction :
fun {Reverse Xs}
case Xs of nil then nil
[] X|Xr then {Append {Reverse Xr} [X]} end
end
Son type est fun {$ List} : List. Cette fonction est-elle efficace ? Pour
répondre à cette question, nous calculons son temps d’exécution avec une liste d’entrée de longueur n. Nous pouvons faire ce calcul rigoureusement avec les techniques
de la section 3.6. Mais même sans ces techniques, nous pouvons voir intuitivement ce
qui se passe. Il y a n appels récursifs suivis par n appels à Append. Chaque appel
d’Append prend une liste de longueur n/2 en moyenne. Le temps total d’exécution
est donc proportionnel à n · n/2, à savoir n
2 . C’est assez lent. Nous nous attendrions à
ce que l’inversion d’une liste prenne un temps proportionnel à la longueur de la liste
et pas à son carré.
i
i
i
i
i
i
i
i
128
3
• Techniques de programmation déclarative
Son type est fun {$ List Int} : Int. La liste d’entrée doit contenir des entiers
parce que SumList utilise l’entier 0 dans sa définition. L’appel suivant
{Browse {SumList [1 2 3]}}
affiche 6. Comme Xs a deux valeurs possibles, à savoir nil ou X|Xr, il est normal
d’utiliser une instruction case. Comme dans l’exemple Nth, ne pas utiliser une clause
else dans la case lèvera une exception si l’argument est en dehors du domaine de
la fonction. Par exemple :
{Browse {SumList 1|foo}}
lève une exception parce que 1|foo n’est pas une liste, et la définition de SumList
suppose que son entrée est une liste.
c) Les définitions naïves sont parfois lentes
Nous définissons une fonction pour inverser les éléments d’une liste. Nous commençons avec une définition récursive de l’inverse d’une liste :
– L’inverse de nil est nil.
– L’inverse de X|Xs est Z, où
l’inverse de Xs est Ys et
la concaténation de Ys et [X] est Z.
Cette définition est correcte ; on peut vérifier que le premier élément X devient le
dernier et pour les autres on utilise un argument inductif. En suivant cette définition
récursive, nous pouvons tout de suite écrire une fonction :
fun {Reverse Xs}
case Xs of nil then nil
[] X|Xr then {Append {Reverse Xr} [X]} end
end
Son type est fun {$ List} : List. Cette fonction est-elle efficace ? Pour
répondre à cette question, nous calculons son temps d’exécution avec une liste d’entrée de longueur n. Nous pouvons faire ce calcul rigoureusement avec les techniques
de la section 3.6. Mais même sans ces techniques, nous pouvons voir intuitivement ce
qui se passe. Il y a n appels récursifs suivis par n appels à Append. Chaque appel
d’Append prend une liste de longueur n/2 en moyenne. Le temps total d’exécution
est donc proportionnel à n · n/2, à savoir n
2 . C’est assez lent. Nous nous attendrions à
ce que l’inversion d’une liste prenne un temps proportionnel à la longueur de la liste
et pas à son carré.