0

我正在尝试编写一个 Prolog 递归，它将返回以下数字表示：

1 --> s(0)

2 --> s(s(0))

3 --> s(s(s(0))) ...

我使用了以下代码：

retnum(s(0),1). %Stop Condition
retnum(S,Z):-
    retnum(s(S),Z1),
    Z is Z1+1.

但是当我尝试运行预测时：

retnum(A,2).

我得到结果 A=0，如果我继续，我会收到超过卡住限制的错误。我期待得到一个结果 A = s(s(0))。我还尝试添加额外的停止条件：retnum(0,0)。

知道我的错误在哪里以及是否有更好的方法吗？

4

2 回答 2

2

您错误地使用了递归调用。递归实例的参数应该小于原始参数（更一般地说：收敛到边界条件）。这可能会给你你想要的：

retnum(s(0), 1).
retnum(s(S), Z) :-
    retnum(S, Z1),
    Z is Z1 + 1.

但这更好。

retnum1(s(0), 1).
retnum1(s(S), Z) :-
    Z > 1, Z1 is Z - 1,
    retnum1(S, Z1).

试着trace/0看看为什么会这样。

于 2021-07-13T12:51:58.267 回答
2

正如@false 所推荐的，最好的方法是使用library(clpfd). 但是，如果您不想使用该库，则可能的解决方案是考虑两种不同的情况：

  • 确定性情况[要转换为Peano形式的自然N是一个常数]：从N开始，递归递减该值，直到达到值0（可以生成唯一解）。

  • 非确定性情况[要转换为Peano形式的自然N是一个变量]：从0开始，递归递增该值，每一步产生一个新的自然N（可以生成无限多个解）。

% nat(?Natural, ?Peano)

  nat(N, P) :-
     (  integer(N) -> nat_det(N, P)
     ;  var(N)     -> nat_nondet(N, P)).

  nat_det(0, 0) :- !.
  nat_det(N, s(P)) :-
     succ(M, N),
     nat_det(M, P).

  nat_nondet(0, 0).
  nat_nondet(N, s(P)) :-
     nat_nondet(M, P),
     succ(M, N).

这里有些例子：

?- nat(2, P).
P = s(s(0)).

?- nat(2, s(s(0))).
true.

?- nat(2, s(s(s(0)))).
false.

?- nat(N, s(s(s(0)))).
N = 3.

?- N = 4, nat(N, P).
N = 4,
P = s(s(s(s(0)))).

?- nat(N, P), N = 4, !. % we know that there exist only one solution!
N = 4,
P = s(s(s(s(0)))).

?- nat(N, P).
N = P, P = 0 ;
N = 1,
P = s(0) ;
N = 2,
P = s(s(0)) ;
N = 3,
P = s(s(s(0))) ;
...
于 2021-07-14T16:46:21.197 回答