list 在 Prolog 中反转列表

Question

提问by Jared

I have finished a homework assignment for my programming class. I was supposed to create a Prolog program that reverses a list. I, however, am having trouble understanding why exactly it works.

我已经完成了我的编程课的家庭作业。我应该创建一个反转列表的 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

What exactly is RevT in this case? I know it is supposed to represent the reverse of T or the rest of the given list, but I don't see how it could have any value as I haven't assigned it to anything. Does it just serve the same purpose as RevList but for each recursive call?

在这种情况下，RevT 究竟是什么？我知道它应该代表 T 的反向或给定列表的其余部分，但我不知道它如何具有任何价值，因为我没有将它分配给任何东西。它是否与 RevList 具有相同的目的，但对于每个递归调用？

Also, why do I have to use [H] instead of just H in my conc() function call? Doesn't H refer to the head of the list (ex: [H])? Or does it just refer to the item at the head of the list (just H)?

另外，为什么我必须在 conc() 函数调用中使用 [H] 而不是 H ？H 不是指列表的头部吗（例如：[H]）？或者它只是引用列表头部的项目（只是 H）？

Please help clear this up for me. I am struggling to understand the logic behind this type of programming.

请帮我解决这个问题。我正在努力理解这种编程背后的逻辑。

Answer 1

回答by Cornel Marian

Your solution explained: If we reverse the empty list, we obtain the empty list. If we reverse the list [H|T] , we end up with the list obtained by reversing T and concatenating with [H] . To see that the recursive clause is correct, consider the list [a,b,c,d] . If we reverse the tail of this list we obtain [d,c,b] . Concatenating this with [a] yields [d,c,b,a] , which is the reverse of [a,b,c,d]

您的解决方案解释了：如果我们反转空列表，我们将获得空列表。如果我们反转列表 [H|T] ，我们最终会得到通过反转 T 并与 [H] 连接获得的列表。要查看递归子句是否正确，请考虑列表 [a,b,c,d] 。如果我们反转这个列表的尾部，我们得到 [d,c,b] 。将其与 [a] 连接产生 [d,c,b,a] ，这是 [a,b,c,d] 的反向

Another reverse solution:

另一个反向解决方案：

 reverse([],Z,Z).

 reverse([H|T],Z,Acc) :- reverse(T,Z,[H|Acc]).

call:

称呼：

?- reverse([a,b,c],X,[]).

For further information please read: http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlse25

更多信息请阅读：http: //www.learnprolognow.org/lpnpage.php?pagetype=html&pageid= lpn-htmlse25

Answer 2

回答by Nicholas Carey

Prolog lists are simple data structures: ./2

Prolog 列表是简单的数据结构： ./2

The empty list is the atom [].
A list of one element, [a], is actually this structure: .(a,[]).
A list of two elements, [a,b]is actually this structure: .(a,.(b,[]))
A list of three elements, [a,b,c]is actually this structure: .(a,.(b,.(c,[])))
and so on.

空列表是 atom []。
一个元素的列表，[a]，实际上是这样的结构：.(a,[])。
一个包含两个元素的列表，[a,b]其实就是这个结构：.(a,.(b,[]))
一个包含三个元素的列表，[a,b,c]其实就是这个结构：.(a,.(b,.(c,[])))
等等。

The square bracket notation is syntactic sugarto spare you from spending your life typing parentheses. Not to mention that it's easier on the eyes.

方括号表示法是一种语法糖，可以让您免于花费大量时间输入括号。更不用说它对眼睛更容易。

