List of integers and infinite loop in Prolog CLPFD

Question

Suppose I want to represent integers: integer:Sign:[FirstDigit,SecondDigit,...] . For example, 42 would be represented as integer:positive:[4,2] .

I need a predicate that generates an integer value based on this representation and vice versa.

Here is what I came up with:

 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). 

This works as expected. However, it has an unfortunate property of accepting things like integer:positive:[0,1] , that is, leading zeros to the beginning of the list. This is especially problematic when I list all possible integers using integer_value_(I,J), label([J]). : Also, those that have leading zeros are also displayed.

Then I tried to fix this by using integer_value_ only for everyone except the first digit, and using integer_value for the first (bearing in mind that we need to place for 0 represented by a list containing only 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). 

However, now he is not behaving correctly. For example, integer_value(I,-19). returns I = integer:negative:[1, 9] , but if we ask for another answer, the Prolog goes into an endless loop for reasons that I don’t understand (it should tell a lie or already know that there are no other answers).

This problem does not occur with the "opposite" request integer_value(integer:negative:[1,9],Z). which returns Z = 19 and then false, and does not occur when both arguments are variables (it lists the numbers correctly, without leading zeros), which is surprising to me.

Any idea what an infinite loop is, and if there is an easy way to fix it?

Answer 1

To see the problem, just look at the tiny part of your program. Actually failure-slice is enough:

  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 is first encountered here, so any length is possible. You will have to somehow change the purpose of the length.

Answer 2

I managed to solve my problem using this other answer provided by @false

One catch is to determine the sign of the number as the last step, so when iterating through possible integers, we get alternating answers between a positive and a negative number: after reaching 9 (1 digit), it will combine with -9, then - 8 etc. After -1, it will be unified with 10, 11, etc. After 99, it will be unified with -99, -98, etc. You will get the 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).