Decompose list into lists of successive subsequences

Question

I am really sorry for previous question, it's my first time post question on this website and I really didn't know I shouldn't post quesion like that. It was my first time using prolog. Actually I spent more than 5 hours on this question but still cannot fully solve it, I tried to tear this question apart and here is what remain to be solved:

How to put the successive increasing whole numbers into a sublist in origin list.

eg. [3,5,1,2,3,7,8,2] to [3,5,[1,2,3],[7,8],2]

Here is what I wrote, can someone tell me how to fix the code? Thanks.

% empty List
chop_up([], []).

% single item list
chop_up([X], [X]).

% continue if the first number is not part of a sequence
chop_up(List, NewList):-
    List = [First | Tail],
    Tail = [Second | _],
    First =\= Second - 1,
    chop_up(Tail, NewList2),
    NewList = [First | NewList2].

% if it is part of a sequence
chop_up(List, NewList):-
    List = [First | Tail],
    Tail = [Second | Tail2],
    First is Second - 1,
    chop_up(Tail, NewList2),
    NewList = [[First] | NewList2].

enter image description here

Answer 1

Finally I did it! this is reversible(generalized) version.This program works cleverly. It was very fun developing this.

Code:

chunk_list([])-->[],!.
chunk_list([Chunk|Rest])-->chunk(Chunk),!,chunk_list(Rest).

chunk([First,Last])-->sequence([First,Last]),{First<Last}. % sequence
chunk(Val)-->sequence([Val,Val]).               % isolated number

sequence([First,Last])-->
                {(number(First),number(Last))->First<Last;true},
                [First],
                {succ(First,Second)},sequence([Second,Last]).
sequence([Val,Val])-->[Val].

Test:

[eclipse 4]: phrase(chunk_list([2,[2,6],[3,5],3,7,[1,3]]),Ret).

Ret = [2, 2, 3, 4, 5, 6, 3, 4, 5, 3, 7, 1, 2, 3]
Yes (0.00s cpu)

[eclipse 5]: phrase(chunk_list(Ret),[3,4,5,2,1,6,7,88,9,4,5,6,7,2,1,2,3]).

Ret = [[3, 5], 2, 1, [6, 7], 88, 9, [4, 7], 2, [1, 3]]
Yes (0.00s cpu)

[eclipse 6]: phrase(chunk_list([[2,4],A,[2,8],3]),[2,B,4,6,2,C,4,5,6,7,D,E]).

A = 6
B = 3
C = 3
D = 8
E = 3
Yes (0.00s cpu)

Answer 2

I conseived much more elegant way with DCG!

chunk_list([])-->[].
chunk_list([C|Rest])-->chunk(C),chunk_list(Rest).

chunk(Ret)-->[First],consecutive(First,Last),{First=:=Last->Ret is First;Ret = [First,Last]}.

consecutive(Prev,Last)-->[Current],{Current is Prev+1},consecutive(Current,Last).
consecutive(Prev,Prev)-->[].

Test:

 ?- phrase(chunk_list(R),[1,2,3,6,7,3,3,2,3,4,6],[]).
R = [[1, 3], [6, 7], 3, 3, [2, 4], 6] 

maybe it could be reversible with more lavor. I.E. convert [[1, 3], [6, 7], 3, 3, [2, 4], 6] into [1,2,3,6,7,3,3,2,3,4,6]

Answer 3

I also tried for my prolog training. terrible program but does work anyway. I tested this in ECLiPSe but it will work with few modification in other environment(may be only deleting :-lib(listut))

call like this:

chunk([4,5,6,3,4,4,57,3,4,5,7,2,3,4,5,7,7,54,3],Ret).

Program:

:-lib(listut).

chunk(List,Ans):-
    chunk_sub(List,0,[],List1),
    first_and_lasts(List1,Ans),
    !.


chunk_sub([],_,Ret,Reverse):-reverse(Ret,Reverse),!.
chunk_sub([Current|Rest],Prev,[NowList|RetRest],Ret):-
    Current =:= Prev+1,
    append(NowList,[Current],NextList),
    chunk_sub(Rest,Current,[NextList|RetRest],Ret).
chunk_sub([Current|Rest],_,NowList,Ret):-
    chunk_sub(Rest,Current,[[Current]|NowList],Ret).

first_and_lasts([],[]):-!.
first_and_lasts([FirstList|RestLists],[Converted|RestRet]):-
    length(FirstList,Len),
    (
        Len=:=1->
        ([OneElem]=FirstList,Converted=OneElem);
        (
            nth1(1,FirstList,Smallest),
            nth1(Len,FirstList,Biggest),
            Converted=[Smallest,Biggest]
        )
    ),
    first_and_lasts(RestLists,RestRet).

Answer 4

Thank you for updating your question to show us what you tried!

Like all Prolog beginners, you are trying to do too much at once. This is normal! But you have to learn and get used to a way of thinking that is different from other programming languages. Almost always you have to decompose your problem into several subproblems that you then put together to get the final program.

So let's try to solve only one part of the problem first: Given a nonempty list, decompose it into successive elements at the front and into all the remaining elements. That is, we want something like this:

?- list_successive_rest([1, 2, 4, 3], Succ, Rest).
Succ = [1, 2],
Rest = [4, 3] .

If we can write this definition, then we should be able to iterate over the Rest to chop it up further.

Here is a definition of list_successive_rest/3. Note how it follows the structure of your attempt for chop_up/2, but it's shorter and simpler because we only look at a successive prefix of the list, not all of the list at once:

list_successive_rest([X], [X], []).
list_successive_rest([A, B | Xs], [A], [B | Xs]) :-
    A + 1 =\= B.
list_successive_rest([A, B | Xs], [A | Successive], Rest) :-
    A + 1 =:= B,
    list_successive_rest([B | Xs], Successive, Rest).

(This is also simpler than your version because I match lists of at least two elements as [A, B | Xs] rather than [A | Tail] and Tail = [B | Tail2]. It's a good idea to get used to this syntax.)

We can call this successively to decompose a list into successive parts:

?- list_successive_rest([1, 2, 4, 3], Succ, Rest), list_successive_rest(Rest, Succ2, Rest2), list_successive_rest(Rest2, Succ3, Rest3).
Succ = [1, 2],
Rest = [4, 3],
Succ2 = [4],
Rest2 = Succ3, Succ3 = [3],
Rest3 = [] ;
false.

Defining chop_up/2 is now easy by using the above predicate to peel off successive prefixes of the list iteratively:

chop_up([], []).
chop_up(List, [Succ | Chopped]) :-
    list_successive_rest(List, Succ, Rest),
    chop_up(Rest, Chopped).

Note that chop_up/2 is recursive, and it uses list_successive_rest/3, which is recursive as well. Trying to write all this in one recursive predicate would be harder and lead to less readable code.

Let's try the above test, and your test case:

?- chop_up([1, 2, 4, 3], Chopped).
Chopped = [[1, 2], [4], [3]] ;
false.

?- chop_up([3,5,1,2,3,7,8,2], Chopped).
Chopped = [[3], [5], [1, 2, 3], [7, 8], [2]] ;
false.

This doesn't actually produce the exact format you wanted: Singleton elements are singleton lists rather than "naked" members of the outer list. I think this is better this way, but your teacher may disagree. In that case, changing this small detail is an exercise for you.