Re: Prolog Programming for AI, problem 7.1

Lash Rambo <lr@xxxxxxxxxxxx> writes:


So, is there a simple, clever solution to this problem in Prolog? I'm
thinking a dozen lines, max. No CFGs, no term decomposition (beyond
stuff like X+Y), no wacky 3rd party libraries, etc.

Consider how you'd go about it if summation expressions had a slightly
different form:

n(N) ... for number N
s(S) ... for symbol S
A + B ... for sum of two terms

That is, distinct functors are used to distinguish distinct classes of
things. You might as well rewrite such terms into lists:

sum_to_list(n(N), [n(N)|Rest], Rest).
sum_to_list(s(N), [s(N)|Rest], Rest).
sum_to_list(A+B, List0, Rest) :-
sum_to_list(A, List0, List1),
sum_to_list(B, List1, Rest).


Together with three auxiliary predicates

un_n(n(N), N).
is_n(n(_)).
is_s(s(_)).

you can then separate symbols from numbers easily and sum the numbers:

simplify(Sum0, Sum) :-
sum_to_list(Sum0, List0, []),
sublist(is_s, List0, Symbols),
sublist(is_n, List0, Numbers0),
maplist(un_n, Numbers0, Numbers),
sumlist(Numbers, S),
append(Symbols, [n(S)], Sum).



?- simplify(n(1) + n(1) + s(a), E).

E = [s(a), n(2)] ;

?- simplify(n(1) + s(a) + n(4) + n(2) + s(b) + s(c), E).

E = [s(a), s(b), s(c), n(7)] ;

?- simplify(n(3) + s(x) + s(x), E).

E = [s(x), s(x), n(3)] ;

You would then add additional code to symbolically sum the symbols
and, if necessary, remove the distinguishing functors and convert the
list into the original form.

.