Extracting sequences (Lists) Prolog

Question

Given a list eg [1,2,3,7,2,5,8,9,3,4] how would I extract the sequences within the list?

A sequence is defined as an ordered list (Normally I would say n-tuple but I have been told in prolog a tuple is referred to as a sequence). So we want to cut the list at the point where the next element is smaller than the previous one.

So for the list [1,2,3,7,2,5,8,9,3,4] it should return:

[ [1,2,3,7], [2,5,8,9], [3,4] ] %ie we have cut the list at position 4 & 8.

For this exercise you CANNOT use the construct ; or ->

Many thanks in advance!

---

EXAMPLE RESULTS:

eg1.

?-function([1,2,3,7,2,5,8,9,3,4],X): %so we cut the list at position 4 & 9

X = [ [1,2,3,7], [2,5,8,9], [3,4] ].

eg2.

?-function([1,2,3,2,2,3,4,3],X): %so we cut the list at position 3,4 & 8

X = [ [1,2,3], [2], [2,3,4], [3] ]. 

---

Hopefully that helps clarify the problem. If you need further clarification just let me know! Thanks again in advance for any help you are able to provide.

Answer 1

First, let's break it down conceptually. The predicate list_ascending_rest/3 defines a relation between a list Xs, the left-most ascending sublist of maximum length Ys, and the remaining items Rest. We will use it like in the following query:

?- Xs = [1,2,3,7,2,5,8,9,3,4], list_ascending_rest(Xs,Ys,Rest).
Ys   = [1,2,3,7],
Rest = [2,5,8,9,3,4] ;
false.

The straight-forward predicate definition goes like this:

:- use_module(library(clpfd)).

list_ascending_rest([],[],[]).
list_ascending_rest([A],[A],[]).
list_ascending_rest([A1,A2|As], [A1], [A2|As]) :-
    A1 #>= A2.
list_ascending_rest([A1,A2|As], [A1|Bs], Cs) :-
    A1 #< A2,
    list_ascending_rest([A2|As], Bs,Cs).

Then, let's implement predicate list_ascendingParts/2. This predicate repeatedly uses list_ascending_rest/3 for each part until nothing is left.

list_ascendingParts([],[]).
list_ascendingParts([A|As],[Bs|Bss]) :-
    list_ascending_rest([A|As],Bs,As0),
    list_ascendingParts(As0,Bss).

Example queries:

?- list_ascendingParts([1,2,3,7,2,5,8,9,3,4],Xs).
Xs = [[1,2,3,7], [2,5,8,9], [3,4]] ;
false.

?-  list_ascendingParts([1,2,3,2,2,3,4,3],Xs).
Xs = [[1,2,3], [2], [2,3,4], [3]] ;
false.

---

Edit 2015/04/05

What if the ascending parts are known but the list is unknown? Let's find out:

?- list_ascendingParts(Ls, [[3,4,5],[4],[2,7],[5,6],[6,8],[3]]).
Ls = [3,4,5,4,2,7,5,6,6,8,3] ? ;
no

And let's not forget about the most general query using list_ascendingParts/2:

?- assert(clpfd:full_answer).
yes

?- list_ascendingParts(Ls, Ps).
Ls = [],      Ps = []                                                   ? ;
Ls = [_A],    Ps = [[_A]]                                               ? ;
Ls = [_A,_B], Ps = [[_A],[_B]], _B#=<_A, _B in inf..sup, _A in inf..sup ? ...

---

Edit 2015-04-27

Room for improvement? Yes, definitely!

By using the meta-predicate splitlistIfAdj/3 one can "succeed deterministically" and "use non-determinism when required", depending on the situation.

splitlistIfAdj/3 is based on if_/3 as proposed by @false in this answer. So the predicate passed to it has to obey the same convention as (=)/3 and memberd_truth/3.

So let's define (#>)/3 and (#>=)/3:

#>=(X,Y,Truth) :- X #>= Y #<==> B, =(B,1,Truth).
#>( X,Y,Truth) :- X #>  Y #<==> B, =(B,1,Truth).

Let's re-ask above queries, using splitlistIfAdj(#>=) instead of list_ascendingParts:

?- splitlistIfAdj(#>=,[1,2,3,7,2,5,8,9,3,4],Pss).
Pss = [[1,2,3,7],[2,5,8,9],[3,4]].        % succeeds deterministically
?- splitlistIfAdj(#>=,[1,2,3,2,2,3,4,3],Pss).
Pss = [[1,2,3],[2],[2,3,4],[3]].          % succeeds deterministically

?- splitlistIfAdj(#>=,Ls,[[3,4,5],[4],[2,7],[5,6],[6,8],[3]]).
Ls = [3,4,5,4,2,7,5,6,6,8,3] ;            % works the other way round, too
false.                                    % universally terminates

Last, the most general query. I wonder what the answers look like:

?- splitlistIfAdj(#>=,Ls,Pss).
Ls = Pss,              Pss = [] ;
Ls = [_G28],           Pss = [[_G28]] ;
Ls = [_G84,_G87],      Pss = [[_G84],[_G87]],        _G84#>=_G87 ;
Ls = [_G45,_G48,_G41], Pss = [[_G45],[_G48],[_G41]], _G45#>=_G48, _G48#>=_G41 
% and so on...

Answer 2

maplist/3 as suggested in the comment won't help you here because maplist/3 is good at taking a list and mapping each element into a same-size collection of something else, or establishing a relation evenly across all of the individual elements. In this problem, you are trying to gather contiguous sublists that have certain properties.

Here's a DCG solution. The idea here is to examine the list as a series of increasing sequences where, at the boundary between them, the last element of the prior sequence is less than or equal to the first element of the following sequence (as the problem statement basically indicates).

% A set of sequences is an increasing sequence ending in X
%    followed by a set of sequences that starts with a value =< X
sequences([S|[[Y|T]|L]]) --> inc_seq(S, X), sequences([[Y|T]|L]), { X >= Y }.
sequences([S]) --> inc_seq(S, _).
sequences([]) --> [].

% An increasing sequence, where M is the maximum value
inc_seq([X,Y|T], M) --> [X], inc_seq([Y|T], M), { X < Y }.
inc_seq([X], X) --> [X].

partition(L, R) :- phrase(sequences(R), L).

| ?- partition([1,2,3,4,2,3,8,7], R).

R = [[1,2,3,4],[2,3,8],[7]] ? ;

(1 ms) no
| ?-  partition([1,2,3,2,2,3,4,3],X).

X = [[1,2,3],[2],[2,3,4],[3]] ? ;

(1 ms) no

The only reason for the rule sequences([]) --> []. is if you want partition([], []) to be true. Otherwise, the rule isn't required.