在Prolog中展开一个列表

Question

我只接触 Prolog 几天时间。虽然有些东西我已经理解了，但这个问题真的让我感到困惑。

我需要编写一个函数，接收一个列表并将其展平。

?- flatten([a,[b,c],[[d],[],[e]]],Xs).  
Xs = [a,b,c,d,e].                           % expected result

这个函数将提取列表的内部结构。

目前我已经有了以下代码：

flatten2([],[]).
flatten2([Atom|ListTail],[Atom|RetList]) :-
      atom(Atom), flatten2(ListTail,RetList).
flatten2([List|ListTail],RetList) :-
      flatten2(List,RetList).

现在，当我调用以下代码时，它可以正常工作：

?- flatten2([a,[b,c],[[d],[],[e]]], R).
R = [a,b,c,d,e].                         % works as expected!

但是当我调用查看输入的列表是否已经被展平时，它返回false而不是true：

?- flatten2([a,[b,c],[[d],[],[e]]], [a,b,c,d,e]).
false.                                   % BAD result!

为什么在一只手上可以工作，而在另一只手上却不能？我感觉自己忽略了某些非常简单的东西。

- ToastyMallows

---

请在考虑特定任务的同时，也考虑一个更一般的情况：?- flatten([X], Ls). 应该产生什么结果？你可能认为它“显然”应该产生 Ls = [X]。然而，你会遇到以下问题：?- flatten([X], Ls), Ls = [X], X = [a]. 成功，但是如果我们通过连词的交换性来简单地交换目标，我们得到：?- Ls = [X], X = [a], flatten([X], Ls).，或者更简洁地说，?- flatten([[a]], [[a]]).，这当然必须失败，因为[[a]]不是一个平坦的列表。那么，它是成功还是失败呢？这表明这真的不是一个好的关系。 - mat

这就是为什么我建议您看一下append/2。它将此关系限制为更有意义且通常也更实用的版本。 - mat

Answer 1

你提供的 flatten2/2 的定义是错误的；它实际上的行为是这样的：

?- flatten2([a, [b,c], [[d],[],[e]]], R).
R = [a, b, c] ;
false. 

所以，假设您已经将R绑定到[a,b,c,d,e]的情况下，失败并不令人惊讶。

您的定义在第3个子句中丢弃了列表的尾部（ListTail）- 这需要整理并连接回列表，通过RetList返回。这是一个建议：

flatten2([], []) :- !.
flatten2([L|Ls], FlatL) :-
    !,
    flatten2(L, NewL),
    flatten2(Ls, NewLs),
    append(NewL, NewLs, FlatL).
flatten2(L, [L]).

这个函数会将所有的列表递归减少到包含单个元素 [x] 或者空列表 []，然后将它们累积并重新附加到输出的一个新列表中。

需要注意的是，在大多数 Prolog 实现中，空列表 [] 既是原子 又是 列表，所以对 atom([]) 和 is_list([]) 的调用都会返回真；这并不能帮助你抛弃空列表而不是字符原子。

- user206428

---

你说得对，它是有问题的。我不知道为什么之前能得到正确的答案。我理解你的方法是如何工作的，但它是如何去除空列表的呢？此外，为什么 [] 是原子？ - ToastyMallows

@ToastyMallows，它会去掉[]，因为将列表和[]附加在一起会得到相同的列表。由于历史原因，[]既是原子也是列表。查找“cons”和“nil”。[]在LISP中被称为“nil”。 - Will Ness

我是Prolog的新手，感到困惑：!代表什么意思？我的解决方案与别人一样，但如果没有!就无法正常工作。 - FranXh

在Prolog中，“!”是一个特殊字符，被称为“剪切”。它告诉解释器要剪切（忽略）其他选择以防止回溯。有关更多信息，请参阅Learn Prolog Now！上的详细教程。 - user206428

Answer 2

你可以保持列表的开放性，既有指向其开头的指针，也有一个“结尾孔/自由指针”（即logvar）在其末尾，当到达末尾时，可以实例化它。

flatten2( [], Z, Z):- !.                                        % ---> X
flatten2( [Atom|ListTail], [Atom|X], Z) :-                      %      .
    \+is_list(Atom), !,                                         %      .
    flatten2( ListTail, X, Z).                                  %      Y
flatten2( [List|ListTail], X, Z) :-                             %      .
    flatten2( List,     X, Y),       % from X to Y, and then    %      .
    flatten2( ListTail, Y, Z).       % from Y to Z              %      Z --->

然后你调用它

flatten2( A, B):- flatten2( A, B, []).

这样就不需要在任何地方使用reverse。这种技术被称为“差异列表”，但更容易将其视为“开放列表”。

---

更新: 使用dcg语法编码要容易得多。由于它是单向的（第一个参数必须完全确定），为什么不在最后使用剪切呢：

