Check if list is Flattened or not in Prolog

user_7024599 0
Viewed 153

Given a list, I want to check whether the given list is flat or not using prolog.

Example:-

1. ?- is_flat([1,2,3]) should return true

2. ?- is_flat([1,f,2,r(p),8]) should return true

3. ?- is_flat([1,2,[3,e,w],u]) should return false

I am thinking of the logic i.e traverse each element of list and then using is_list check, whether the head is a list or not. I tried as:

is_flat([]).
is_flat([H|T]) :- is_list(H), is_flat(T).

But I don't think I am on the right track. Please suggest how I can solve this.

prolog
2 Answers

The approach as given is correct, we just need to "inverse the truth value" of the is_list/2 test (or, more accurately, declare the proof as having failed as soon as we encounter a list). For good measure, I add a completely unnecessary message writing instruction:

is_flat([]).
is_flat([X|Xs]) :- 
   format("Examining ~q\n",[X]),
   \+ is_list(X),
   is_flat(Xs).

Then:

?- is_flat([a,b,c]).
Examining a
Examining b
Examining c
true.

But:

?- is_flat([a,[x,y,z],c]).
Examining a
Examining [x,y,z]
false.

Using maplist/2

This can be done compactly with maplist/2, which applies a predicate to each element and breaks off as soon as failure appears for such an application:

another_is_flat(List) :- maplist(not_is_list,List).

not_is_list(L) :- \+ is_list(L).

Then:

?- another_is_flat([a,b,c]).
true.

?- another_is_flat([a,[x,y,z],c]).
false.

Using forall/2

Or using CapelliC's solution. forall/2 is exactly made for this: It performs a test (in this case, \+is_list(E)) for every successful condition (in this case member(E,L)), and behaves like a short-circuiting AND (that also leaves no accidental bindings behind on success):

another_another_is_flat(L) :- forall(member(E,L),\+is_list(E)).

Then:

?- another_another_is_flat([a,b,c]).
true.

?- another_another_is_flat([a,[x,y,z],c]).
false.

Edge case:

?- another_another_is_flat([]) .
true.

The "vacuous truth": an empty list is correctly accepted.

user_8844630

The short, non-rigorous way:

flat_list( [ []    | _  ] ) :- !, fail.       % not flat : a list containing the empty list
flat_list( [ [_|_] | _  ] ) :- !, fail.       % not flat : a list containing a non-empty list
flat_list( []             ) .                 %     flat : the empty list
flat_list( [ _     | Xs ] ) :- flat_list(Xs). %     flat : anything else, so long as the tail is flat
user_4674730
Related