Как оставить в первом списке элементы, которые имеют четные вхождения во втором списке? (Пролог)

Question

У меня есть пример на 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))]]

Результат равен [-1, 2, 2, 4] (Это правильный результат, и код Prolog дает мне тот же результат)

Во-первых, "elemIndices" получают списки[-1, -1], ..., [2, 2], ..., [3, 3, 3], ..., ..., [4, 4, 4, 4], ..., затем «length» дает нам длину списка, затем «even» сообщает нам, является ли длина четной или нечетной, и затем «elem» проверяет, есть ли элементы x (list1) в списках, которые мы собрали.

Итак, у меня есть:

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

И нужен результат:

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

Любые идеи на этот счет или предложения, как решить эту проблему?

Спасибо.

Answer 1

Решение Haskell неверно: 5, 6 и 7 каждый имеет 0 вхождений во втором списке, а 0 - четное, поэтому они должны встречаться в решении.

Что касается решения Prolog, вы должны иметь в виду, что Prolog не является языком, основанным на выражениях, вы не можете легко вкладывать выражения, как в Haskell. Вместо этого вы должны разбить вашу программу на элементарные шаги и соединить эти части в одно целое. Это может быть утомительно, но, помимо прочего, позволяет вам поочередно решать подзадачи и тестировать их.

Итак, начнем с сбора вхождений элемента в списке:

% 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).

Делает ли это то, что мы ожидаем?

?- 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.

Выглядит хорошо, давайте продолжим. Что нас действительно интересует, так это не список вхождений, а то, является ли количество вхождений четным или нечетным:

% 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.

Тесты:

?- 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.

Хорошо. Давайте также сделаем двойное:

% 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.

Нет необходимости создавать промежуточный список и затем вычислять его длину; мы могли бы просто посчитать элементы напрямую. Вы можете сделать это упрощение позже, если хотите. Пролог отличается от Haskell тем, что Haskell фактически не выделяет весь список перед вычислением его длины.

В любом случае, теперь нам просто нужно использовать эти предикаты, чтобы увидеть, какие элементы мы должны выбрать из списка (я не рад названию здесь):

% 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).

И это дает:

?- 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.

Теперь вы можете подумать о замене определения list_list_even_occurrences/3 на findall/3 и, возможно, расширении вспомогательных предикатов в строке.

Answer 2

Проблема здесь в том, что вы делаете проверку, которая выглядит следующим образом:

length(Zs0, <b>N</b>)

Это означает, что вы указываете, что количество элементов должно быть равно до N,даже не по сути.Мне не очень понятно, почему вы все равно используете параметр N, так как в примере с Haskell вы просто проверяете, имеет ли список четную длину.

Возможно, почти буквальный перевод программы на Haskellчто-то вроде:

p(Xs, Ys, Zs) :-
    findall(
        Y,
        (
            member(Y, Ys),
            findall(Y, member(Y, Ys), Ts),
            length(Ts, NT),
            <b>0 is NT mod 2</b>
        ),
        Ts
    ),
    list_to_set(Ts, STs),
    findall(X, (member(X, Xs), member(X, STs)), Zs).

При этом, как уже отмечалось @IsabelleNewbie, ваша функция Haskell не дает список элементов в xs, которые встречаются четное число раз вys, это дает элементы, которые встречаются хотя бы один раз и четное число раз в ys.Мы можем обновить функцию до:

func = filter (even . length . flip filter list2 . (==)) list1

и эквивалентный предикат Пролога будет:

p(Xs, Ys, Zs) :-
    findall(
        X,
        (
            member(Y, Ys),
            findall(Y, member(Y, Ys), Ts),
            length(Ts, NT),
            0 is NT mod 2
        ),
        Zs
    ).