flattn([]) --> [], !.
flattn([A|T]) --> {\+is_list(A)}, [A], !, flattn(T).
flattn([A|T]) --> flattn(A), flattn(T).

测试：

16 ?- phrase(flattn([a,[b,c],[[d],[],[e]]]), [a, b, c, d, e]).
true.

17 ?- phrase(flattn([a,[b,c],[[d],[],[e]]]), R).
R = [a, b, c, d, e].

18 ?- phrase(flattn([a,[b,c],[[d],[],[e]]]), R, [1,2,3]).
R = [a, b, c, d, e, 1, 2, 3].

19 ?- phrase(flattn([a,[b,X],[[d],[],[e]]]), [a, b, c, d, e]).
X = c.

如果定义是完全声明性的，那么最后一个例子应该也会成功，如X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ...，但很遗憾它并不是。

- Will Ness

---

从技术上讲，我最喜欢你的解决方案，但它在SWI-Prolog 6中对我不起作用。 - FK82

我尝试运行 flatten2([1,[8,3],[3,[5,6],2],8], X)，但它返回了 false。 - FK82

@FK82 你说得对，我应该使用atomic/1而不是atom/1。-- 已经修复了，谢谢！ - Will Ness

!//0 是一个DCG非终端符号，不需要进行包装。例如，您可以编写 flattn([]) --> !. 但是，您必须使用 phrase/2 来访问DCG！实现可以自由选择任何扩展方法，并且确实不需要将DCG扩展为显式差异。例如，在某些抽象机中，使用不同的参数顺序可能更加高效。如果您依赖于特定的扩展方法，那么在未来的系统中实现这样的优化将变得越来越困难。 - mat

我点赞了这个帖子，因为DCG版本是整个讨论串中我认为我有机会理解的第一个谓词版本；-）不过你仍然可以简化它！ - mat

Answer 3

为了完整性，这里提供一个基于累加器的版本:

% flatten/2
flatten(List, Result) :- flatten(List, [], Result).

% auxiliary predicate flatten/3
flatten([], Result, Result).
flatten([Head| Tail], Part, Result) :- 
    is_list(Head),
    !, 
    flatten(Head, HR),
    append(Part, HR, PR),
    flatten(Tail, PR, Result).
flatten([Head| Tail], Part, Result) :- 
    append(Part, [Head], PR),
    flatten(Tail, PR, Result).
flatten(X, Part, Result) :-
    fail.

- FK82

---

通常情况下，我们会尽量避免使用 append，除非它是 O(1) 的，比如使用差分列表 app(A-B,B-C,A-C)。 - Will Ness

@WillNess 好的，我是Prolog的新手。 :-) 我试图避免使用append，但仅使用列表无法使它正常工作。 - FK82

干得好。 :) （你没有像往常一样做flatten，flatten，append - 你尝试至少进行一个递归调用作为尾调用；不错）。--顺便说一句，一个总是fail的子句可以完全安全地被删除 - 无论它是否匹配子句的头并立即失败，或者只是因为没有（更多）匹配而失败，都无所谓：失败就是失败。 - Will Ness

@WillNess 谢谢，已经注意到了！ :) - FK82

Answer 4

Prolog的列表表示法是在非常简单的Prolog术语上添加的“语法糖”。Prolog列表如下所示：

1. 空列表由原子[]表示。为什么？因为它看起来像空列表的数学表示法。他们本可以使用像nil这样的原子来表示空列表，但他们没有。

2. 非空列表由术语.\2表示，其中第一个（最左边的）参数是列表的头，第二个（最右边的）参数是列表的尾巴，递归地说，它本身是一个列表。

一些例子：

• An empty list: [] is represented as the atom it is:

  []
  

• A list of one element, [a] is internally stored as

  .(a,[])
  

• A list of two elements [a,b] is internally stored as

  .(a,.(b,[]))
  

• A list of three elements, [a,b,c] is internally stored as

  .(a,.(b,.(c,[])))
  

对列表头部的检查也是同样的语法糖，使用相同的符号:

• [X|Xs] 与 .(X,Xs) 相同

• [A,B|Xs] 与 .(A,.(B,Xs)) 相同

• [A,B] (参见上文) 与 .(A,.(B,[])) 相同

我自己会这样编写flatten/2:

%------------------------
% public : flatten a list
%------------------------
flatten( X , R ) :-
  flatten( X , [] , T ) ,
  reverse( T , R )
  .

%--------------------------------------------
% private : flatten a list into reverse order
%--------------------------------------------
flatten( [] , R , R ) .        % the empty list signals the end of recursion
flatten( [X|Xs] , T , R ) :-   % anything else is flattened by
  flatten_head( X , T , T1 ) , % - flattening the head, and
  flatten( Xs , T1 , R )       % - flattening the tail
  .                            %

%-------------------------------------
% private : flatten the head of a list
%-------------------------------------
flatten_head( X , T , [X|T] ) :- % if the head is a not a list
  \+ list(X) ,                   % - simply prepend it to the accumulator.
  ! .                            %
