How to leave in the first list elements that have a even occurrences in the second list? (Prolog)

Question

I have example on haskell:

import Data.List
list1 = [-1, 2, 2, 3, 4, 5, 6, 7]
list2 = [-1, -1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

func = [x | x <- list1, elem x [y | y <- list2, even (length (elemIndices y list2))]]

Result is [-1, 2, 2, 4] (This is correct result and want Prolog code give me same result)

First, "elemIndices" get lists [-1, -1], ..., [2, 2], ..., [3, 3, 3], ..., ..., [4, 4, 4, 4], ..., then "length" give us length of list, then "even" tells us whether the length is even or odd and then "elem" check if elements x (list1) are in lists that we have collected.

So I have:

list1 = [-1, 2, 2, 3, 4, 5, 6, 7]
list2 = [-1, -1, 2, 2, 3, 3, 3, 4, 4, 4, 4]

And want result:

Result = [-1, 2, 2, 4]

Any ideas on this or suggestions how to resolve this problem?

Thanks.

Answer 1

The Haskell solution is wrong: 5, 6, and 7 each have 0 occurrences in the second list, and 0 is even, so they should occur in the solution.

As for a Prolog solution, you must keep in mind that Prolog is not an expression-based language, you cannot easily nest expressions the way you can do in Haskell. Instead you must decompose your program into elementary steps and put those parts together to a whole. This can be tedious, but among other things it allows you to cleanly tackle subproblems one by one and to test them.

So let's start with collecting occurrences of an element in a list:

% list_element_occurrences(List, Element, Occurrences).
% Occurrences is a list of occurrences of Element in List
list_element_occurrences([], _Element, []).
list_element_occurrences([Element|Elements], Element, [Element|Occurrences]) :-
    list_element_occurrences(Elements, Element, Occurrences).
list_element_occurrences([X|Elements], Element, Occurrences) :-
    dif(X, Element),
    list_element_occurrences(Elements, Element, Occurrences).

Does this do what we expect?

?- list_element_occurrences([-1, -1, 2, 2, 3, 3, 3, 4, 4, 4, 4], -1, Occurrences).
Occurrences = [-1, -1] ;
false.

?- list_element_occurrences([-1, -1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3, Occurrences).
Occurrences = [3, 3, 3] ;
false.

Looks OK, let's continue. What we're really interested in is not the list of occurrences but whether the number of occurrences is even or odd:

% list_element_even_occurrences(List, Element).
% Element occurs an even number of times in List.
list_element_even_occurrences(List, Element) :-
    list_element_occurrences(List, Element, Occurrences),
    length(Occurrences, NumberOfOccurrences),
    NumberOfOccurrences mod 2 =:= 0.

Tests:

?- list_even_occurrences([-1, -1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 3).
false.

?- list_even_occurrences([-1, -1, 2, 2, 3, 3, 3, 4, 4, 4, 4], 4).
true ;
false.

Good. Let's also do the dual:

% list_element_odd_occurrences(List, Element).
% Element occurs an odd number of times in List.
list_element_odd_occurrences(List, Element) :-
    list_element_occurrences(List, Element, Occurrences),
    length(Occurrences, NumberOfOccurrences),
    NumberOfOccurrences mod 2 =:= 1.

It's not really necessary to construct the intermediate list and then calculate its length; we could just count elements directly. You can do this simplification later if you wish. Prolog is different from Haskell in that Haskell doesn't actually allocate the entire list before calculating its length.

Anyway, now we just need to use these predicates to see which elements we should pick out of a list (I'm not happy about the naming here):

% list_list_even_occurrences(List, List2, EvenOccurrences).
% EvenOccurrences is the list of elements of List that occur in List2 an even
% number of times.
list_list_even_occurrences([], _List2, []).
list_list_even_occurrences([X|Xs], List2, [X|EvenOccurrences]) :-
    list_element_even_occurrences(List2, X),
    list_list_even_occurrences(Xs, List2, EvenOccurrences).
list_list_even_occurrences([X|Xs], List2, EvenOccurrences) :-
    list_element_odd_occurrences(List2, X),
    list_list_even_occurrences(Xs, List2, EvenOccurrences).

And this gives:

?- list_list_even_occurrences([-1, 2, 2, 3, 4, 5, 6, 7], [-1, -1, 2, 2, 3, 3, 3, 4, 4, 4, 4], EvenOccurrences).
EvenOccurrences = [-1, 2, 2, 4, 5, 6, 7] ;
false.

Now you could think about replacing the definition of list_list_even_occurrences/3 with a findall/3-based one, and possibly expanding the auxiliary predicates inline as well.