<div class="notebook">
<div class="nb-cell markdown" name="md1">
# Plus ou Moins 1 ... ?
La question vient d'un étudiant, "Quand faut-il faire +1, quand faut-il faire -1 ? est-ce que c'est dans l'appel récursif ou dans le retour ?"
Réponse : ça dépend ...
Prenons l'exemple du calcul de la longueur d'une liste.
## Longueur d'une liste, première version (avec "+" dans le retour)
En prolog classique (ou presque, j'utiliserai des contraintes comme des "is") :
</div>
<div class="nb-cell program" data-background="true" name="p1">
:- use_module(library(clpq)).
</div>
<div class="nb-cell program" data-background="true" name="p2">
longueurClassique([],0).
longueurClassique([_E|L],N):-
longueurClassique(L,M),
{N=M+1}.
</div>
<div class="nb-cell query" name="q1">
longueurClassique([1,2,2,3,3,3],N).
</div>
<div class="nb-cell markdown" name="md3">
il fut un temps où l'on pouvait écrire (en PrologIII)
</div>
<div class="nb-cell program" data-background="true" name="p4">
longueurClassiqueP3([],0).
longueurClassiqueP3([_E|L],N+1):-
longueurClassiqueP3(L,N).
</div>
<div class="nb-cell markdown" name="md4">
mais à l'évaluation, maintenant cela donne :
</div>
<div class="nb-cell query" name="q2">
longueurClassiqueP3([1,2,2,3,3,3],N).
</div>
<div class="nb-cell markdown" name="md5">
ce n'est pas joli
pour retrouver le résultat, il faut écrire :
</div>
<div class="nb-cell query" name="q3">
longueurClassiqueP3([1,2,2,3,3,3],N), Resultat is N.
</div>
<div class="nb-cell markdown" name="md2">
voila, ça marche, mais ce n'est pas direct (et pas général, cf. la suite)
## Seconde version (avec "+" dans l'appel => accumulateur)
Autre méthode, en utilisant un accumulateur (j'aime moins) :
</div>
<div class="nb-cell program" data-background="true" name="p3">
longueurAccumulateur(L,N) :-
lgAcc(L,0,N).
lgAcc([],N,N).
lgAcc([_E|L],Acc,N):-
{Bcc=Acc+1},
lgAcc(L,Bcc,N).
</div>
<div class="nb-cell query" name="q4">
longueurAccumulateur([1,2,2,3,3,3],N).
</div>
<div class="nb-cell markdown" name="md14">
ou en intégrant le calcul (à la manière de PrologIII) :
</div>
<div class="nb-cell program" name="p10">
longueurAccumulateurP3(L,N) :-
lgAccP3(L,0,N).
lgAccP3([],N,N).
lgAccP3([_E|L],Acc,N):-
lgAccP3(L,Acc+1,N).
</div>
<div class="nb-cell query" name="q10">
longueurAccumulateurP3([1,2,2,3,3,3],N).
</div>
<div class="nb-cell markdown" name="md16">
ou pour éviter d'avoir à faire le calcul final à la main (on peut aussi mettre un "is"):
</div>
<div class="nb-cell markdown" name="md15">
</div>
<div class="nb-cell program" name="p11">
longueurAccumulateurP3(L,N) :-
lgAccP3(L,0,N).
lgAccP3([],N,M) :- {M=N}.
lgAccP3([_E|L],Acc,N):-
lgAccP3(L,Acc+1,N).
</div>
<div class="nb-cell query" name="q9">
longueurAccumulateurP3([1,2,2,3,3,3],N).
</div>
<div class="nb-cell markdown" name="md6">
Donc, on dirait qu'il faut utiliser un +.
## Troisième version (avec "-" dans l'appel et contraintes [pas d'accumulateur])
Oui, mais voilà, depuis que l'on a les contraintes on peut écrire :
</div>
<div class="nb-cell program" name="p5">
longueurContrainte([],0).
longueurContrainte([_E|L],N):-
longueurContrainte(L,M),
{M=N-1}.
</div>
<div class="nb-cell markdown" name="md13">
ou ce qui est plus extraordinaire (car cela demande vraiment des contraintes) :
</div>
<div class="nb-cell program" data-background="true" name="p9">
longueurContrainte([],0).
longueurContrainte([_E|L],N):-
{M=N-1},
longueurContrainte(L,M).
</div>
<div class="nb-cell query" name="q5">
longueurContrainte([1,2,2,3,3,3],N).
</div>
<div class="nb-cell markdown" name="md7">
ce qui pourrait s'écrire :
</div>
<div class="nb-cell program" name="p6">
longueurContrainteP3([],0).
longueurContrainteP3([_E|L],N):-
longueurContrainteP3(L,N-1).
</div>
<div class="nb-cell markdown" name="md8">
mais vous comprenez :
</div>
<div class="nb-cell query" name="q6">
longueurContrainteP3([1,2,2,3,3,3],N).
</div>
<div class="nb-cell markdown" name="md17">
et là, pas de "is" ... c'est plus grave (les contraintes sont obligatoires, en PrologIII elles étaient "juste" mieux intégrées)
</div>
<div class="nb-cell program" name="p12">
longueurContrainteP3([],S) :- {S=0}.
longueurContrainteP3([_E|L],N):-
longueurContrainteP3(L,N-1).
</div>
<div class="nb-cell query" name="q11">
longueurContrainteP3([1,2,2,3,3,3],N).
</div>
<div class="nb-cell markdown" name="md9">
## Quatrième version (avec "-" dans le retour, pour contraintes et accumulateur)
Il y a aussi une seconde méthode avec accumulateur (et un "-") :
</div>
<div class="nb-cell program" data-background="true" name="p7">
longueurAccumulateurContrainte(L,N) :-
lgAccContr(L,0,N).
lgAccContr([],N,N).
lgAccContr([_E|L],Acc,N):-
lgAccContr(L,Bcc,N),
{Acc=Bcc-1}.
</div>
<div class="nb-cell query" name="q7">
longueurAccumulateurContrainte([1,2,2,3,3,3],N).
</div>
<div class="nb-cell markdown" name="md10">
ce qui pourrait s'écrire en PrologIII :
</div>
<div class="nb-cell program" name="p8">
longueurAccumulateurContrainteP3(L,N) :-
lgAccContrP3(L,Zero,N), {Zero=0}.
lgAccContrP3([],N,M):-{N=M}.
lgAccContrP3([_E|L],Acc-1,N):-
lgAccContrP3(L,Acc,N).
</div>
<div class="nb-cell markdown" name="md11">
mais bon ...
</div>
<div class="nb-cell query" name="q8">
longueurAccumulateurContrainteP3([1,2,2,3,3,3],N).
</div>
<div class="nb-cell markdown" name="md12">
Bref, on restera aux versions avec contraintes pour cette seconde série de calcul de longueur avec "-" (version 3 et 4)
## Conclusions
* on peut écrire avec "+" ou "-"
* que ce soit lors de l'appel ou du retour
* il y a des versions que l'on peut préférer, plus lisibles, plus efficaces, ...
*
Pour ma part, par ordre de préférence (ma préférée en premier) :
* longueurClassiqueP3 (version 1)
* longueurContrainteP3 (version 3)
* et loin derrière
* longueurAccumulateurP3 (version 2)
*
remarque supplémentaires, en fait, même sans contraintes on aurait pu trouver des cas avec des "+" et des "-" pour le même résultat, ...
Continuons un tout petit peu, il y a encore d'autres façons de calculer la longueur d'une liste. Par exemple, on peut trouver que les versions précédentes sont logiques, car il y a un invariant entre la longueur intermédiaire calculée et la longueur de la liste courante. Et donc, si on change l'une il faut changer l'autre. Est-ce que c'est encore le cas ci-après (réponse : oui, mais c'est plus compliqué de le voir car la liste courante ne change pas ! il y a une autre liste, annexe qui change mais comme est-elle en lien avec la liste dont on cherche la longueur ?)
</div>
<div class="nb-cell program" name="p13">
longueurAnnexe(L,N) :-
lgAnnexe(L,N,[], 0).
lgAnnexe(L,N,L, NA):- {N=NA}.
lgAnnexe(L,N,LAnnexe, NAnnexe) :-
lgAnnexe(L,N,[_A|LAnnexe], NAnnexe+1).
</div>
<div class="nb-cell query" name="q12">
longueurAnnexe([1,2,3,2,1],N), !.
</div>
<div class="nb-cell markdown" name="md18">
(attention, il faut s'arréter à la première solution [par exemple en ajoutant un cut, comme j'ai fait], ou avec des contraintes de taille, sinon cela boucle)
</div>
</div>