%% https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/
%% Pack consecutive duplicates of list elements into sublists.
%% If a list contains repeated elements they should be placed in
separate sublists.
%% Example:
%% ?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
%% X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]]
% pack $INPUTLIST into $OUTPUTLIST
pack([], []).
pack([X], [[X]]).
pack([X,X|Zs], [[X,X|AllX] |NewPack]) :- packAll(X, Zs, AllX, Rest),
pack(Rest, NewPack).
pack([X,Y|Zs], [[X],[Y|AllY]|NewPack]) :- packAll(Y, Zs, AllY, Rest),
pack(Rest, NewPack).
% packAll $X from $LIST into $OUTPUT and any non-X goes into $NEWPACK
packAll(X, [], [], []).
packAll(X, [X|Zs], [X|Xp], NewPack) :- packAll(X, Zs , Xp, NewPack).
packAll(X, [Y|Zs], [], [Y|Zs]).
> My pack program is almost correct, except it does not handle the final
> list in the input correctly. I would appreciate some input on how to
> fix my problem:
>
> %% https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/
> %% Pack consecutive duplicates of list elements into sublists.
> %% If a list contains repeated elements they should be placed in
> separate sublists.
> %% Example:
> %% ?- pack([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
> %% X = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]]
>
> % pack $INPUTLIST into $OUTPUTLIST
You need to add calls to dif(X,Y) to ensure that X and Y do not unify,
in both pack and packAll:
> pack([], []).
> pack([X], [[X]]).
>
> pack([X,X|Zs], [[X,X|AllX] |NewPack]) :- packAll(X, Zs, AllX, Rest),
> pack(Rest, NewPack).
> pack([X,Y|Zs], [[X],[Y|AllY]|NewPack]) :-
dif(X,Y),
> packAll(Y, Zs, AllY, Rest),
> pack(Rest, NewPack).
>
> % packAll $X from $LIST into $OUTPUT and any non-X goes into $NEWPACK
>
> packAll(X, [], [], []).
> packAll(X, [X|Zs], [X|Xp], NewPack) :- packAll(X, Zs , Xp, NewPack).
> packAll(X, [Y|Zs], [], [Y|Zs]) :-
dif(X,Y).
?- pack([a,a,a,a,b,b,b,a,a,a,c,d,d,d,e,e,e,e,e],X),print(X).
[[a, a, a, a], [b, b, b], [a, a, a], [c], [d, d, d], [e, e, e, e, e]]
X = [[a, a, a, a], [b, b, b], [a, a, a], [c], [d, d, d], [e, e, e|...]] ;
false.
Here is how I would do it:
packRuns([],[]).
packRuns([X],[[X]]).
packRuns([X|Rest],[XRun|Packed]):-
run(X,Rest,XRun,RRest),
packRuns(RRest,Packed).
run(Var,[],[Var],[]).
run(Var,[Var|LRest],[Var|VRest],RRest):-
run(Var,LRest,VRest,RRest).
run(Var,[Other|RRest],[Var],[Other|RRest]):-
dif(Var,Other).
?- packRuns([a,a,a,a,b,b,b,a,a,a,c,d,d,d,e,e,e,e,e],X),print(X).
[[a, a, a, a], [b, b, b], [a, a, a], [c], [d, d, d], [e, e, e, e, e]]
X = [[a, a, a, a], [b, b, b], [a, a, a], [c], [d, d, d], [e, e, e|...]] ;
false.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Here is how I would do it:
:- use_module(library(lists), [keyclumped/2]).
pack(List, Packed) :-
( foreach(X,List),
foreach(X-X,Tagged)
do true
),
keyclumped(Tagged, Keyclumped),
( foreach(_-Clump,Keyclumped),
foreach(Clump,Packed)
do true
).
How about:
pack([], []).
pack([X], [[X]]).
pack([X, X| L], [[X| Xs]| R]) :-
pack([X| L], [Xs| R]).
pack([X, Y| L], [[X]| R]) :-
X \= Y,
pack([Y| L], R).
This solution assumes that the original list contains no variables. On
the other hand, it will run on any Prolog compiler, as it doesn't
depend on proprietary predicates (such as dif/2 or do/2), which seems
more fit for someone learning Prolog programming.
Cheers,
Paulo
> How about:
>
> pack([], []).
> pack([X], [[X]]).
> pack([X, X| L], [[X| Xs]| R]) :-
> pack([X| L], [Xs| R]).
> pack([X, Y| L], [[X]| R]) :-
> X \= Y,
> pack([Y| L], R).
Just for fun ... how about
pack([],[]).
pack([X|R],Out) :-
pack(R,ROut),
(ROut = [[X|A]|B] ->
Out = [[X,X|A]|B]
;
Out = [[X]|ROut]
).
Cheers
Bart Demoen
>
> You need to add calls to dif(X,Y) to ensure that X and Y do not unify,
> in both pack and packAll:
Actually I do not. Because the first clause requires that they are
equal, the second clause will only fire when they fail to be equal.
My problem was misreading the output [e,e,e|...] as being non-
terminating when it wasnt.
But thanks for the input... also note X \= Y is another way to check
for non-equality.
> On Jun 1, 6:28 pm, p...@informatimago.com (Pascal J. Bourguignon) wrote:
>
>
>> You need to add calls to dif(X,Y) to ensure that X and Y do not unify,
>> in both pack and packAll:
>
> Actually I do not. Because the first clause requires that they are
> equal, the second clause will only fire when they fail to be equal.
On backtracking the last clause will "fire" even if X and Y do unify.
So the \= is needed, unless you prevent backtracking in some other way.
That gives rise to extra and incorrect solutions to the query.
Cheers
Bart Demoen