当前位置: 动力学知识库 > 问答 > 编程问答 >

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

网友答案:

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).
分享给朋友:
您可能感兴趣的文章:
随机阅读: