Liste des entiers et boucle infinie dans Prolog CLPFD

Question

Supposons que je veux représenter les entiers comme tels: integer:Sign:[FirstDigit,SecondDigit,...]. Par exemple, 42 serait représenté par integer:positive:[4,2].

J'ai besoin d'un prédicat qui génère la valeur de l'entier basé sur cette représentation et vice versa.

Voici ce que je suis venu avec:

integer_value_('integer':Sign:[H],E) :- 
    H in 0..9, 
    (
     Sign = 'positive', 
     E #= H 
     ; 
     Sign = 'negative', 
     E #= -H 
    ). 
integer_value_('integer':Sign:[H,I|T],E) :- 
    H in 0..9, 
    length([I|T],L), 
    (
     Sign = 'positive', 
     E #= F + H * 10^L 
     ; 
     Sign = 'negative', 
     E #= F - H * 10^L 
    ), 
    integer_value_('integer':Sign:[I|T],F). 

Cela fonctionne comme prévu. Cependant, il a la malheureuse propriété d'accepter des choses comme integer:positive:[0,1], c'est-à-dire des zéros au début de la liste. Ceci est particulièrement problématique lorsque j'énumère tous les entiers possibles en utilisant integer_value_(I,J), label([J]).: ceux avec des zéros en tête apparaissent également.

Je puis tenté de corriger cela en utilisant integer_value_ seulement pour tous, mais le premier chiffre, et en utilisant integer_value pour le premier (en gardant à l'esprit que nous devons accueillir pour 0 étant représenté par une liste contenant seulement 0):

integer_value('integer':Sign:[H],E) :- 
    abs(E) #< 10, 
    abs(E) #> -1, 
    integer_value_('integer':Sign:[H],E). 
integer_value('integer':Sign:[H,I|T],E) :- 
    H in 1..9, 
    length([I|T],L), 
    (
     Sign = 'positive', 
     E #= F + H * 10^L 
     ; 
     Sign = 'negative', 
     E #= F - H * 10^L 
    ), 
    integer_value_('integer':Sign:[I|T],F). 

Cependant, maintenant, il ne se comporte pas correctement. Par exemple, integer_value(I,-19). renvoie I = integer:negative:[1, 9], mais si nous demandons une autre réponse, Prolog entre dans une boucle infinie pour des raisons que je ne comprends pas (cela devrait être faux, ou je sais déjà qu'il n'y a pas d'autres réponses).

Ce problème ne se produit pas avec la requête "adverse" integer_value(integer:negative:[1,9],Z). qui renvoie Z = 19 puis false, et cela ne se produit pas non plus lorsque les deux arguments sont des variables (il énumère les nombres correctement, sans zéros), ce qui me surprend.

Une idée de ce que cette boucle infinie se produit, et s'il existe un moyen facile de le réparer?

Answer 1

Pour voir le problème, il suffit de regarder une infime fraction de votre programme. En fait, le failure-slice est suffisante suivant:

 
integer_value('integer':Sign:[H],E) :- false, 
    abs(E) #< 10, 
    abs(E) #> -1, 
    integer_value_('integer':Sign:[H],E). 
integer_value('integer':Sign:[H,I|T],E) :- 
    H in 1..9, 
    length([I|T],L), false, 
    ( Sign = 'positive', 
     E #= F + H * 10^L 
     ; 
     Sign = 'negative', 
     E #= F - H * 10^L 
    ), 
    integer_value_('integer':Sign:[I|T],F). 

L se produit ici pour la première fois, de sorte que toute la longueur est possible. Vous devrez modifier l'objectif de longueur en quelque sorte.

Answer 2

j'ai réussi à résoudre mon problème en utilisant this other answer a souligné par @false

Une des prises est de décider du signe du nombre que la dernière étape, de sorte que lorsque itérer entiers possibles nous obtenons des réponses en alternance entre les nombres positifs et négatifs: après avoir atteint 9 (1 chiffre), il s'unifie avec -9, puis -8, etc. Après -1, il s'unifie avec 10, 11, etc. Après 99, il s'unifie avec -99 , -98, etc. Vous obtenez le point.

integer_value('integer':Sign:I,E) :- 
    integer_value('integer':Sign:I,0,E,E). 

integer_value('integer':Sign:[H],N0,N,M) :- 
    H in 0..9, 
    N1 #= H + N0 * 10, 
    abs(M) #>= abs(N1), 
    integer_value_('integer':Sign:[],N1,N,M). 
integer_value('integer':Sign:[H,I|T],N0,N,M) :- 
    H in 1..9, 
    N1 #= H + N0 * 10, 
    abs(M) #>= abs(N1), 
    integer_value_('integer':Sign:[I|T],N1,N,M). 

integer_value_('integer':Sign:[],N0,N,_) :- 
    (
     Sign = 'positive', 
     N #= N0 
     ; 
     Sign = 'negative', 
     N #\= 0, 
     N #= - N0 
    ). 
integer_value_('integer':Sign:[H],N0,N,M) :- 
    H in 0..9, 
    N1 #= H + N0 * 10, 
    abs(M) #>= abs(N1), 
    integer_value_('integer':Sign:[],N1,N,M). 
integer_value_('integer':Sign:[H,I|T],N0,N,M) :- 
    H in 0..9, 
    N1 #= H + N0 * 10, 
    abs(M) #>= abs(N1), 
    integer_value_('integer':Sign:[I|T],N1,N,M).