在 Prolog 中创建尾递归丢弃函数

Question

我正在尝试在序言中创建尾递归 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] 时会产生 H 为 a 和 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 个元素，这将失败。使该案例成功是一个简单的更改。

使这个尾部递归的原因是唯一重要的状态是递归调用之间传递的内容。这意味着栈帧可以被重用。由于没有新的框架被推送到调用堆栈，这实际上将递归函数调用转变为迭代。

在 Prolog 中创建尾递归丢弃函数

Creating a tail recursive drop function in Prolog

recursion

prolog

tail-recursion