0
votes

I am trying to work out how to remove duplicate elements in a list of lists in Prolog.

E.g:
input: [[1,2,3],[5,6],[3,4],[1,7]]

expected output: [[1,2,3],[5,6],[4],[7]]

I know I can use the predicate sort/2 to remove duplicates in a single list, but how do I get it to work across multiple lists?

1
coder, I've tried using sort so far, but with little success.piyo_kuro
A simple idea would be to traverse the list of lists storing the current element that you examine in a list if it does not belong in the list, if it already belongs it means you have encountered it before so ignore it and go on the next recursively.coder
What kind of predicate do I need to implement to do the traverse?piyo_kuro
Just a recursion, for example write a predicate: remove_dupl([H|T],L,L2):-... where [H|T] is the list of lists (H is a list), L is the list that you will keep the elements that you find and L2 will be the output list that you will build recursively.coder
so should I use member to check if each element in H is in T?piyo_kuro

1 Answers

1
votes

Here is my attempt. Hope you've made some attempts to solve it and learn from this...Anyway if you still didn't come up with anything take a look at the following code:

 remove_dupl(InL, OutL):- remove_dupl(InL, [], OutL1),remove_empty(OutL1,OutL).

remove_dupl([],_,[]).
remove_dupl([H|T],L,[[H1]|T2]):-
              H=[H1], \+member(H1,L), 
              remove_dupl(T,[H1|L],T2).
remove_dupl([H|T],L,[[H1|T2]|T3]):- 
              H=[H1|T1], \+member(H1,L), 
              remove_dupl([T1|T],[H1|L],[T2|T3]).
remove_dupl([H|T],L,T2):- 
              H=[H1|T1], member(H1,L), 
              remove_dupl([T1|T],L,T2).
remove_dupl([H|T],L,[[]|T2]):- 
              H=[H1], member(H1,L), 
              remove_dupl(T,L,T2).

remove_empty([],[]).
remove_empty([[]|T],T1):-remove_empty(T,T1).
remove_empty([[H|T]|T1],[[H|T]|T2]):-remove_empty(T1,T2).

Maybe not the most efficient solution. Example:

?- remove_dupl([[1,2,3],[5,6],[3,4],[1,7]],L).
L = [[1, 2, 3], [5, 6], [4], [7]] ;
false.