How to implement kind of sumator in prolog

Question

I'm trying to implement predicate which will works in mode with all variables not substituted sum(X,Y,Z) will generate all numbers which fill that conditional X+Y=Z. Well actually i can generate list of next numbers in that way.

lisst([_]).
lisst([_|Y]) :- lisst(Y).
fill([]).
fill([0|Xs]) :- fill(Xs).
fill([1|Xs]) :- fill(Xs).
fill([2|Xs]) :- fill(Xs).
fill([3|Xs]) :- fill(Xs).
fill([4|Xs]) :- fill(Xs).
fill([5|Xs]) :- fill(Xs).
fill([6|Xs]) :- fill(Xs).
fill([7|Xs]) :- fill(Xs).
fill([8|Xs]) :- fill(Xs).
fill([9|Xs]) :- fill(Xs).



concat_number(D,N) :- concat_number(D,N,0).
concat_number([],M,M).
concat_number([H|T],N,M) :- M1 is M*10+H, concat_number(T,N,M1).

    sum2(X,Y,Z) :-lisst(X),fill(X),lisst(Y),fill(Y),concat_number(X,X1), concat_number(Y,Y1), Z is X1 + Y1.

and my ask to prolog is ?- sum2(X,Y,Z). but it does not work well only Y number is changing.

I can't reproduce the error (on SWI-Prolog). Btw., the idiomatic way of enumerating finite lists is length(L,_). — Fred Foo
Undefined procedure: concat_number. Also, X is a singleton variable in that definition. — Fred Foo
Please edit your original question; comments are no good for long pieces of code. Also, please rethink your question and try to come with an SSCCE. — Fred Foo

Fred Foo Fred Foo · Accepted Answer · 2012-03-11T19:16:35

The behavior you encounter is due to Prolog's depth-first search control algorithm: because Y has an infinite number of values, Prolog never backtracks beyond the choice point for it. You should implement an iterative deepening search algorithm, like

length(XY, _),       % backtrack over lists in order of length
X=[_|_],             % constrain X and Y to be non-empty
Y=[_|_],
append(X, Y, XY),    % break XY into X and Y
fill(XY),            % fill X and Y in one go
concat_number(X,I),
concat_number(Y,J),
Z is I+J.

How to implement kind of sumator in prolog

1 Answers