How to remove sub-lists in prolog?

Question

Can someone help me, please? I need to solve this problem in prolog and I don't know how...

"Given a list of integer numbers. Remove all sub-lists formed from decreases elements."

Answer 1

We remove descending sublists in three steps:

1. separate decreasing and non-decreasing parts (using splitlistIfAdj/3 and (#=<)/3)

   ?- splitlistIfAdj(#=<,[ 1 , 2 , 3 , 4,3,2,1 , 2 , 3 , 4,3,2,1 , 2 ],Xs1).
   Xs1 =                 [[1],[2],[3],[4,3,2,1],[2],[3],[4,3,2,1],[2]].
   

2. exclude non-singleton lists (using tfilter/3, Prolog lambdas, and (=)/3)

   ?- tfilter(\[_|T]^(T=[]),[[1],[2],[3],[4,3,2,1],[2],[3],[4,3,2,1],[2]],Xs2).
   Xs2 =                    [[1],[2],[3],          [2],[3],          [2]].
   

3. map singleton lists to items (using maplist/3 and Prolog lambdas)

   ?- maplist(\[H|_]^H^true,[[1],[2],[3],[2],[3],[2]],Xs).
   Xs =                     [ 1 , 2 , 3 , 2 , 3 , 2 ].
   

---

Let's put it together!

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

descending_removed(Xs0,Xs) :-
   splitlistIfAdj(#=<,Xs0,Xs1),
   tfilter(\[_|T]^(T=[]),Xs1,Xs2),
   maplist(\[H|_]^H^true,Xs2,Xs).

Here are some queries:

?- descending_removed([1,2,3,4,3,2,1,2,3,4,3,2,1,2],Xs).
Xs = [1,2,3,2,3,2].

?- descending_removed([4,3,2,1,0],Xs).
Xs = [].

?- descending_removed([1,2,3,4],Xs).
Xs = [1,2,3,4].

?- descending_removed([1,2,3,  4,3,3,2,2,1],Xs).
Xs = [1,2,3].

?- descending_removed([1,2,3,4,4,3,3,2,2,1],Xs).
Xs = [1,2,3,4].

Answer 2

We can improve this answer by using tchoose/3 instead of tfilter/3 and maplist/3, removing descending sublists in two steps---not three:

1. separate decreasing and non-decreasing parts (using splitlistIfAdj/3 and (#=<)/3)

   ?- splitlistIfAdj(#=<,[ 1 , 2 , 3 , 4,3,2,1 , 2 , 3 , 4,3,2,1 , 2 ],Xs1).
   Xs1 =                 [[1],[2],[3],[4,3,2,1],[2],[3],[4,3,2,1],[2]].
   

2. filter singleton lists and map to items (using tchoose/3, Prolog lambdas, and (=)/3)

   ?- tchoose(\[H|T]^H^(T=[]),[[1],[2],[3],[4,3,2,1],[2],[3],[4,3,2,1],[2]],Xs).
   Xs =                       [ 1 , 2 , 3 ,           2 , 3 ,           2 ].
   

Let's put it together!

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

descending_removed(Xs0,Xs) :-
   splitlistIfAdj(#=<,Xs0,Xs1),
   tchoose(\[H|T]^H^(T=[]),Xs1,Xs).

Same queries, same results:

?- descending_removed([1,2,3,4,3,2,1,2,3,4,3,2,1,2],Xs).
Xs = [1,2,3,2,3,2].

?- descending_removed([4,3,2,1,0],Xs).
Xs = [].

?- descending_removed([1,2,3,4],Xs).
Xs = [1,2,3,4].

?- descending_removed([1,2,3,  4,3,3,2,2,1],Xs).
Xs = [1,2,3].

?- descending_removed([1,2,3,4,4,3,3,2,2,1],Xs).
Xs = [1,2,3,4].

Answer 3

Let's start with some sample list of numbers:

1 2 3 4 3 2 1 2 3 4 3 2 1 2

After eliminating all decreasing sublists we should have

1 2 3 2 3 2

How could this be done? I would propose going through the list and observing how the "output" is generated when looking at group of numbers:

A B C
  1 2   -> output 1
1 2 3   -> output 2
2 3 4   -> output 3
3 4 3   -> output none
4 3 2   -> output none
3 2 1   -> output none
2 1 2   -> output none
1 2 3   -> output 2
2 3 4   -> output 3
3 4 3   -> output none
4 3 2   -> output none
3 2 1   -> output none
2 1 2   -> output none
1 2     -> output 2

What we see is that we output number from middle column B only when A < B < C. So this is what we can do: we can go through entire list and check number triples. If the're sorted then we output B.

remove_dec([], []).
remove_dec(Input, Output) :-
    min_list(Input, Min),
    remove_dec0([ Min | Input ], Output).
remove_dec0([ A, B, C | Input], [ B | Output ]) :-
    A =< B, B =< C,
    remove_dec0([ B, C | Input], Output).
remove_dec0([ _, B, C | Input], Output) :-
    remove_dec0([ B, C | Input], Output).
remove_dec0([A, B], [B]) :-
    A =< B.
remove_dec0([A, B], []) :-
    A > B.

Sample input and output:

?- remove_dec([1,2,3,4,3,2,1,2,3,4,3,2,1,2],R).
R = [1, 2, 3, 2, 3, 2] .

?- remove_dec([4,3,2,1,0],R).
R = [] ;
false.

?- remove_dec([1,2,3,4],R).
R = [1, 2, 3, 4] .

Answer 4

What about (using same names and test than in previous answers):

descending_removed(L,R) :- dr(a,L,R).

dr(_,[],[]).

dr(DIR,[A|Q],R) :-
  ( [B|_]=Q, A>B ->  
        dr(d,Q,R)
  ;
        dr(a,Q,T), ( DIR=a -> R=[A|T]; R=T )
  ).

verification:

test :-
  descending_removed([1,2,3,4,3,2,1,2,3,4,3,2,1,2],[1,2,3,2,3,2]),
  descending_removed([4,3,2,1,0],[]),
  descending_removed([1,2,3,4],[1,2,3,4]),
  descending_removed([1,2,3,4,3,3,2,2,1],[1,2,3]),
  descending_removed([1,2,3,4,4,3,3,2,2,1],[1,2,3,4]),
  descending_removed([1],[1]).

gives following result:

[debug]  ?- test.
true ;
false.

If we want to cover the case of two consecutive equal values, with the interpretation they doesn't changes the curve tendency, we can define:

descending_removed(L,R) :- dr(a,L,R).

dr(_,[],[]).

dr(DIR,[A|Q],R) :-
  ( [B|_]=Q, A>B ->  
        dr(d,Q,R)
  ; [B|_]=Q, A=B ->  
        dr(DIR,Q,T), ( DIR=a -> R=[A|T]; R=T )   
  ;   
        dr(a,Q,T), ( DIR=a -> R=[A|T]; R=T )
  ).

that produces following answers:

descending_removed([1,2,2,2,3,4,3,3,2,2,1],R).
R = [1, 2, 2, 2, 3] ;
false

descending_removed([1,2,3,3,2,4,3,3,2,2,5],R).
R = [1, 2, 3, 5]
false