Requête Prolog: quelle est l'importance de l'addition pour les requêtes récursives

Question

J'essaye d'écrire un prédicat pour trouver le nième élément d'une liste.

Au départ, j'ai écrit quelque chose comme ceci:

nth([X|_], 0, X).
nth([_|T],N,Z):- N > 0, nth(T, M, Z), N is M + 1.

Cela fonctionne pour les requêtes telles que nth([1, 2, 3, 4, 5], 0, X).mais pour les requêtes telles que nth([1, 2, 3, 4, 5], N, 1)., j'obtiens une erreur "arguments insuffisamment instanciés" après avoir entré ";" après avoir obtenu la réponse. Je sais qu'il n'y aura que 1 ans dans ce cas, mais par souci d'exhaustivité, je veux savoir pourquoi.

J'ai lu sur le débordement de pile ici que ce qui suit est une meilleure solution:

nth([X|_], 0, X) :- !.
nth([_|Y], N, Z) :- N > 0, M is N-1, nth(Y, M, Z).

Je veux comprendre pourquoi M is N-1, nth(Y, M, Z).fait une différence par rapport au nth(T, M, Z), N is M + 1dans ma réponse.

PS: Je pense que le titre de la question peut être amélioré, mais je ne sais pas comment. Si vous avez des suggestions, faites-le moi savoir!

Answer 1

is/2n'est pas un solveur de contraintes complet. Donc, N is M + 1et M is N - 1semblent être équivalents, mais ils ne le sont pas. Le premier ne réussit que lorsque M est instancié et le second lorsque N est instancié. Avez-vous essayé votre solution avec des indices autres zéro? Ils ne fonctionneront pas. Vous pouvez utiliser à la plus(1, M, N)place de l'un ou l'autre pour le faire fonctionner. L'ordre des clauses est également important, il plus(1, M, N)devrait donc être avant l'appel récursif à nth.

nth([X|_], 0, X).
nth([_|T],N,Z):- N > 0, plus(1, M, N), nth(T, M, Z).

Si N > 0, nth(T, M, Z), plus(1, M, N)votre clause est ordonnée, votre programme essaiera de satisfaire en nth(T, M, Z)premier et provoquera une erreur non corroborée à N > 0puisque M n'est pas déjà instancié.

De plus, aucun des programmes ne fonctionnera dans le cas génératif.