“doc” (Col. : Science Sup 17x24) — 2007/7/19 — 18:18 — page 132 — #142
i
i
i
i
i
i
i
i
132
3
• Techniques de programmation déclarative
Pour éviter l’ambiguïté, il faut ajouter une condition sur T, par exemple que T n’est
ni nil ni une paire de liste. Maintenant nous pouvons écrire la fonction {LengthL
NestedList T} : Int qui compte le nombre d’éléments dans une liste imbriquée.
En suivant la définition du type nous obtenons le squelette suivant :
fun {LengthL Xs}
case Xs of nil then expr
[] X|Xr andthen {IsList X} then
expr+expr % Appels r´ ecursifs pour X et Xr
[] X|Xr then
expr % Appel r´ ecursif pour Xr
end
end
(On peut omettre {Not {IsList X}} dans la troisième clause parce que c’est
une conséquence de la négation de la deuxième clause.) Ici {IsList X} est une
fonction qui vérifie si X est nil ou une paire de liste :
fun {IsList X} X==nil orelse {IsCons X} end
fun {IsCons X}
case X of _|_ then true else false end end
Compléter le squelette donne la fonction suivante :
fun {LengthL Xs}
case Xs of nil then 0
[] X|Xr andthen {IsList X} then
{LengthL X}+{LengthL Xr}
[] X|Xr then
1+{LengthL Xr}
end
end
Voici deux appels :
X=[[1 2] 4 nil [[5] 10]]
{Browse {LengthL X}}
{Browse {LengthL [X X]}}
Qu’est-ce qui est affiché par ces appels ?
En utilisant une autre définition du type pour les listes imbriquées nous obtenons une
autre fonction de longueur. Par exemple, nous pouvons définir le type NestedList2 T
comme ceci :