在Prolog中展开列表
我只在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!
但是当我打电话来查看我input的列表是否已经变平时，返回false而不是true ：
?- flatten2([a,[b,c],[[d],[],[e]]], [a,b,c,d,e]). false. % BAD result!
它为什么一方面工作，而另一方面呢？ 我觉得我错过了很简单的事情。
你给的flatten2/2的定义是破产的; 它的行为实际上是这样的：
?- flatten2([a, [b,c], [[d],[],[e]]], R). R = [a, b, c] ; false.
所以，鉴于你已经将R绑定到[a,b,c,d,e] ，失败并不令人惊讶。
你的定义是抛弃列表（ ListTail ）的尾部在第三个子句 – 这需要整理和连接回列表通过RetList返回。 这是一个build议：
flatten2([], []) :- !. flatten2([L|Ls], FlatL) :- !, flatten2(L, NewL), flatten2(Ls, NewLs), append(NewL, NewLs, FlatL). flatten2(L, [L]).
这个recursion地将所有列表的列表减less到单个项目列表[x]或空列表[] ，它扔掉了。 然后，将它们累积并将其全部附加到输出中的一个列表中。
请注意，在大多数Prolog实现中，空列表[]是一个primefaces和一个列表，所以对atom([])和is_list([])的调用都计算为true; 这不会帮助你抛弃空字符而不是字符primefaces。
你可以保持你的列表是开放式的，既有指向它开始的指针，也有末尾有一个“结束空洞/空闲指针” （即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).
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.
如果定义是完全声明的，最后一个也应该用X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ... X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ... X=[c] ; X=[[],c] ; ... ; X=[[c]] ; ... ; 唉，事实并非如此。
（编辑2：简化了两个版本，感谢@ mat的评论！）
Prolog的列表符号是非常简单的序言术语上的语法糖 。 序言列表如下所示：
-
空列表由atom
[]。 为什么？ 因为这看起来像一个空列表的math符号。 他们可以用一个像nil的primefaces来表示空的列表，但他们没有。 -
非空列表由术语
.\2，其中第一个（最左边的）参数是列表的头部 ，第二个（最右边的）参数是列表的尾部 ，recursion地，它本身就是一个列表。
一些例子：
-
一个空的列表：
[]被表示为primefaces：[] -
一个元素的列表
[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,[]))
我自己，我会这样写：
%------------------------ % 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( [_|_] ) .
基于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)描述了相同的解决scheme，但解决scheme顺序不同。 考虑：
?- 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
这里是一个基于累加器的版本来完整：
% 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.
我没有find使用findall的解决scheme，所以我会添加它。 （如果名单是基础的话，这将起作用）
首先，我们定义如何testing一个列表：
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*所有解决scheme，不是列表：
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].
没有任何其他的谓词，只有尾recursion。
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([], []).
