4

我需要编写一个扁平化列表的函数。

例如：

flat([ c , [[[]]] , [] , k] , X).
X=[c,k]

这就是我所做的：

    flat([],[]).
    flat([[A] |B] , R) :- flat([A|B],R).
    flat([[]|L],L1) :- flat(L,L1).!
    flat([[A|L]|W],R) :- flat([A|L],U), flat(W,W1), append(U,W1,R).
    flat([A|L], [A|L1]) :- flat(L,L1).

我知道为什么这不是真的，但我不知道该怎么做。谢谢。

编辑： 几乎工作：

    flat([],[]).
flat([[]|L],L1) :- flat(L,L1).  --- i think something here missing
flat([[A|L]|W],R) :- flat([A|L],U), flat(W,W1), append(U,W1,R).
flat([A|L], [A|L1]) :- flat(L,L1).


?- flat([c , [[[]]] , [] , k],C).
C = [c, k] ;
C = [c, [], k] ;
C = [c, [], k] ;
C = [c, [], [], k] ;
C = [c, [[]], k] ;
C = [c, [[]], [], k] ;
C = [c, [[[]]], k] ;
C = [c, [[[]]], [], k].
4

3 回答 3

1

代码编辑（见评论）

另一种可能性，使用 DCG ：

flat(L, FL) :-
    flat(L, FL, []).

flat(X) -->
    {var(X)},
    !,
    [X].

flat([]) --> 
    [], 
    !.

flat([X | T]) -->
    flat(X),
    !,
    flat(T).

flat(X) --> [X].

现在我们得到：

 ?- flat([[a,b,c,d|r]], FL) .
FL = [a,b,c,d,r] .


 ?- flat([1,2,[3,4]],L).
L = [1,2,3,4] .

 ?- flat([1,2,[3,4]],[1,2,3,4]).
true .

 ?- flat([ c , [[[]]] , [] , k] , X).
X = [c,k] .
于 2012-06-27T12:11:22.497 回答
1 
flatten(List, FlatList) :-
    flatten(List, [], FlatList0), !,
    FlatList = FlatList0.

flatten(Var, Tl, [Var|Tl]) :-
    var(Var), !.
flatten([], Tl, Tl) :- !.
flatten([Hd|Tl], Tail, List) :- !,
    flatten(Hd, FlatHeadTail, List),
    flatten(Tl, Tail, FlatHeadTail).
flatten(NonList, Tl, [NonList|Tl]).

这是 Jan Wielemaker 和 Richard O'Keefe 的 swi-prolog 解决方案，代码可以在 prolog 的库目录中的 lists.pl 文件中找到。

于 2012-06-27T09:27:48.397 回答
0

That bang (...flat(L,L1).!...) it's a typo, isn't it?

You could study a good implementation from SWI-Prolog, that exposes its code and gives what's expected:

?- flatten([ c , [[[]]] , [] , k] , X).
X = [c, k].

Otherwise, try to debug with a simple case to see where your code, once cleaned, fails. BTW, your code seems to works, just yields more solutions, you need to prune some unwanted path:

?- flat([c , [[[]]] , [] , k],C).
C = [c, k] ;
C = [c, [], k] ;
C = [c, [], k] ;
C = [c, [], [], k] .
...

edit here is code from library(lists) of SWI-Prolog

%%  flatten(+List1, ?List2) is det.
%
%   Is true if List2 is a non-nested version of List1.
%
%   @deprecated Ending up needing flatten/3 often indicates,
%           like append/3 for appending two lists, a bad
%           design.  Efficient code that generates lists
%           from generated small lists must use difference
%           lists, often possible through grammar rules for
%           optimal readability.
%   @see append/2

flatten(List, FlatList) :-
    flatten(List, [], FlatList0), !,
    FlatList = FlatList0.

flatten(Var, Tl, [Var|Tl]) :-
    var(Var), !.
flatten([], Tl, Tl) :- !.
flatten([Hd|Tl], Tail, List) :- !,
    flatten(Hd, FlatHeadTail, List),
    flatten(Tl, Tail, FlatHeadTail).
flatten(NonList, Tl, [NonList|Tl]).

Your code seems fairly correct WRT your comment:

?- flat([1,2,[3,4]],[1,2,3,4]).
true ;
false.
于 2012-06-27T06:56:34.087 回答