Search code examples
prolog

Prolog - remove the non unique elements


I have a predicate to check if the element is member of list and looks the following:

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).

When I called: ?- member(1,[2,3,1,4]) I get: true.

And now I have to use it to write predicate which will remove all non unique elements from list of lists like the following:

remove([[a,m,t,a],[k,a,w],[i,k,b,b],[z,m,m,c]],X).
X = [[t],[w],[i,b,b],[z,c]]

How can I do that?


Solution

  • Going by your example and @false's comment, the actual problem seems to be something like removing elements from each sublist that occur in any other sublist. My difficulty conceptualizing this into words has led me to build what I consider a pretty messy and gross piece of code.

    So first I want a little helper predicate to sort of move member/2 up to lists of sublists.

    in_sublist(X, [Sublist|_])  :- member(X, Sublist).
    in_sublist(X, [_|Sublists]) :- in_sublist(X, Sublists).
    

    This is no great piece of work, and in truth I feel like it should be inlined somehow because I just can't see myself ever wanting to use this on its own.

    Now, my initial solution wasn't correct and looked like this:

    remove([Sub1|Subs], [Res1|Result]) :-
        findall(X, (member(X, Sub1), \+ in_sublist(X, Subs)), Res1),
        remove(Subs, Result).
    remove([], []).
    

    You can see the sort of theme I'm going for here though: let's use findall/3 to enumerate the elements of the sublist in here and then we can filter out the ones that occur in the other lists. This doesn't quite do the trick, the output looks like this.

    ?- remove([[a,m,t,a],[k,a,w],[i,k,b,b],[z,m,m,c]], R).
    R = [[t], [a, w], [i, k, b, b], [z, m, m, c]].
    

    So, it starts off looking OK with [t] but then loses the plot with [a,w] because there is not visibility into the input [a,m,t,a] when we get to the first recursive call. There are several ways we could deal with it; a clever one would probably be to form a sort of zipper, where we have the preceding elements of the list and the succeeding ones together. Another approach would be to remove the elements in this list from all the succeeding lists before the recursive call. I went for a "simpler" solution which is messier and harder to read but took less time. I would strongly recommend you investigate the other options for readability.

    remove(In, Out) :- remove(In, Out, []).
    remove([Sub1|Subs], [Res1|Result], Seen) :-
        findall(X, (member(X, Sub1),
                    \+ member(X, Seen),
                    \+ in_sublist(X, Subs)), Res1),
        append(Sub1, Seen, Seen1),
        remove(Subs, Result, Seen1).
    remove([], [], _).
    

    So basically now I'm keeping a "seen" list. Right before the recursive call, I stitch together the stuff I've seen so far and the elements of this list. This is not particularly efficient, but it seems to get the job done:

    ?- remove([[a,m,t,a],[k,a,w],[i,k,b,b],[z,m,m,c]], R).
    R = [[t], [w], [i, b, b], [z, c]].
    

    This strikes me as a pretty nasty problem. I'm surprised how nasty it is, honestly. I'm hoping someone else can come along and find a better solution that reads better.

    Another thing to investigate would be DCGs, which can be helpful for doing these kinds of list processing tasks.