27

我只用 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!

为什么一方面有效，另一方面无效？我觉得我错过了一些非常简单的东西。

4

7 回答 7

25

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([])一个列表，因此对and的调用is_list([])都评估为 true；这不会帮助您丢弃空列表而不是字符原子。

于 2012-01-30T05:39:41.833 回答
8

你可以保持你的列表是开放式的，在它的末尾有一个指向它的开始的指针和一个“结束孔/空闲指针”（即 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任何地方使用。这种技术被称为“差异列表”，但将其视为“开放式列表”要容易得多。

更新：使用语法更容易编码。既然它是单向的（第一个参数必须是完全接地的），为什么不使用 cut 呢：

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：简化了两个版本，感谢@mat的评论！）

于 2012-01-30T18:57:08.157 回答
2

这是一个基于累加器的完整版本：

% 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.
于 2014-10-10T11:06:47.000 回答
1

Prolog 的列表符号是非常简单的 prolog 术语之上的语法糖。Prolog 列表表示如下：

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

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

一些例子：

  • 一个空列表：[]表示为它的原子：

    []

  • 一个元素的列表，[a]内部存储为

    .(a,[])

  • 两个元素的列表在[a,b]内部存储为

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

  • 三个元素的列表，[a,b,c]内部存储为

    .(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( [_|_] ) .
于 2012-01-30T18:45:15.547 回答
1

基于if_//3and 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)describe 有相同的解决方案，但解决方案的顺序不同。考虑：

?- 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
于 2015-06-13T23:02:42.157 回答
1

没有任何其他谓词，只有尾递归。

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([], []).
于 2017-01-17T11:02:27.160 回答
0

我没有找到使用的解决方案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].
于 2015-06-13T15:24:30.470 回答