Trying to break elements which are lists in a list?

Question

I am trying to write a program which make the following:

?- g([2,3, [22,[3],9] ,4,[5],99],X).

X= [2,3,22,[3],9 ,4,5,99]

So it searches for lists in the given list and replace it by their elements without brackets [].

So I wrote this program:

The first block just searches for the first element in the list which is list
If there is no such element it returns [there_is_no_list].

first_list_in_the_list([],[there_is_no_list]):-!.  
first_list_in_the_list([H|_],X):-is_list(H),X=H,!.  
first_list_in_the_list([_|T],X):-first_list_in_the_list(T,X).

The first block works in prolog perfectly.

The second block just search in the list for an element X and then split the list into a two lists one is the list of all elements before X and the second is the elements after X.

splite_when_find_element([H|T],H,[],T):-!.  
splite_when_find_element([H|T],X,F,G):-
    splite_when_find_element(T,X,F1,G),append([H],F1,F).

it also works fine in Prolog.

and the third block is append, and it joins two list together in a new list.

append([],L,L).  
append([H|T],L,[H|U1]):- append(T,L,U1).

and the last part is:

gg(L,L):-first_list_in_the_list(L,[there_is_no_list]),!.    
gg(L,U):-first_list_in_the_list(L,X),
         splite_when_find_element(L,X,F,G),gg(G,R),append(F,X,E),
         append(E,R,U).

When I give a query [2,[3],5] I get also [2,[3],5] and I really don't understand why it does this.

possible duplicate of [Flatten a list in Prolog](http://stackoverflow.com/questions/9059572/flatten-a-list-in-prolog) — Nicholas Carey, Aug 08 '13 at 16:53
Your example doesn't get rid of all the sublists but seems to remove only one level in between. For example, `[1, 2, [3, [4], 5], 6]` becomes `[1, 2, 3, [4], 5, 6]` if I try to follow your example. Is that what you intend? — lurker, Aug 08 '13 at 17:04

score 2 · Accepted Answer · answered Aug 09 '13 at 09:17

A simple recursive solution will also work. Recursion is done by the head of the input list. In the non-trivial case, when the head is a list itself, we just append the rest of the flattened list to it. In the code below, it has not flattened Rest yet in append(H, Rest, Out), but it will be, after the recursive call of g(In, Rest). Cut after the append call ensures that backtracking won't consider the last case, where the head will appear in the output as-is.

% Base case, empty list.

g([], []).

% First recursive case: head is list.
% Append remaining elements to it.

g([H|In], Out):-
    append(H, Rest, Out), !,
    g(In, Rest).

% Second recursive case: head is not list.
% Will appear as-is in the output.

g([H|In], [H|Out]):-
    g(In, Out).

score 1 · Answer 2 · answered Aug 09 '13 at 10:14

1

also a DCG can do

lev, X --> [X], {is_list(X)}, lev.
lev, [X] --> [X], lev.
lev --> [].

test:

?- phrase(lev,[a,[b,c,[d]],e],L).
L = [a, b, c, [d], e] .

answered Aug 09 '13 at 10:14

CapelliC

59,646
5
47
90

score 0 · Answer 3 · answered Aug 09 '13 at 00:31

To flatten 1 level of a nested list, try something like this:

flatten1( Xs , Ys ) :-        % to flatten a list
  flatten1( Xs , [] , Ys ) ,  % - invoke the worker predicate
  .                           %

flatten1( [] , T , R ) :-          % if we get to to the empty list
  reverse(T,R)                     % - just reverse the accumulator and we're done.
  .                                %
flatten1( [X|Xs] , T , R ) :-      % if the head of the list is unbound 
  var(X) ,                         % - check for being a var 
  ! ,                              % - cut (to eliminate problems on backtracking
  T1 = [X|T] ,                     % - prepend the head of the list to the accumulator
  flatten( Xs , T1 , R )           % - and recurse down
  .                                %
flatten1( [[]|Xs] , T , R ) :-     % if head of the list is an empty list, skip it
  flatten1( Xs , T , R )           % - ignore it and recurse down
  .                                %
flatten1( [[X|Ns]|Xs] , T , R ) :- % if head of the list is a non-empty list
  X1 = [Ns|Xs] ,                   % - prepend the tail of the sublist to the list
  T1 = [X|T] ,                     % - prepend the head of the sublist to the accumulator
  flatten( X1 , T1 , R )           % - and recurse down
  .                                %
flatten( [X|Xs] , T , R ) :-       % if the head of the list is something else (except an unbound variable)
  T1 = [X|T] ,                     % - prepend the list head to the accumulator and
  flatten( Xs , T1 , R )           % - recurse down
  .                                %

Trying to break elements which are lists in a list?

3 Answers3