在Prolog中翻转一个列表

Question

我已经完成了编程课的一项作业。 我应该创建一个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）？

请帮助我澄清这一点。我很难理解这种类型的编程逻辑。

- Jared

---

有用的链接：http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse25 和 http://www.csupomona.edu/~jrfisher/www/prolog_tutorial/2_7.html - Cornel Marian

我也开始用Prolog实现我的reverse/2 :) - CapelliC

Answer 1

您的解决方案说明： 如果我们反转空列表，我们将得到空列表。 如果我们反转列表[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

该链接提供了更多有关IT技术的信息，请查看。

- Cornel Marian

---

谢谢你的回答，它真的帮了我很多。我有一个问题：Z变量是用来做什么的？ - Tom Oakley

@TomOakley Z 是最终结果。 - Ellen Spertus

Answer 2

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指针要么为空，要么是另一个列表结构。

因此，我们可以得到简单[天真的]实现reverse/2：

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²)的行为。其次，它不是尾递归的，这意味着足够长的列表会导致堆栈溢出。

需要注意的是，要将一个项附加到Prolog列表中，需要遍历整个列表，而由于Prolog列表的结构，将一个项放在列表前面是一个微不足道的操作。我们可以简单地将一个项预置到现有列表中：

prepend( X , Xs , [X|Xs] ) .

在Prolog中常见的习惯用法是使用一个带有累加器的“工作谓词”。这使得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
  .

现在您已经有了一个运行时间为O(n)的reverse/2实现。它也是尾递归的，这意味着它可以处理任何长度的列表而不会导致栈溢出。

- Nicholas Carey

Answer 3

考虑使用DCG，它更易于理解：

reverse([])     --> [].
reverse([L|Ls]) --> reverse(Ls), [L].

例子：

?- phrase(reverse([a,b,c]), Ls).
Ls = [c, b, a].

- mat

---

什么是DCG？我不理解这个缩写。 - starbeamrainbowlabs

请查看DCG标签描述以获取更多信息，以及相关问题和答案的[tag:dcg]标签！ - mat

考虑使用 DCG，它更容易理解。——DCG 很难理解，假装不是这样也没有用。 - Kintalken

使用reverse([a,b,c],Q)可以正常工作，但是使用reverse(P,[a,b,c])会导致非终止。 - Kintalken

Answer 4

关于测试 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

但请注意，这种基于属性/随机化的测试不会检查非终止情况，因为这些情况仅在第一个解决方案后回溯时发生。

- Paulo Moura

Answer 5

在这种情况下，RevT到底是什么？我知道它应该表示T的反转或给定列表的其余部分，但我不明白它如何具有任何值，因为我并没有将其赋值给任何东西。它是否只是为每个递归调用提供与RevList相同的作用？

Prolog中的变量是关系参数的“占位符”。我们知道，在成功调用后，指定的参数恰好对于那个关系成立。

然后，如果调用成功，RevT将会有一个值。具体来说，当列表不为空时，它将是调用`conc（RevT，[H]，RevList）`的最后一个参数。否则将是空列表。

此外，为什么我必须在我的conc()函数调用中使用[H]而不是只是H呢？H是否指代列表的头（例如：[H]）？还是只是指列表头部的项目（只是H）？

是的，H指的是列表中的第一个项（通常称为元素），然后我们必须将其“重塑”为列表（仅包含1个元素），以满足conc/3的要求，这是另一种关于列表的关系。

- CapelliC

Answer 6

以下是 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

- Kintalken

Answer 7

:- op(2'1,'fy','#') .
:- op(2'1,'fy','##') .
:- op(2'1,'fy','###') .

'reverse/2' .

/* 以下是我刚刚发明的 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] ? 
    */

- Kintalken

---

哇！那真是令人难以置信的。 - user502187

@MostowskiCollapse 是的，这真是不可思议；这个看似简单的东西背后需要付出大量的努力和挫折。 - Kintalken

Answer 8

这是谓词的反向递归版本。

reverse([H|T], Res):-reverse(T, R1), append(R1, [H], Res). reverse([], []).

append([], L2, L2). append([H|T], L2, R):-append(T, L2, R1), R = [H|R1].

在SWISH上或者用一些简单的例子在纸上尝试它们。

这个谓词的正向递归版本是： reverse_fwd([H|T], Acc, R):-reverse_fwd(T, [H|Acc], R). reverse_fwd([], R, R).

代码取自这里： https://users.utcluj.ro/~cameliav/lp/4_Lists_part2.pdf https://users.utcluj.ro/~cameliav/lp/3_Lists_part1.pdf

您可以通过访问链接https://users.utcluj.ro/~cameliav/lp来检查所有文件。

- Aida

---

性能非常糟糕。例如，numlist(1, 10_000, L), time(reverse(L, R)) 执行需要1.3秒，而使用https://www.swi-prolog.org/pldoc/doc/_SWI_/library/lists.pl?show=src#reverse/2只需要0.002秒。第二个问题是你的 reverse(L, [a,b]) 超出了堆栈限制。 - brebs