From this, we get the notion of the headof the list (the datum in the outermost ./2structure) and the tailof the list (the sublist contained in that outermost ./2data structure.

由此，我们得到了列表头部（最外层./2结构中的数据）和列表尾部（包含在最外层./2数据结构中的子列表）的概念。

This is essentially, the same data structure you see for a classic singly-linked list in C:

这本质上与您在 C 中看到的经典单向链表相同的数据结构：

struct list_node
{
  char payload ;
  struct list_node *next ;
}

where the nextpointer is either NULL or another list structure.

其中next指针为 NULL 或其他列表结构。

So, from that, we get the simple [naive] implementation of reverse/2:

因此，由此，我们得到了 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
  .                      %

This same algorithm would work for reversing a singly-linked list in a more conventional programming language.

同样的算法也适用于在更传统的编程语言中反转单链表。

However, this algorithm is not very efficient: it exhibits O(n²) behavior, for starters. It's also not tail recursive, meaning that a list of sufficient length will cause a stack overflow.

然而，这个算法不是很有效：对于初学者来说，它表现出 O(n ²) 行为。它也不是尾递归的，这意味着足够长度的列表会导致堆栈溢出。

One should note that to append an item to a prolog list requires traversing the entire list, prepending is a trivial operation, due to the structure of a prolog list. We can prepend an item to an existing list as simply as:

应该注意的是，将一项附加到序言列表需要遍历整个列表，由于序言列表的结构，前置是一项微不足道的操作。我们可以简单地将一个项目添加到现有列表中：

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

A common idiom in prolog is to use a worker predicatewith an accumulator. This makes the reverse/2implementation much more efficient and (possibly) a little easier to understand. Here, we reverse the list by seeding our accumulator as an empty list. We iterate over the source list. As we encounter item in the source list we prepend it to the reversed list, thus producing the reversed list as we go.

prolog 中的一个常见习惯用法是使用带有累加器的工作谓词。这使得实现更加高效并且（可能）更容易理解。在这里，我们通过将累加器作为空列表播种来反转列表。我们遍历源列表。当我们在源列表中遇到 item 时，我们将它添加到反向列表中，从而生成反向列表。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
  .

Now you have a reverse/2implementation that runs in O(n) time. It's also tail recursive, meaning that it can handle a list of any length without blowing its stack.

现在您有一个reverse/2在 O(n) 时间内运行的实现。它也是尾递归的，这意味着它可以处理任何长度的列表而不会破坏其堆栈。

Answer 3

回答by mat

Consider using a DCG instead, which is much easier to understand:

考虑改用 DCG，这更容易理解：

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

Example:

例子：

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

Answer 4

回答by CapelliC

What exactly is RevT in this case? I know it is supposed to represent the reverse of T or the rest of the given list, but I don't see how it could have any value as I haven't assigned it to anything. Does it just serve the same purpose as RevList but for each recursive call?

在这种情况下，RevT 究竟是什么？我知道它应该代表 T 的反向或给定列表的其余部分，但我不知道它如何具有任何价值，因为我没有将它分配给任何东西。它是否与 RevList 具有相同的目的，但对于每个递归调用？

Variables in Prolog are 'placeholders' for relations' arguments. What we know, after a successful call, it's exactly that the specified arguments hold for thatrelation.

Prolog 中的变量是关系参数的“占位符”。我们知道，在成功调用之后，正是指定的参数适用于该关系。

Then RevTwill have a value, if the call succeed. Specifically, will be the last argument of the call conc(RevT, [H], RevList), whenthe list is notempty. Otherwise, will be the empty list.

然后RevT将有一个值，如果调用成功。具体而言，将是调用的最后一个参数conc(RevT, [H], RevList)，当该列表是不是空的。否则，将是空列表。

Also, why do I have to use [H] instead of just H in my conc() function call? Doesn't H refer to the head of the list (ex: [H])? Or does it just refer to the item at the head of the list (just H)?

另外，为什么我必须在 conc() 函数调用中使用 [H] 而不是 H ？H 不是指列表的头部吗（例如：[H]）？或者它只是引用列表头部的项目（只是 H）？

Yes, H refers to the first item(usually called element) of the list, then we must 'reshape' it to be a list (of just 1 element), as required by conc/3, that is another relation among lists.

是的， H 指的是列表的第一项（通常称为element），然后我们必须将它“重塑”为一个列表（只有 1 个元素），如 conc/3 所要求的，这是列表之间的另一种关系。

Answer 5

回答by Paulo Moura

Just a note on testingreverse/2predicate definitions, too long to fit a comment.

只是一个关于测试reverse/2谓词定义的注释，太长了，不适合评论。

Reversing a list is the "hello world" example for introducing QuickCheck, which means that you can use it for helping in testing your definition. First, we define a propertythat holds for the reverse/2predicate: reversing a list twice must give the original list, which we can translate to:

反转列表是介绍 QuickCheck 的“hello world”示例，这意味着您可以使用它来帮助测试您的定义。首先，我们定义一个适用于谓词的属性reverse/2：反转列表两次必须给出原始列表，我们可以将其转换为：

same_list(List) :-
    reverse(List, Reverse),
    reverse(Reverse, ReverseReverse),
    List == ReverseReverse.

Using Logtalk's lgtunittool QuickCheck implementation:

使用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

Or simply:

或者干脆：

% either bound or unbound first argument:
| ?- lgtunit::quick_check(same_list(?list)).
% 100 random tests passed
yes

But we need another property definition to test with the second argument bound:

但是我们需要另一个属性定义来测试第二个参数绑定：

same_list_2(Reverse) :-
    reverse(List, Reverse),
    reverse(List, ListReverse),
    Reverse == ListReverse.

We can now do:

我们现在可以这样做：

% second argument bound:
| ?- lgtunit::quick_check(same_list_2(+list)).
% 100 random tests passed
yes

But note that this property-based/randomized testing do not check for the non-terminating cases as these only occur when backtracking after the first solution.

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

Answer 6

回答by Kintalken

The following is the typical implementation of reverse/2 . It does however have the problem as marked bellow with "non-termination" .

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

Answer 7

回答by Kintalken

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

'reverse/2' .

'反向/2' 。

/* The following is an implementation of reverse/2 that I just invented that does not suffer from a non-termination problem for reverse(P,[]). */

/* 以下是我刚刚发明的 reverse/2 的一个实现，它不会遇到reverse(P,[]). */

'implementation' .

'执行' 。

    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_])  .

