Removing Duplicate Elements from List of Lists in Prolog

Question

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?

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

coder coder · Accepted Answer · 2017-09-03T12:39:02

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.

Removing Duplicate Elements from List of Lists in Prolog

1 Answers