如何保留在第二个列表中出现偶数的第一个列表元素?(序言) [英] How to leave in the first list elements that have a even occurrences in the second list? (Prolog)

问题描述

我有关于haskell的例子:

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))]]

结果是 [-1, 2, 2, 4] (这是正确的结果，希望 Prolog 代码给我相同的结果)

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

首先，elemIndices"得到列表[-1, -1], ..., [2, 2], ..., [3, 3, 3], ..., ..., [4, 4, 4, 4], ..., 然后length"给我们列表的长度，然后even"告诉我们长度是偶数还是奇数，然后elem"检查是否有元素x (list1) 在我们收集的列表中.

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.

所以我有:

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]

对此有任何想法或建议如何解决此问题?

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

谢谢.

推荐答案

Haskell 的解决方案是错误的:5、6 和 7每个在第二个列表中都有 0 次出现，0 是偶数，所以它们应该出现在解决方案中.

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.

对于 Prolog 解决方案，您必须记住 Prolog 不是基于表达式的语言，您无法像在 Haskell 中那样轻松地嵌套表达式.相反，您必须将您的程序分解为基本步骤，并将这些部分组合成一个整体.这可能很乏味，但除此之外，它还能让您干净利落地解决子问题并对其进行测试.

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.

测试:

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

其实没有必要先构造中间列表然后计算它的长度；我们可以直接计算元素.如果您愿意，您可以稍后进行此简化.Prolog 与 Haskell 的不同之处在于 Haskell 在计算其长度之前实际上并没有分配整个列表.

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

这给出了:

?- 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 的定义，并可能扩展辅助谓词也内联.

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.

这篇关于如何保留在第二个列表中出现偶数的第一个列表元素?(序言)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！