Flatten a list in Prolog

Question

I've only been working with Prolog for a couple days. I understand some things but this is really confusing me.

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 false instead of 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.

Solution 1

The definition of flatten2/2 you've given is busted; it actually behaves like this:

?- flatten2([a, [b,c], [[d],[],[e]]], R).
R = [a, b, c] ;
false. 

So, given the case where you've already bound R to [a,b,c,d,e], the failure isn't surprising.

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:

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.

Note that, in most Prolog implementations, the empty list [] is an atom and a 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.

Solution 2

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:

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 reverse anywhere. This technique is known as "difference lists", but it's much easier just to think about it as "open-ended lists" instead.

---

update: This is much easier coded using the dcg syntax. Since it is unidirectional (the first argument must be fully ground), why not use cuts after all:

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,c],[[d],[],[e]]]), R, [1,2,3]).
R = [a, b, c, d, e, 1, 2, 3].

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

(edit2: simplified both versions, thanks to @mat's comments!)

Solution 3

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

Solution 4

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.

Solution 5

Building on if_//3 and list_truth/2, we can implement myflatten/2 as follows:

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_t and not(nil_or_cons_t) describe have same solutions, but the solution order differs. Consider:

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

View more solutions

Comments

[mat]

With this specific task, please also consider a more general case: What should ?- flatten([X], Ls). yield? You may think that it "obviously" should yield Ls = [X]. However, you then have the following problem: ?- flatten([X], Ls), Ls = [X], X = [a]. succeeds, but if we simply exchange the goals by commutativity of conjunction, we get: ?- Ls = [X], X = [a], flatten([X], Ls)., or more compactly, ?- flatten([[a]], [[a]])., which of course must fail because [[a]] is not a flat list. So, which is it? Fail or succeed? This shows that this is really not a nice relation at all.

[mat]

This is why I recommend you take a look at append/2. It limits this relation to a more meaningful and often also more practically useful version.

[ToastyMallows]

You're right it was busted. I don't know why I was getting the right answer before. I understand how your approach works but how does it get rid of empty lists? Also, why is [] an atom?

[Will Ness]

@ToastyMallows it gets rid of []s because appending a list and an [] gets you your same list back. [] is both atom and list for historical reasons. Look up "cons" and "nil". [] is what's known in LISP as "nil".

[Will Ness]

I tried flatten([a,[b,c],[],[[[d]]]],X) call with your code and it didn't work. The atom-handling case seems missing in your version.

[Will Ness]

but now it produces X = [a, [c, b], [[[d]]]].

[FranXh]

(I am new to prolog) What does the ! stand for? I had the same solution, but without ! it does not work

[Admin]

! is a special character called a cut in Prolog. It tells the interpreter to cut (ignore) other choices to prevent backtracking. For more information, Learn Prolog Now! has a nice tutorial.

[FK82]

Technically I like your solution best, but it didn't work for me in SWI-Prolog 6.

[Will Ness]

usually we try to avoid append, unless it's O(1), like with e.g. difference lists, app(A-B,B-C,A-C)..

[FK82]

I tried flatten2([1,[8,3],[3,[5,6],2],8], X). and it returned false.

[FK82]

@WillNess Yeah, well I'm new to Prolog. :-) I tried to avoid append but couldn't get it to work using lists only.

[Will Ness]

@FK82 you're right, I should've used atomic/1 instead of atom/1. -- fixed it, thanks!

[Will Ness]

nicely done. :) (you didn't do the usual flatten, flatten, append - you tried to make at least one recursive call as a tail call; good). -- BTW, a clause that always fails can be safely removed altogether - whether it matches a clause's head and immediately fails, or just fails because there was no (any more) matches, doesn't matter: a fail is a fail.

[FK82]

@WillNess Thank you, noted! :)

[false]

This renames variables element-wise in, say, [[f(X),g(X)]]

[bph]

what does list( X ) :- var(X) , ! , fail . mean?

[Nicholas Carey]

list(X) :-var(X) , ! , fail. say, "If X is an unbound variable, X is not a list." The !, fail. bit eliminates the choice point (so it can't follow the predicate's other alternative paths) and fails. With that that guard clause, an unbound variable would unify with [] and succeed. And on backtracking, it would unify (again) with [_|_] and succeed a second time. A true/false check for list-ness should be deterministic.

[mat]

?- flatten(Ls0, Ls). yields: Out of local stack.

[Loic]

Variables are not allowed in the first argument, indeed. Otherwise, I believe that the correct solution is computed if it exists.

[mat]

!//0 is a DCG nonterminal, there is no need to wrap it. For example, you can write flattn([]) --> !. However, you must use phrase/2 to portably access a DCG! An implementation is free to choose any expansion method it wants, and indeed need not expand the DCG to explicit differences at all. For example, in some abstract machines, using a different argument order may be a lot more efficient. If you rely on a particular expansion method, it will be increasingly harder to implement such optimizations in future systems.

[mat]

I have upvoted this because the DCG version is the first version of the predicate in this whole thread that I think I have a chance to understand ;-) You can still simplify it though!

[Will Ness]

nice idea! too bad it doesn't work for the above mentioned case, but it works for the fully ground lists, so, it's still nice. :)