在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） - 這需要整理並連接回列表中，以便通過RetList返回。這裏有一個建議：

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

這一個遞歸降低列出的所有列表進入任一單項列表[x]，或空列表[]它扔掉。然後，它將它們累積並將其全部添加到輸出中的一個列表中。

需要注意的是，在大多數Prolog的實現中，空單[]是原子和列表，以便調用atom([])和is_list([])都評價爲真;這不會幫助你拋棄空字符而不是字符原子。

Answer 2

序言的列表符號是句法糖除了非常簡單的序言術語。 Prolog的列表被因而表示爲：

1. 空列表由原子[]表示。爲什麼？因爲這看起來像是一個空列表的數學符號。他們可以使用像nil這樣的原子來表示空列表，但它們沒有。

2. 甲非空列表被術語.\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([_|_]) . 

Answer 3

您可以維護你的列表開放式的，既具有指向它的啓動和「結尾的孔⁄免費指針」（即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：簡化的兩個版本，感謝@mat的評論）

Answer 4

下面是完整的蓄電池基於版本：

% 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. 

Answer 5

我沒有找到使用findall解決方案，所以我會添加它。 （它會工作，如果該列表是地面）

首先，我們定義如何測試列表：

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

和member的transitive closure，我們稱之爲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]. 

Answer 6

大廈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 

Answer 7

沒有任何其他謂詞，只有尾遞歸。

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([], []).