'testing' .

'测试' 。

'testing : part 1' .

'测试：第1部分'。

    /*
    ?- reverse([],Q) .
    Q = []

    ?- reverse([a],Q) .
    Q = [a]

    ?- reverse([a,b],Q) .
    Q = [b,a]

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

'testing : part 2' .

'测试：第 2 部分'。

    /*
    ?- reverse(P,[]) .
    P = []

    ?- reverse(P,[a]) .
    P = [a]

    ?- reverse(P,[a,b]) .
    P = [b,a]

    ?- reverse(P,[a,b,c]) .
    P = [c,b,a]
    */

'testing : part 3' .

'测试：第 3 部分'。

    /*
    ?- 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] ? 
    */

list 在 Prolog 中反转列表

提问by Jared

回答by Cornel Marian

回答by Nicholas Carey

回答by mat

回答by CapelliC

回答by Paulo Moura

回答by Kintalken

回答by Kintalken

'reverse/2' .

'反向/2' 。

'implementation' .

'执行' 。

'testing' .

'测试' 。

'testing : part 1' .

'测试：第1部分'。

'testing : part 2' .

'测试：第 2 部分'。

'testing : part 3' .

'测试：第 3 部分'。

相关推荐

最近更新

标签

list 在 Prolog 中反转列表

提问by Jared

回答by Cornel Marian

回答by Nicholas Carey

回答by mat

回答by CapelliC

回答by Paulo Moura

回答by Kintalken

回答by Kintalken

'reverse/2' .

'反向/2' 。

'implementation' .

'执行' 。

'testing' .

'测试' 。

'testing : part 1' .

'测试：第1部分'。

'testing : part 2' .

'测试：第 2 部分'。

'testing : part 3' .

'测试：第 3 部分'。

相关推荐

list 两个列表的Scala差异

list 如何展平列表列表？

list 在 R 中构建嵌套列表

list 显式删除列表的元素

相关推荐

最近更新

标签