list 在 Prolog 中展平列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9059572/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Flatten a list in Prolog
提问by ToastyMallows
I've only been working with Prolog for a couple days. I understand some things but this is really confusing me.
我只和 Prolog 一起工作了几天。我明白一些事情，但这真的让我感到困惑。
I'm suppose to write a function that takes a list and flattens it.
我想写一个函数，它接受一个列表并将其展平。
?- flatten([a,[b,c],[[d],[],[e]]],Xs).
Xs = [a,b,c,d,e]. % expected result
The function takes out the inner structures of the list.
该函数取出列表的内部结构。
This is what I have so far:
这是我到目前为止：
flatten2([],[]).
flatten2([Atom|ListTail],[Atom|RetList]) :-
atom(Atom), flatten2(ListTail,RetList).
flatten2([List|ListTail],RetList) :-
flatten2(List,RetList).
Now, this works when I call:
现在，这在我打电话时有效：
?- flatten2([a,[b,c],[[d],[],[e]]], R).
R = [a,b,c,d,e]. % works as expected!
But when I call to see if a list that I input is already flattened, is returns falseinstead of true:
但是，当我打电话查看我输入的列表是否已经展平时，返回的是false而不是true：
?- flatten2([a,[b,c],[[d],[],[e]]], [a,b,c,d,e]).
false. % BAD result!
Why does it work on one hand, but not the other? I feel like I'm missing something very simple.
为什么一方面有效，另一方面无效？我觉得我错过了一些非常简单的东西。
采纳答案by ToastyMallows
The definition of flatten2/2you've given is busted; it actually behaves like this:
flatten2/2你给出的定义被破坏了；它实际上是这样的：
?- flatten2([a, [b,c], [[d],[],[e]]], R).
R = [a, b, c] ;
false.
So, given the case where you've already bound Rto [a,b,c,d,e], the failure isn't surprising.
因此，考虑到您已经绑定R到 的情况[a,b,c,d,e]，失败也就不足为奇了。
Your definition is throwing away the tail of lists (ListTail) in the 3rd clause - this needs to be tidied up and connected back into the list to return via RetList. Here is a suggestion:
您的定义ListTail在第三个子句中丢弃了列表 ( )的尾部- 这需要整理并连接回列表以通过RetList. 这是一个建议：
flatten2([], []) :- !.
flatten2([L|Ls], FlatL) :-
!,
flatten2(L, NewL),
flatten2(Ls, NewLs),
append(NewL, NewLs, FlatL).
flatten2(L, [L]).
This one recursively reduces all lists of lists into either single item lists [x], or empty lists []which it throws away. Then, it accumulates and appends them all into one list again out the output.
这个递归地将所有列表列表减少为单个项目列表[x]或[]它丢弃的空列表。然后，它会累积并将它们全部附加到一个列表中，再次输出。
Note that, in most Prolog implementations, the empty list []is an atom anda list, so the call to atom([])and is_list([])both evaluate to true; this won't help you throw away empty lists as opposed to character atoms.
请注意，在大多数 Prolog 实现中，空列表[]是一个原子和一个列表，因此对atom([])和的调用is_list([])都为真；这不会帮助你扔掉空列表而不是字符原子。
回答by Will Ness
You can maintain your lists open-ended, with both a pointer to its start, and an "ending hole ⁄ free pointer"(i.e. logvar) at its end, which you can then instantiate when the end is reached:
你可以保持你的列表是开放式的，有一个指向它的开始的指针，和一个“结束空洞 ⁄ 空闲指针”（即 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 --->
You then call it as
然后你把它称为
flatten2( A, B):- flatten2( A, B, []).
That way there's no need to use reverseanywhere. This technique is known as "difference lists", but it's much easier just to think about it as "open-ended lists" instead.
这样就不需要在reverse任何地方使用了。这种技术被称为“差异列表”，但将其视为“开放式列表”要容易得多。
update:This is much easier coded using the dcgsyntax. Since it is unidirectional (the first argument must be fully ground), why not use cuts after all:
更新：使用dcg语法更容易编码。既然是单向的（第一个参数必须完全接地），为什么不使用切割毕竟：
flattn([]) --> [], !.
flattn([A|T]) --> {\+is_list(A)}, [A], !, flattn(T).
flattn([A|T]) --> flattn(A), flattn(T).
Testing:
测试：
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.
If the definition were fully declarative, the last one should've succeeded also with X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ...; alas, it isn't.
如果定义是完全声明性的，那么最后一个也应该成功了X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ...; 唉，它不是。
(edit2: simplified both versions, thanks to @mat's comments!)
（edit2：简化了两个版本，感谢@ mat的评论！）
回答by FK82
Here's an accumulator based version for completeness:
这是一个基于累加器的完整版本：
% 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.
回答by Nicholas Carey
Prolog's list notation is syntactic sugaron top of very simple prolog terms. Prolog lists are denoted thus:
Prolog 的列表符号是非常简单的 prolog 术语之上的语法糖。Prolog 列表表示为：
The empty list is represented by the atom
[]. Why? Because that looks like the mathematical notation for an empty list. They could have used an atom likenilto denote the empty list but they didn't.A non-empty list is represented by the term
.\2, where the first (leftmost) argument is the headof the list and the second (rightmost) argument is the tailof the list, which is, recursively, itself a list.
空列表由 atom 表示
[]。为什么？因为这看起来像一个空列表的数学符号。他们可以使用原子nil来表示空列表，但他们没有。非空列表由术语 表示
.\2，其中第一个（最左边的）参数是列表的头部，第二个（最右边的）参数是列表的尾部，递归地，它本身就是一个列表。
Some examples:
一些例子：
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,[])))
一个空列表：
[]表示为它所在的原子：[]一个元素的列表，
[a]在内部存储为.(a,[])两个元素的列表在
[a,b]内部存储为.(a,.(b,[]))三个元素的列表，
[a,b,c]在内部存储为.(a,.(b,.(c,[])))
Examination of the head of the list is likewise syntactic sugar over the same notation:
对列表头部的检查同样是对相同符号的语法糖：
[X|Xs]is identical to.(X,Xs)[A,B|Xs]is identical to.(A,.(B,Xs))[A,B]is (see above) identical to.(A,.(B,[]))
[X|Xs]等同于.(X,Xs)[A,B|Xs]等同于.(A,.(B,Xs))[A,B]与（见上文）相同.(A,.(B,[]))
Myself, I'd write flatten/2like this:
我自己，我会这样写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( [_|_] ) .
回答by repeat
Building on if_//3and list_truth/2, we can implement myflatten/2as follows:
以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)
).
Sample queries (taken from other answers, and comments to answers):
示例查询（取自其他答案，以及对答案的评论）：
?- 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_tand not(nil_or_cons_t)describe have same solutions, but the solution order differs. Consider:
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
回答by Loic
Without any other predicate, with tail-recursion only.
没有任何其他谓词，只有尾递归。
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([], []).
回答by fferri
I didn't find a solution using findall, so I'll add it. (it will work if the list is ground)
我没有找到使用 的解决方案findall，所以我会添加它。（如果列表是地面的，它将起作用）
First, we define how to test for a list:
首先，我们定义如何测试列表：
list(X) :- var(X), !, fail.
list([]).
list([_|_]).
and the transitive closureof member, we call it member*:
和传递闭包的member，我们把它叫做member*：
'member*'(X, Y) :- member(X, Y).
'member*'(X, Y) :- member(Z, Y), 'member*'(X, Z).
The flattened list is all the solution of member*which are not lists:
扁平列表是非列表的所有解决方案member*：
flatten(X, Y) :- findall(Z, ('member*'(Z, X), \+ list(Z)), Y).
Example:
例子：
?- flatten([[4],[[5,6],[7,[8],[9,[10,11]]]]],Y).
Y = [4, 5, 6, 7, 8, 9, 10, 11].
