CODEWITHSUNDEEP
prologsuccessor-arithmetics
user1235720
user1235720

Reputation:

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.

Upvotes: 2

Views: 598

Answers (6)

lurker
lurker

Reputation: 58244

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

Upvotes: 0

Grzegorz Adam Kowalski
Grzegorz Adam Kowalski

Reputation: 5565

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 ps and ss 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.

Upvotes: 1

Sergii Dymchenko
Sergii Dymchenko

Reputation: 7209

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

Upvotes: 2

Paulo Moura
Paulo Moura

Reputation: 18663

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

Upvotes: 2

false
false

Reputation: 10102

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

Upvotes: 2

Sergii Dymchenko
Sergii Dymchenko

Reputation: 7209

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

Upvotes: 2

Related Questions