“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 135 — #145
i
i
i
i
i
i
i
i
3.4 La programmation avec la récursion
135
fun {MergeSort Xs}
case Xs of nil then nil
[] [X] then [X]
else Ys Zs in
{Split Xs Ys Zs}
{Merge {MergeSort Ys} {MergeSort Zs}}
end
end
Son type est fun {$ List T} : List T avec la même restriction sur T que
Merge. La découpe de la liste d’entrée s’arrête avec les listes de longueur zéro et un,
qui peuvent être triées immédiatement.
3.4.3 Les accumulateurs
Nous avons vu comment programmer des fonctions de liste simples et comment les
rendre itératives. La programmation déclarative pratique est généralement abordée
d’une autre façon, par la définition des fonctions qui sont itératives dès le début.
L’idée est que le programme porte un état avec lui et le transforme juste avant chaque
appel, sans jamais le transformer au moment d’un retour. Cela garde l’optimisation
terminale. Un état S est représenté en ajoutant une paire d’arguments, S1 et Sn, à
chaque procédure. Cette paire s’appelle un accumulateur. S1 représente l’état à
l’entrée et Sn représente l’état à la sortie. Ainsi, chaque procédure est écrite dans le
style suivant :
proc {P X S1 ?Sn}
if {BaseCase X} then Sn=S1
else
{P1 S1 S2}
{P2 S2 S3}
{P3 S3 Sn}
end
end
Comme le cas de base ne fait pas de calculs, l’état à la sortie est le même que l’état
à l’entrée (Sn=S1). Le cas récursif enfile l’état dans chaque appel de procédure (P1,
P2 et P3) et finalement le retourne à P. La figure 3.10 montre ce qui se passe. Chaque
flèche représente un argument. Nous faisons un enfilage d’état : la sortie de chaque
procédure est l’entrée de la procédure suivante. Enfiler veut dire passer un fil ; ici on
passe l’accumulateur comme un fil dans un tissu. Le technique d’enfiler un état dans
les appels de procédure imbriqués s’appelle la programmation par accumulateur.
La programmation par accumulateur est utilisée dans les fonctions IterLength
et IterReverse que nous avons vues auparavant. Dans ces fonctions la structure
© 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
135
fun {MergeSort Xs}
case Xs of nil then nil
[] [X] then [X]
else Ys Zs in
{Split Xs Ys Zs}
{Merge {MergeSort Ys} {MergeSort Zs}}
end
end
Son type est fun {$ List T} : List T avec la même restriction sur T que
Merge. La découpe de la liste d’entrée s’arrête avec les listes de longueur zéro et un,
qui peuvent être triées immédiatement.
3.4.3 Les accumulateurs
Nous avons vu comment programmer des fonctions de liste simples et comment les
rendre itératives. La programmation déclarative pratique est généralement abordée
d’une autre façon, par la définition des fonctions qui sont itératives dès le début.
L’idée est que le programme porte un état avec lui et le transforme juste avant chaque
appel, sans jamais le transformer au moment d’un retour. Cela garde l’optimisation
terminale. Un état S est représenté en ajoutant une paire d’arguments, S1 et Sn, à
chaque procédure. Cette paire s’appelle un accumulateur. S1 représente l’état à
l’entrée et Sn représente l’état à la sortie. Ainsi, chaque procédure est écrite dans le
style suivant :
proc {P X S1 ?Sn}
if {BaseCase X} then Sn=S1
else
{P1 S1 S2}
{P2 S2 S3}
{P3 S3 Sn}
end
end
Comme le cas de base ne fait pas de calculs, l’état à la sortie est le même que l’état
à l’entrée (Sn=S1). Le cas récursif enfile l’état dans chaque appel de procédure (P1,
P2 et P3) et finalement le retourne à P. La figure 3.10 montre ce qui se passe. Chaque
flèche représente un argument. Nous faisons un enfilage d’état : la sortie de chaque
procédure est l’entrée de la procédure suivante. Enfiler veut dire passer un fil ; ici on
passe l’accumulateur comme un fil dans un tissu. Le technique d’enfiler un état dans
les appels de procédure imbriqués s’appelle la programmation par accumulateur.
La programmation par accumulateur est utilisée dans les fonctions IterLength
et IterReverse que nous avons vues auparavant. Dans ces fonctions la structure
© Dunod – La photocopie non autorisée est un délit