Search code examples
listprologfailure-slice

Removing duplicates in prolog

I'm fairly new to prolog and I'm currently reading through a book which is giving me practice examples to code. It has tasked me with removing duplicates.

Note: I have read other stackoverflows, and I understand how to remove duplicates but what I don't understand is why my code isn't working. ( I have chose a different approach to other stackoverflows)

I've created a is_member predicate which I believe works fine.

is_member(X, [Head,Tail]):-
    X == Head;
    is_member(X, Tail).

And then my remove_duplicates predicate

remove_duplicates([Head|Tail], Without):-
    is_member(Head, Tail),
    remove_duplicates(Tail, Without);
    remove_duplicates(Tail, Head).

In my head this makes sense, it checks if the Head is a member of the tail and if it is, it doesn't add it to the Without list,

else it does.

I'm obviously missing something trivial here,

Thanks in advance

Solution

  • Let's simplify the task a bit by first considering is_member/2.

    You write it as:

    is_member(X, [Head,Tail]):-
    X == Head;
    is_member(X, Tail).

    Consider how easy it is to misread this as:

    is_member(X, [Head,Tail]):-
    X == Head,
    is_member(X, Tail).

    Exercise: What did I change?

    For this reason, I recommend a layout like the following:

    is_member(X, [Head,Tail]):-
        (   X == Head
        ;   is_member(X, Tail)
        ).

    Now, on to a few test cases!

    First, it is always a good idea to post the most general query. This simply asks: Are there any solutions at all?

    ?- is_member(E, Ls).
nontermination

    That's not a good sign!

    So, let us try a few concrete cases. For example, is a a member of the empty list?

    ?- is_member(a, []).
false.

    That's good! It is what we expected.

    Then, is a a member of the list [a]?

    ?- is_member(a, [a]).
false.

    That's definitely wrong!

    I recommend you start from there, and then move on to more complex definitions. Approach it in a systematic way:

    1. Write down what ought to hold.
    2. Try the most general query to see if you can obtain answers from your program.
    3. Try concrete test cases.
    4. Think about what the predicate actually means: You can use a predicate in multiple directions, and in many of these cases, the way you described the predicate does not make sense. For example, both the list and the element can already be given, and in that case there is nothing to "add" or "remove".

    To locate causes of unexpected failure in your program, use , for example by using the following definition to generalize away goals:

    :- op(950,fy, *).
*_.

    You can now write:

    is_member(X, [Head,Tail]):-
        (   * X == Head
        ;   * is_member(X, Tail)
        ).

    which is a massive generalization of your original program, and in fact declaratively equivalent to:

    is_member(X, [Head,Tail]) :- true.

    The test case above still fails with this fragment, which shows that the program is still too specific:

    ?- is_member(a, [a]).
false.