1

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
  • 12,832
  • 5
  • 39
  • 53
piyo_kuro
  • 105
  • 9
  • coder, I've tried using sort so far, but with little success. – piyo_kuro Sep 02 '17 at 22:10
  • 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 Sep 02 '17 at 22:24
  • What kind of predicate do I need to implement to do the traverse? – piyo_kuro Sep 02 '17 at 22:30
  • 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 Sep 02 '17 at 22:51
  • so should I use member to check if each element in H is in T? – piyo_kuro Sep 02 '17 at 22:55
  • Yes exactly...For example you could define clause similar to: `remove_dupl([H|T],L,[[H1|T2]|T3]):- H=[H1|T1], \+member(H1,L), remove_dupl([T1|T],[H1|L],[T2|T3]).` if that helps... – coder Sep 02 '17 at 23:01
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/153535/discussion-between-piyo-kuro-and-coder). – piyo_kuro Sep 02 '17 at 23:11

1 Answers1

1

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.
coder
  • 12,832
  • 5
  • 39
  • 53
  • Thanks for the code, but will you be able to tell me what is the difference between the 2nd and 3rd code? Thank you. – piyo_kuro Sep 03 '17 at 12:42
  • 1
    You mean 2nd and 3rd clause because this is one code? If yes then I use the 2nd clause for the case that I'm examining the last element of a list so H=[H1] and not [H1|T1] so to close in this point the output list by writing just `[[H1]|T2]` and not `[[H1|T2]|T3]` I had to separate these two cases. – coder Sep 03 '17 at 12:52
  • Yes, and thank you for your explanations. I have traced the code and understood it. ^_^ – piyo_kuro Sep 03 '17 at 13:05
  • Hey, just one question, when I ran the query ?- remove_dupl([[-1,-3,-4],[2,3,-4],[1,-2,4],[1,3,4],[-1,2,-3]],L). it output as false (failed). – piyo_kuro Sep 03 '17 at 13:17
  • Funnily, when i run the query above, it works fine for the first list, and from the second list (i.e. [2,3,-4]) it works fine until it reaches -4, then it redo back the method till 2. – piyo_kuro Sep 03 '17 at 13:24
  • 1
    The problem was in handling the case H=[H1] when member(H1,L) so added last clause, though this may leave empty lists in the final list for example in your last query all the elements from [1,3,4] must not be included leaving an empty list in this solution, so I think the easiest way based on the above solution was just to remove empty lists using another predicate. – coder Sep 03 '17 at 13:58