flatten_head( X , T , R     ) :- % if the head is a list
  flatten( X , T , R )           % - recurse down and flatten it.
  .

%-----------------------
% what's a list, anyway?
%-----------------------
list( X ) :- var(X) , ! , fail .
list( []    ) .
list( [_|_] ) .

- Nicholas Carey

---

我使用你的代码尝试了 flatten([a,[b,c],[],[[[d]]]],X) 调用，但它没有起作用。在你的版本中好像缺少了处理原子的情况。 - Will Ness

但现在它生成了X = [a，[c，b]，[[[d]]]]。 - Will Ness

list(X)的意思是什么：:- var(X)，！，fail。 - bph

list(X) :-var(X) , ! , fail. 的意思是，如果 X 是一个未绑定的变量，则 X 不是列表。!, fail. 部分消除了选择点（因此它不能跟随谓词的其他可选路径）并失败。有了这个保护条款，未绑定的变量将与 [] 统一并成功。在回溯时，它将再次统一为 [_|_] 并再次成功。对于列表性的真/假检查应该是确定性的。 - Nicholas Carey

Answer 5

在 if_//3 和 list_truth/2 的基础上，我们可以按照以下方式实现 myflatten/2:

myflatten(Xs,Ys) :-
   phrase(myflatten_aux(Xs),Ys).

myflatten_aux([]) --> [].
myflatten_aux([T|Ts]) --> 
   if_(neither_nil_nor_cons_t(T), [T], myflatten_aux(T)),
   myflatten_aux(Ts).

:- use_module(library(dialect/sicstus/block)).

:- block neither_nil_nor_cons(-).
neither_nil_nor_cons(X) :-
   \+nil_or_cons(X).

nil_or_cons([]).
nil_or_cons([_|_]).

neither_nil_nor_cons_t(X,Truth) :-
   (  nonvar(X)
   -> (  neither_nil_nor_cons(X) -> Truth = true
      ;                             Truth = false
      )
   ;  nonvar(Truth) 
   -> (  Truth == true -> neither_nil_nor_cons(X)
      ;  Truth == false,  nil_or_cons(X)
      )
   ;  Truth = true,  neither_nil_nor_cons(X)
   ;  Truth = false, nil_or_cons(X)
   ).

示例查询（摘自其他答案和答案评论）：

?- myflatten([[4],[[5,6],[7,[8],[9,[10,11]]]]], Xs).
Xs = [4, 5, 6, 7, 8, 9, 10, 11].

?- myflatten([1,[8,3],[3,[5,6],2],8], Xs).
Xs = [1, 8, 3, 3, 5, 6, 2, 8].

?- myflatten([a,[b,c],[],[[[d]]]], Xs).
Xs = [a, b, c, d].

?- myflatten([a,[b,c],[[d],[],[e]]], Xs).
Xs = [a, b, c, d, e].

neither_nil_nor_cons_t和not(nil_or_cons_t)描述具有相同解决方案，但解决方案的顺序不同。请考虑：

?- myflatten([A,B,C],Xs), A=a,B=b,C=c.
A = a,
B = b,
C = c,
Xs = [a, b, c] ;                       % does not terminate universally

- repeat

Answer 6

仅使用尾递归，没有其他谓词。

flatten([[X|S]|T], F) :- flatten([X|[S|T]], F).
flatten([[]|S], F) :- flatten(S, F).
flatten([X|S], [X|T]) :- \+(X = []), \+(X = [_|_]), flatten(S, T).
flatten([], []).

- Loic

---

?- flatten(Ls0, Ls). 会导致 本地栈溢出。 - mat

第一个参数中不允许使用变量。否则，如果存在正确的解决方案，则我相信它已经被计算出来了。 - Loic

Answer 7

我没有使用findall找到解决方案，所以我会添加它。（如果列表是完全确定的，包括所有元素都是完全确定的，那么它将起作用）

首先，我们定义如何测试列表：

list(X) :- var(X), !, fail.
list([]).
list([_|_]).

通过传递闭包和member的交集，我们称之为member*：

'member*'(X, Y) :- member(X, Y).
'member*'(X, Y) :- member(Z, Y), 'member*'(X, Z).

扁平化列表是所有 member* 的解决方案，这些方案不是列表：

flatten(X, Y) :- findall(Z, ('member*'(Z, X), \+ list(Z)), Y).

例子：

?- flatten([[4],[[5,6],[7,[8],[9,[10,11]]]]],Y).
Y = [4, 5, 6, 7, 8, 9, 10, 11].

- fferri

---

这会逐个元素地重命名变量，例如在 [[f(X),g(X)]] 中。 - false

好主意！很遗憾它不适用于上述情况，但对于完全实例化的列表有效，所以仍然很好。 :) - Will Ness