问题描述:

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