Flatting a list

问题:

I need to write a function that flat a list.

For example:

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

this is what I did:

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

I know why it is not true but I do not know how to do that. thanks.

EDIT: almost work:

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

回答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]).

Here is swi-prolog solution by Jan Wielemaker and Richard O'Keefe, the code can be found in prolog's library directory, in lists.pl file.

回答2:

Code edited (see comments)

Another possibiliy, using DCG :

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

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

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

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

flat(X) --> [X].

Now we get :

 ?- 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] .

回答3:

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.