在 Prolog 中创建尾递归下降函数

Question

我正在尝试在prolog中创建一个尾递归drop/3。尾递归教给我们的方式(很糟糕)甚至没有开始告诉我我需要如何解决这个问题。

这是我唯一拥有的东西，据我所知，它甚至不是尾递归的。我正处于精神绳索的尽头，所以任何帮助将不胜感激。

drop(N, [], []).
drop(N, [A,As], Bs) :-
integer(N), 
N > 0,
N1 is N - 1,
Bs is As,
drop(N1, As, Bs).

Answer 1

你的问题是：

• [A,As]是一个 2 元素列表(例如，[ alpha, bravo ])，而不是将列表分解为它的头和尾。[ H | T ]当应用于列表时[a,b,c]收益Ha，T[b,c]。
• is/2会算术，所以Bs is As不起作用。如果是这样，你正在与结果统一：一个Prolog变量，一旦统一就不再是变量，因此不能重新分配。

因此，假设您要实现此drop/3，请尝试以下操作：

drop( _ , []    , [] ) .  % allows `drop(3, [a,b], R)` to succeed
drop( 0 , R     , R  ) .  % dropping the first 0 element from a list returns the same list
drop( N , [_|T] , R  ) :- % otherwise . . .
integer(N) ,            % - given that N is an integer, and
N > 0 ,                 % - given that N is positive, then
N1 is N-1 ,             % - we decrement N, and
drop( N1, T , R )       % - recurse down, discarding the head (1st element) of the list
.                       % Easy!

请注意，如果您尝试从 2 元素列表中删除 3 个元素，此操作将失败。这是一个简单的更改，可以让该案例成功。

使这种尾递归的原因是，唯一重要的状态是在递归调用之间传递的内容。这意味着堆栈帧可以重复使用。由于没有新帧被推送到调用堆栈上，这基本上将递归函数调用转换为迭代。