SWI-Prolog sort predicate not working

Question

I just made up a program, doing following task: "Get elements, which values are equal to their indexes".

Here is the code:

% get element's index
get_index([Element|_], Element, 0).
get_index([_|T], Element, Index) :-
    get_index(T, Element, Index1),
    Index is Index1+1.

index_equals_to_element(List, List2) :-
    member(X, List),
    get_index(List, X, Index),
    Index =:= X,
    append([], [X], List2).

It works pretty well. But there is one problem. For list [0, 3, 2, 4, 0] my predicate index_equals_to_element returns [0, 2, 0].

Okay, let it happen. But when I'm trying to output only unique elements, I'm getting the same list without any changes. Example:

?- index_equals_to_element([0, 3, 2, 4, 0], List).
% Outputs [0, 2, 0]

?- sort(List, List2).
% Outputs [0, 2, 0] either, when expected [0, 2]

It's very strange for me, because this works fine:

?- sort([0, 2, 1, 0], List).
% Outputs [0, 1, 2].

Why sort doesn't work only with the list, generated by my predicate?

Answer 1

A simple solution is:

index_equals_to_element(List1, List2) :-
    % assume that list position index starts at 0
    index_equals_to_element(List1, 0, List2).

index_equals_to_element([], _, []).
index_equals_to_element([X| Xs], Index, List2) :-
    NextIndex is Index + 1,
    (   X == Index ->
        List2 = [X| Tail],
        index_equals_to_element(Xs, NextIndex, Tail)
    ;   index_equals_to_element(Xs, NextIndex, List2)
    ).

Example call:

?-  index_equals_to_element([0, 3, 2, 4, 0], List).
List = [0, 2].

I suggest you study it by using the trace feature of your Prolog system by typing the query:

?-  trace, index_equals_to_element([0, 3, 2, 4, 0], List).

Step trough the execution until is the predicate definition is clear for you.

Answer 2

Your index_equals_to_element([0, 3, 2, 4, 0], List). doesn't output [0, 2, 0] as you claim, but gives three answers [0], [2] and [0]:

?- index_equals_to_element([0, 3, 2, 4, 0], List).
List = [0] ;
List = [2] ;
List = [0] ;
false.

You can use findall to get what you want:

?- findall(X, index_equals_to_element([0, 3, 2, 4, 0], [X]), List).
List = [0, 2, 0].

Update. Here is what I think a better implementation of index_equals_to_element/2:

index_equals_to_element(List, List2) :-
    index_equals_to_element(List, 0, List2).

index_equals_to_element([], _, []).
index_equals_to_element([X | Rest], I, Rest2) :-
    Inext is I + 1,
    index_equals_to_element(Rest, Inext, NewRest),
    ( X =:= I ->
        Rest2 = [X | NewRest]
    ; 
        Rest2 = NewRest
    ).

Test run:

?- index_equals_to_element([0, 3, 2, 4, 0], List).
List = [0, 2].

?- index_equals_to_element([0, 1, 2, 2, 4, 5], List).
List = [0, 1, 2, 4, 5].

Answer 3

The other answers are best for learning the nuts and bolts of Prolog. But here's a more concise (but also easier to grok) solution using the higher-order predicate findall/3 and nth0/3 from the SWI-Prolog library(lists):

elements_equal_to_index(List, Elements) :-
    findall(Index, nth0(Index, List, Index), Elements).

Edit:

As @Paulo Moura pointed out in a comment, the above answer is only equivalent to the others offered here if all argument are instantiated. I.e., if the above encounters a free variable in the list, I will bind that variable to its index in the list instead of rejecting it as an unsatisfactory element. The addition of a test for strong equality between the index and the list element should make the answer conform:

elements_equal_to_index(List, Elements) :-
    findall( Index,
             ( nth0(Index, List, Elem),
               Elem == Index ),
             Elements
           ).