在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)？

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

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 = lll -htmlse25

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指针是NULL或另一个列表结构.

那么,从那以后,我们得到了反向/ 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中常见的习语是使用带有累加器的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)时间内运行的实现.它也是尾递归的,这意味着它可以处理任何长度的列表而不会吹掉它的堆栈.