在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!

为什么一方面工作,另一方面又不工作？我觉得我错过了很简单的事情.

Answer 1

flatten2/2你给出的定义是破坏的; 它实际上表现得像这样:

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

因此,鉴于在那里你已经绑定的情况下R,以[a,b,c,d,e],失败也就不足为奇了.

你的定义是扔掉ListTail第三个子句中的lists()的尾部- 这需要整理并连接回列表以返回通过RetList.这是一个建议:

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

这一个递归地将所有列表列表减少到单个项目列表[x]或[]它丢弃的空列表.然后,它累积并将它们全部附加到输出中的一个列表中.

请注意,在大多数Prolog实现中,空列表[]是一个原子和一个列表,因此调用to atom([])并且is_list([])都评估为true; 这不会帮助你抛弃空列表而不是字符原子.

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,X],[[d],[],[e]]]), [a, b, c, d, e]).
X = c.

如果定义完全是声明性的,那么最后一个也应该成功X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ...; 唉,事实并非如此.

(EDIT2:简体两种版本,感谢@ 垫的评论!)