2

我的序言考试的部分修订存在一些问题。

我需要创建一个递归语句，称为 simple/2。一个示例用途是 

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

这将导致Zs(0)。S代表后继者，P代表前身。所以： s(0)是 1、 s(s(0))是 2 和p(0)是 -1 等等，并且 p(s(p(p(0))))会是p(p(0))。

我最初拥有的代码是

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

但这显然不起作用，因为第二部分需要保留为在递归调用期间添加到自身的变量。大约 30 分钟后我会再看一遍，因为我现在头都炸了。

4

6 回答 6

2

好的，另一个“有趣”的解决方案。这个在ECliPSe中工作并使用 non-standard append_strings，它是字符串的“列表模拟” 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
    ).
于 2014-05-15T23:49:47.193 回答
2

另一个答案，为了好玩而编码。它首先将表达式简化为整数，然后将结果转换p(...)为负整数、正s(...)整数（不包括零）和0. 0标准sign/1算术函数用于利用第一个参数索引。

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).
于 2014-05-15T22:27:50.413 回答
2 
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).
于 2014-05-15T18:14:41.910 回答
2

我的尝试：

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

更新- 较短的版本：

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

一些测试：

?- 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
于 2014-05-15T19:37:07.747 回答
1

这是我的回答：

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

我将输入结构划分为ps 和ss 的两条链，然后从两条链中一一删除。当其中一个结束时，另一个成为操作的结果。我认为这是非常有效的。

于 2014-05-15T20:03:58.787 回答
0

我受到 Paulo 提交的启发，做了一个“计算 p 和 s”方法的变体：

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).
于 2014-05-15T23:05:10.687 回答