在Prolog中反转列表

问题描述 投票：8回答：7

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

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

list prolog concatenation reverse head
7个回答
16
投票

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

7
投票

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（n2）行为。它也不是尾递归，这意味着足够长度的列表将导致堆栈溢出。

应该注意的是，要将一个项目附加到一个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
  .

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

2
投票

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

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

例：

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

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

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

如果通话成功，那么RevT将有一个值。具体来说，当列表不为空时，将是调用conc(RevT, [H], RevList)的最后一个参数。否则，将是空列表。

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

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

1
投票

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

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

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

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

0
投票

以下是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
-1
投票
:- 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_])  .

'测试'。

'testing : part 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' .

    /*
    ?- 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' .

    /*
    ?- 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] ? 
    */
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.