我已经完成了我的编程课的家庭作业。我应该创建一个反转列表的 Prolog 程序。但是，我很难理解它为什么会起作用。
%1. reverse a list
%[a,b,c]->[c,b,a]
%reverse(list, rev_List).
reverse([],[]). %reverse of empty is empty - base case
reverse([H|T], RevList):-
reverse(T, RevT), conc(RevT, [H], RevList). %concatenation
在这种情况下，RevT 到底是什么？我知道它应该代表 T 的反向或给定列表的其余部分，但我看不出它如何具有任何价值，因为我没有将它分配给任何东西。它是否与 RevList 具有相同的目的，但对于每个递归调用？
另外，为什么我必须在我的 conc() 函数调用中使用 [H] 而不是 H？H 不是指列表的头部（例如：[H]）吗？或者它只是指列表头部的项目（只是 H）？
请帮我解决这个问题。我正在努力理解这种编程背后的逻辑。
您的解决方案解释说：如果我们反转空列表，我们将获得空列表。如果我们反转列表 [H|T] ，我们最终得到通过反转 T 并与 [H] 连接获得的列表。要查看递归子句是否正确，请考虑列表 [a,b,c,d] 。如果我们反转这个列表的尾部，我们会得到 [d,c,b] 。将其与 [a] 连接会产生 [d,c,b,a] ，这是 [a,b,c,d] 的反面
另一个反向解决方案：
reverse([],Z,Z).
reverse([H|T],Z,Acc) :- reverse(T,Z,[H|Acc]).
称呼：
?- reverse([a,b,c],X,[]).
如需更多信息，请阅读：http ://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse25
Prolog 列表是简单的数据结构：./2
[]。[a]，实际上是这样的结构：.(a,[])。[a,b]其实就是这样的结构：.(a,.(b,[]))[a,b,c]其实就是这样的结构：.(a,.(b,.(c,[])))方括号符号是一种语法糖，可以让您免于花费一生的时间输入括号。更不用说它对眼睛更容易。
由此，我们得到了链表头./2（最外层结构中的数据）和链表尾（包含在最外层./2数据结构中的子链表）的概念。
这本质上与您在 C 中看到的经典单链表的数据结构相同：
struct list_node
{
char payload ;
struct list_node *next ;
}
其中next指针为 NULL 或另一个列表结构。
因此，由此，我们得到了 reverse/2 的简单 [naive] 实现：
reverse( [] , [] ) . % the empty list is already reversed.
reverse[ [X] , [X] ) . % a list of 1 item is already reversed. This special case is, strictly speaking, optional, as it will be handled by the general case.
reverse( [X|Xs] , R ) :- % The general case, a list of length >= 1 , is reversed by
reverse(Xs,T) , % - reversing its tail, and
append( T , [X] , R ) % - appending its head to the now-reversed tail
. %
同样的算法也适用于在更传统的编程语言中反转单链表。
然而，这个算法不是很有效：对于初学者来说，它表现出 O(n 2 ) 的行为。它也不是尾递归，这意味着足够长的列表会导致堆栈溢出。
应该注意的是，将一个项目附加到序言列表需要遍历整个列表，由于序言列表的结构，前置是一项微不足道的操作。我们可以将一个项目添加到现有列表中，如下所示：
prepend( X , Xs , [X|Xs] ) .
prolog 中的一个常见习惯用法是使用带有accumulator的worker 谓词。这使得实现更加高效并且（可能）更容易理解。在这里，我们通过将我们的累加器播种为空列表来反转列表。我们遍历源列表。当我们在源列表中遇到项目时，我们将其添加到反向列表中，从而生成反向列表。reverse/2
reverse(Xs,Ys) :- % to reverse a list of any length, simply invoke the
reverse_worker(Xs,[],Ys) . % worker predicate with the accumulator seeded as the empty list
reverse_worker( [] , R , R ). % if the list is empty, the accumulator contains the reversed list
reverse_worker( [X|Xs] , T , R ) :- % if the list is non-empty, we reverse the list
reverse_worker( Xs , [X|T] , R ) % by recursing down with the head of the list prepended to the accumulator
.
现在你有一个reverse/2在 O(n) 时间内运行的实现。它也是尾递归的，这意味着它可以处理任何长度的列表而不会破坏其堆栈。
考虑改用 DCG，这更容易理解：
reverse([]) --> [].
reverse([L|Ls]) --> reverse(Ls), [L].
例子：
?- phrase(reverse([a,b,c]), Ls).
Ls = [c, b, a].
在这种情况下，RevT 到底是什么？我知道它应该代表 T 的反向或给定列表的其余部分，但我看不出它如何具有任何价值，因为我没有将它分配给任何东西。它是否与 RevList 具有相同的目的，但对于每个递归调用？
Prolog 中的变量是关系参数的“占位符”。我们知道，在成功调用之后，正是指定的参数为该关系成立。
然后RevT将有一个值，如果调用成功。具体来说，将是 call 的最后一个参数conc(RevT, [H], RevList)，当列表不为空时。否则，将是空列表。
另外，为什么我必须在我的 conc() 函数调用中使用 [H] 而不是 H？H 不是指列表的头部（例如：[H]）吗？或者它只是指列表头部的项目（只是 H）？
是的，H 指的是列表的第一项（通常称为element），然后我们必须按照 conc/3 的要求将其“重塑”为一个列表（只有一个元素），这是列表之间的另一种关系。
只是关于测试 reverse/2谓词定义的注释，太长了，不适合评论。
反转列表是引入 QuickCheck 的“hello world”示例，这意味着您可以使用它来帮助测试您的定义。首先，我们为谓词定义一个属性reverse/2：将列表反转两次必须给出原始列表，我们可以将其转换为：
same_list(List) :-
reverse(List, Reverse),
reverse(Reverse, ReverseReverse),
List == ReverseReverse.
使用 Logtalk 的lgtunit工具 QuickCheck 实现：
% first argument bound:
| ?- lgtunit::quick_check(same_list(+list)).
% 100 random tests passed
yes
% both arguments unbound
| ?- lgtunit::quick_check(same_list(-list)).
% 100 random tests passed
yes
或者简单地说：
% either bound or unbound first argument:
| ?- lgtunit::quick_check(same_list(?list)).
% 100 random tests passed
yes
但是我们需要另一个属性定义来测试绑定的第二个参数：
same_list_2(Reverse) :-
reverse(List, Reverse),
reverse(List, ListReverse),
Reverse == ListReverse.
我们现在可以这样做：
% second argument bound:
| ?- lgtunit::quick_check(same_list_2(+list)).
% 100 random tests passed
yes
但请注意，这种基于属性的/随机测试不会检查非终止情况，因为这些情况仅在第一个解决方案后回溯时发生。
以下是 reverse/2 的典型实现。然而，它确实存在如下标记的问题“非终止”。
?- ['/dev/tty'] .
reverse(_source_,_target_) :-
reverse(_source_,_target_,[]) .
reverse([],_target_,_target_) .
reverse([_car_|_cdr_],_target_,_collect_) :-
reverse(_cdr_,_target_,[_car_|_collect_]) .
end_of_file.
.
?- reverse([],Q) .
Q = []
?- reverse([a],Q) .
Q = [a]
?- reverse([a,b],Q) .
Q = [b,a]
?- reverse([a,b,c],Q) .
Q = [c,b,a]
?- reverse(P,[]) .
P = [] ? ;
%% non-termination ! %%
^CAction (h for help): a
?- reverse(P,[a]) .
P = [a] ? ;
%% non-termination ! %%
^CAction (h for help): a
?- reverse(P,[a,b]) .
P = [b,a] ? ;
%% non-termination ! %%
^CAction (h for help): a
?- reverse(P,[a,b,c]) .
P = [c,b,a] ? ;
%% non-termination ! %%
^CAction (h for help): a
:- op(2'1,'fy','#') .
:- op(2'1,'fy','##') .
:- op(2'1,'fy','###') .
/* 以下是我刚刚发明的 reverse/2 的实现，它不会遇到reverse(P,[]). */
reverse(_source_,_target_) :-
reverse(_source_,_target_,_source_,_target_,[],[]) .
reverse(_source_,_target_,[],[],_target_,_source_) .
reverse(_source_,_target_,[_source_car_|_source_cdr_],[_target_car_|_target_cdr_],_source_collect_,_target_collect_) :-
reverse(_source_,_target_,_source_cdr_,_target_cdr_,[_source_car_|_source_collect_],[_target_car_|_target_collect_]) .
/*
?- reverse([],Q) .
Q = []
?- reverse([a],Q) .
Q = [a]
?- reverse([a,b],Q) .
Q = [b,a]
?- reverse([a,b,c],Q) .
Q = [c,b,a]
/*
?- reverse(P,[]) .
P = []
?- reverse(P,[a]) .
P = [a]
?- reverse(P,[a,b]) .
P = [b,a]
?- reverse(P,[a,b,c]) .
P = [c,b,a]
*/
/*
?- reverse(P,Q) .
P = Q = [] ? ;
P = Q = [_A] ? ;
P = [_A,_B],
Q = [_B,_A] ? ;
P = [_A,_B,_C],
Q = [_C,_B,_A] ? ;
P = [_A,_B,_C,_D],
Q = [_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E],
Q = [_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F],
Q = [_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G],
Q = [_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H],
Q = [_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I],
Q = [_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J],
Q = [_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K],
Q = [_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L],
Q = [_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M],
Q = [_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N],
Q = [_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O],
Q = [_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P],
Q = [_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q],
Q = [_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R],
Q = [_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S],
Q = [_S,_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T],
Q = [_T,_S,_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ? ;
P = [_A,_B,_C,_D,_E,_F,_G,_H,_I,_J,_K,_L,_M,_N,_O,_P,_Q,_R,_S,_T,_U],
Q = [_U,_T,_S,_R,_Q,_P,_O,_N,_M,_L,_K,_J,_I,_H,_G,_F,_E,_D,_C,_B,_A] ?
*/