# successor arithmetics - Prolog counting using s(0) and p(0)

I am having some issues with a part of my revision for my prolog exam.

I need to create a recursive statement that will be called simplify/2. An example use would be

``simplify(s(p(s(0))),Z)``

which would result in `Z` being s(0). S stands for successor and P predecessor.

So:

`s(0)` is 1,

`s(s(0))` is 2 and `p(0)` is -1 etc.

and

`p(s(p(p(0))))` would be `p(p(0))`.

The code I initially had was

``check(s(0),s(0)).check(s(X),s(0)) :- check(X,s(s(0))).check(p(X),s(0)) :- check(X,0).``

But this clearly doesn't work as the second part needs to be kept as a variable that is added on to itself during the recursive call. I'll have another look at it in around 30 minutes because my head is fried at the moment.

``````z(0).
z(s(X)) :-
z(X).
z(p(X)) :-
z(X).

z_canonized(Z, C) :-
z_canonized(Z, 0, C).

z_canonized(0, C,C).
z_canonized(s(N), C0,C) :-
z_succ(C0,C1),
z_canonized(N, C1,C).
z_canonized(p(N), C0,C) :-
z_pred(C0,C1),
z_canonized(N, C1,C).

z_succ(0,s(0)).
z_succ(s(X),s(s(X))). % was: z_succ(X,s(X)) :- ( X = 0 ; X = s(_) ).
z_succ(p(X),X).

z_pred(0,p(0)).
z_pred(p(X),p(p(X))).
z_pred(s(X),X).
``````

My attempt:

``````simplify(X, Z) :-
simplify(X, 0, Z).
simplify(0, Z, Z).
simplify(s(X), 0, Z) :- simplify(X, s(0), Z).
simplify(p(X), 0, Z) :- simplify(X, p(0), Z).
simplify(p(X), s(Y), Z) :- simplify(X, Y, Z).
simplify(s(X), p(Y), Z) :- simplify(X, Y, Z).
simplify(s(X), s(Y), Z) :- simplify(X, s(s(Y)), Z).
simplify(p(X), p(Y), Z) :- simplify(X, p(p(Y)), Z).
``````

Update - shorter version:

``````simplify(X, Z) :-
simplify(X, 0, Z).
simplify(0, Z, Z).
simplify(p(X), s(Y), Z) :- simplify(X, Y, Z).
simplify(s(X), p(Y), Z) :- simplify(X, Y, Z).
simplify(s(X), Y, Z) :- Y \= p(_), simplify(X, s(Y), Z).
simplify(p(X), Y, Z) :- Y \= s(_), simplify(X, p(Y), Z).
``````

Some tests:

``````?- simplify(s(p(s(0))), Z).
Z = s(0)

?- simplify(p(s(p(p(0)))), Z).
Z = p(p(0))

?- simplify(p(p(s(s(0)))), Z).
Z = 0
``````

Yet another answer, coded for fun of it. It first simplifies an expression into an integer and then converts the result into `p(...)` for negative integers, `s(...)` for positive integers (excluding zero), and `0` for `0`. The standard `sign/1` arithmetic function is used to take advantage of first-argument indexing.

``````simplify(Expression, Result) :-
simplify(Expression, 0, Result0),
Sign is sign(Result0),
convert(Sign, Result0, Result).

simplify(0, Result, Result).
simplify(s(X), Result0, Result) :-
Result1 is Result0 + 1,
simplify(X, Result1, Result).
simplify(p(X), Result0, Result) :-
Result1 is Result0 - 1,
simplify(X, Result1, Result).

convert(-1, N, p(Result)) :-
N2 is N + 1,
Sign is sign(N2),
convert(Sign, N2, Result).
convert(0, _, 0).
convert(1, N, s(Result)) :-
N2 is N - 1,
Sign is sign(N2),
convert(Sign, N2, Result).
``````

OK, another "fun" solution. This one works in ECliPSe and uses non-standard `append_strings`, which is a strings' analog of lists' `append`:

``````simplify(X, Z) :-
term_string(X, Xstr),
( append_strings(Middle, End, Xstr),
(
append_strings(Begin, "s(p(", Middle)
;
append_strings(Begin, "p(s(", Middle)
) ->
append_strings(NewEnd, "))", End),
append_strings(Begin, NewEnd, Zstr),
term_string(Ztemp, Zstr),
simplify(Ztemp, Z)
;
Z = X
).
``````

This is my answer:

``````simplify(X, Z) :- simplify(X, 0, 0, Z).
simplify(0, 0, X, X).
simplify(0, X, 0, X) :- X \= 0.
simplify(0, p(X), s(Y), Z) :- simplify(0, X, Y, Z).
simplify(p(X), P, S, Z) :- simplify(X, p(P), S, Z).
simplify(s(X), P, S, Z) :- simplify(X, P, s(S), Z).
``````

I'm dividing input structure into two chains of `p`s and `s`s and then I am removing one by one from both chains. When one of them ends, the other one becomes the result of operation. I think it is quite efficient.

I was inspired by Paulo's submission to do a variant of the "Count the p's and s's" approach:

``````simplify(Exp, Simp) :-
exp_count(Exp, Count),
exp_count(Simp, Count).

exp_count(Exp, C) :-
exp_count(Exp, 0, C).

exp_count(s(X), A, C) :-
(   nonvar(C)
->  A < C
;   true
),
A1 is A + 1,
exp_count(X, A1, C).
exp_count(p(X), A, C) :-
(   nonvar(C)
->  A > C
;   true
),
A1 is A - 1,
exp_count(X, A1, C).
exp_count(0, C, C).
``````