“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 127 — #137
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
127
Sa signature de type est fun {$ List List} : List. Cette fonction suit exactement les deux propriétés suivantes de la concaténation :
append(nil, m) = m
append(x|l, m) = x | append(l, m)
Le cas récursif appelle toujours Append avec un premier argument plus petit, donc le
programme terminera.
b) Les fonctions récursives et leurs domaines
Définissons la fonction Nth pour obtenir le nième élément d’une liste.
fun {Nth Xs N}
if N==1 then Xs.1
elseif N>1 then {Nth Xs.2 N-1} end
end
Son type est fun {$ List Int} : Value. Souvenez-vous qu’une liste Xs est
soit nil soit un tuple X|Y avec deux arguments. Xs.1 est égal à X et Xs.2 est égal
à Y. Que se passe-t-il quand on fait ceci ? :
{Browse {Nth [a b c d] 5}}
La liste n’a que quatre éléments. Tenter d’obtenir le cinquième élément veut dire tenter
de faire Xs.1 ou Xs.2 avec Xs=nil, ce qui lèvera une exception. Une exception
sera levée aussi si N n’est pas plus grand que zéro, par exemple si N=0. C’est parce
qu’il n’y a pas de clause else dans l’instruction if.
Cette fonction est un exemple d’une technique plus générale : utiliser des instructions qui lèvent des exceptions pour les valeurs en dehors de leurs domaines. Nous
voudrions que la fonction lève une exception quand elle est appelée avec une entrée en
dehors de son domaine. Nous ne pouvons pas garantir qu’une exception sera toujours
levée dans ce cas, par exemple {Nth 1|2|3 2} renvoie 2 mais 1|2|3 n’est pas
une liste. De telles garanties sont difficiles à obtenir sans faire plus de calculs. On peut
parfois les obtenir dans les langages statiquement typés.
L’instruction case se comporte correctement à cet égard. L’utilisation d’une
instruction case pour traverser récursivement une liste lèvera une exception quand
l’argument n’est pas une liste. Par exemple, nous pouvons définir une fonction qui
additionne tous les éléments d’une liste d’entiers :
fun {SumList Xs}
case Xs of nil then 0
[] X|Xr then X+{SumList Xr} end
end
© 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
127
Sa signature de type est fun {$ List List} : List. Cette fonction suit exactement les deux propriétés suivantes de la concaténation :
append(nil, m) = m
append(x|l, m) = x | append(l, m)
Le cas récursif appelle toujours Append avec un premier argument plus petit, donc le
programme terminera.
b) Les fonctions récursives et leurs domaines
Définissons la fonction Nth pour obtenir le nième élément d’une liste.
fun {Nth Xs N}
if N==1 then Xs.1
elseif N>1 then {Nth Xs.2 N-1} end
end
Son type est fun {$ List Int} : Value. Souvenez-vous qu’une liste Xs est
soit nil soit un tuple X|Y avec deux arguments. Xs.1 est égal à X et Xs.2 est égal
à Y. Que se passe-t-il quand on fait ceci ? :
{Browse {Nth [a b c d] 5}}
La liste n’a que quatre éléments. Tenter d’obtenir le cinquième élément veut dire tenter
de faire Xs.1 ou Xs.2 avec Xs=nil, ce qui lèvera une exception. Une exception
sera levée aussi si N n’est pas plus grand que zéro, par exemple si N=0. C’est parce
qu’il n’y a pas de clause else dans l’instruction if.
Cette fonction est un exemple d’une technique plus générale : utiliser des instructions qui lèvent des exceptions pour les valeurs en dehors de leurs domaines. Nous
voudrions que la fonction lève une exception quand elle est appelée avec une entrée en
dehors de son domaine. Nous ne pouvons pas garantir qu’une exception sera toujours
levée dans ce cas, par exemple {Nth 1|2|3 2} renvoie 2 mais 1|2|3 n’est pas
une liste. De telles garanties sont difficiles à obtenir sans faire plus de calculs. On peut
parfois les obtenir dans les langages statiquement typés.
L’instruction case se comporte correctement à cet égard. L’utilisation d’une
instruction case pour traverser récursivement une liste lèvera une exception quand
l’argument n’est pas une liste. Par exemple, nous pouvons définir une fonction qui
additionne tous les éléments d’une liste d’entiers :
fun {SumList Xs}
case Xs of nil then 0
[] X|Xr then X+{SumList Xr} end
end
© Dunod – La photocopie non autorisée est un délit