CODEWITHSUNDEEP
listprologfiltering
user899372
user899372

Reputation: 63

managing lists in prolog

Im new to Prolog and was looking for some assistance. What i am trying to do is basically get a list L consisting of elements that repeat at least twice in a given list L'

Example L'=[1,2,1,3,4,3,2] => L=[1,2,3].

So far I am able to compute the occurrence of every consecutive variables

% pack(L1,L2) :- the list L2 is obtained from the list L1 by packing
%    repeated occurrences of elements into separate sublists.
%    (list,list) (+,?)

pack([],[]).
pack([X|Xs],[Z|Zs]) :- transfer(X,Xs,Ys,Z), pack(Ys,Zs).

% transfer(X,Xs,Ys,Z) Ys is the list that remains from the list Xs
%    when all leading copies of X are removed and transfered to Z

transfer(X,[],[],[X]).
transfer(X,[Y|Ys],[Y|Ys],[X]) :- X \= Y.
transfer(X,[X|Xs],Ys,[X|Zs]) :- transfer(X,Xs,Ys,Zs).

% encode(L1,L2) :- the list L2 is obtained from the list L1 by run-length
%    encoding. Consecutive duplicates of elements are encoded as terms [N,E],
%    where N is the number of duplicates of the element E.
%    (list,list) (+,?)

encode(L1,L2) :- pack(L1,L), transform(L,L2).

transform([],[]).
transform([[X|Xs]|Ys],[[N,X]|Zs]) :- length([X|Xs],N), transform(Ys,Zs).

which will return the following list of touples

?- encode([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [[4,a],[1,b],[2,c],[2,a],[1,d][4,e]]

But there still remains the problem of building a list that will contain distinct elements that repeat at least twice.

If anyone can help me or point me in the general direction that would be great.

Thanks in advance

Upvotes: 0

Views: 679

Answers (2)

CapelliC
CapelliC

Reputation: 60014

You could write a procedure:

% E it's the list of are elements from L that repeat at least twice
elements_that_repeat_at_least_twice(L, E) :-
  elements_that_repeat_at_least_twice(L, [], E).

elements_that_repeat_at_least_twice([H|Ls], Dupl, E) :-
  ...

In elements_that_repeat_at_least_twice the added list Dupl will keep each element you verify it's present multiple times. Examine each element of L, using [H|Ls]. Use memberchk/2 to verify if H is in L: then it's at least duplicate. If it's not yet in Dupl, add to it, and recurse. Remember to write the recursion base case (stop at empty list []).

Now I see you have added some code: then I complete suggestion:

elements_that_repeat_at_least_twice([], Dupl, Dupl).
elements_that_repeat_at_least_twice([H|Ls], Dupl, E) :-
  (  memberchk(H, Ls)
  -> ( \+ memberchk(H, Dupl)
     -> Dupl1 = [H|Dupl]
     ;  Dupl1 = Dupl
     )
  ;  Dupl1 = Dupl
  ),
  elements_that_repeat_at_least_twice(Ls, Dupl1, E).

Remember to reverse the list of duplicates when done.

Upvotes: 0

thanos
thanos

Reputation: 5858

an element E of list L should:
   be a member of list L',
   be a member of list L'' where L'' is list L' if we remove element E.

check select/3, member/2, findall/3 and/or setof/3

Upvotes: 1

Related Questions