Prolog - trying to flatten a list

Author

trying to flatten a list

Anders Lindén

2005-05-26, 9:00 pm

Hello!
I am trying to flatten a list (making a list like [1,3,[4,5],6,9] to become [1,2,4,5,6,9].
So I created a predicate flatten/2, that expects the first argument to be the list to be flattened and the next argument to become a
variable.
It would in other ways be called like this:
flatten([1,3,[4,5],6,9],X).

Here is the program:

flatten([],[]).
flatten([[A]|B],[A|B]).
flatten([A|B],[A|C]) :- not(A = [_|_]), flatten(B,C).

It seems that I do not get a unification against the 2nd predicate if the first element of the list denoted by arg 1 is a list!
Why?

Do I need to write it in another way?

And what about the check if A is not a list in the predicate on line 3?
Is that appropriate?

best regards
Anders Lindén

Roy Haddad

2005-05-26, 9:00 pm

Anders Lindén wrote:
> Hello!
> I am trying to flatten a list (making a list like [1,3,[4,5],6,9] to become [1,2,4,5,6,9].
> So I created a predicate flatten/2, that expects the first argument to be the list to be flattened and the next argument to become a
> variable.
> It would in other ways be called like this:
> flatten([1,3,[4,5],6,9],X).
>
>
> Here is the program:
>
> flatten([],[]).
> flatten([[A]|B],[A|B]).
> flatten([A|B],[A|C]) :- not(A = [_|_]), flatten(B,C).
>
>
> It seems that I do not get a unification against the 2nd predicate if the first element of the list denoted by arg 1 is a list!
> Why?

Your second predicate only catches single-value lists. That is, it only
catches things like [1,3,[4],6,...], but not [1,3,[4,5],6,...] or
[1,3,[],6,...].

Try starting the second predicate like this:

flatten([[A|B]|C], [X|Y]) :- ...

> And what about the check if A is not a list in the predicate on line 3?
> Is that appropriate?

First of all, the check is not equivalent to the statement "the first
argument of this predicate would not match in the second predicate",
which seems to have been your intention. It should have been "not(A =
[_])", if it was, but neither of those are efficient. You can get the
same behavior with a cut:

flatten([[A]|B],[A|B]) :- !.
flatten([A|B],[A|C]) :- flatten(B,C).

This forces Prolog to not try any other alternatives once it has found a
match.

Anders Lindén

2005-05-26, 9:00 pm

I solved it with this:

flatten2([],[]).
flatten2([[]|B],C) :- flatten2(B,C).
flatten2([[A|B]|C], D) :- flatten2([A,B|C], D).
flatten2([A|B], [A|C]) :- not(list(A)), flatten2(B,C).

not(A) :- A,!,fail;true.

now I instaed wonder this:

whats the difference between
not(A) :- A,!,fail;true.
and
not(A) :- !,A,fail;true.

rafe@cs.mu.oz.au

2005-05-28, 3:58 am

Anders Lind=E9n wrote:
>
> whats the difference between
> not(A) :- A,!,fail;true.
> and
> not(A) :- !,A,fail;true.

With

not(A) :- A, !, fail ; true.

a goal not(P) will call P. If P succeeds, the cut
commits to this arm of the disjunction, and then
the clause fails.

If P fails, Prolog backtracks into the second arm
of the disjunction which succeeds.

With

not(A) :- !, A, fail ; true.

a goal not(P) starts by committing to the first
disjunct. Then either P succeeds and we go on
to fail, or P fails and so not(P) fails. That
is, this definition of not/1 will always fail!

-- Ralph

PS What is it with Prolog programmers and bad code
layout? Adding a bit of whitespace doesn't cost
that much extra effort...

student

2005-05-28, 8:57 am

Anders Lindén wrote:
> Hello!
> I am trying to flatten a list.

For example

[1,3,[4,5],6,9] becomes [1,2,4,5,6,9]

This makes me think of picking apples.

pick([],In,In).

pick([Q|Tree],In,Out) :-
is_tree(Q),
pick(Q,In,Next),
pick(Tree,Next,Out).

pick([Q|Tree],In,Out) :-
\+ is_tree(Q),
pick(Tree,[Q|In],Out).

i.e.,

pick([Q|Tree],In,Out) :-
( is_tree(Q) ->
pick(Q,In,Next),pick(Tree,Next,Out)
;
pick(Tree,[Q|In],Out)
).

is_tree([]).
is_tree([_|L]) :-
is_tree(L).

| ?- pick([1,[[2,3],[[4,5,[a,[b],c,d],6]]],[7
,[u,[v]],8],9],[],Q).

Q = [9,8,v,u,7,6,d,c,b,a,5,4,3,2,1];
No

Too obvious.

There must be something more profound involved here.

Maybe I can do the picking "inside" is_tree (while I'm at it,
so to speak) ...

is_tree([],In,In).

is_tree([L|R],In,Out) :-
is_tree(L,In,Next),
is_tree(R,Next,Out).

is_tree([L|R],In,Out) :-
\+ is_tree(L,In,_),
is_tree(R,[L|In],Out).

i.e.,

is_tree([L|R],In,Out) :-
( is_tree(L,In,Next) ->
is_tree(R,Next,Out)
;
is_tree(R,[L|In],Out)
).

| ?- is_tree([1,[[2,3],[[4,5,[a,[b],c,d],6]]]
,[7,[u,[v]],8],9],[],Q).

Q = [9,8,v,u,7,6,d,c,b,a,5,4,3,2,1] ? ;
No

How weird is that?

bill

traveller

2005-06-01, 8:57 pm

student wrote:
>
> is_tree([L|R],In,Out) :-
> ( is_tree(L,In,Next) ->
> is_tree(R,Next,Out)
> ;
> is_tree(R,[L|In],Out)
> ).
>
> | ?- is_tree([1,[[2,3],[[4,5,[a,[b],c,d],6]]]
,[7,[u,[v]],8],9],[],Q).
>
> Q = [9,8,v,u,7,6,d,c,b,a,5,4,3,2,1] ? ;
> No
>
> How weird is that?
>

A bit mysterious, perhaps, but perfectly and completely reproducible,
which if anything makes it the opposite of "weird" (which means "ghostly").

Sponsored Links