如何使用Prolog从列表中删除偶数

Question

如何使用Prolog从列表中删除偶数

3

我需要从第一个列表中删除所有的偶数并将剩余部分保存到第二个列表中。我的第一种不起作用的尝试是:

remove_even([],[]).
remove_even([H1|T1],[H2|T2]):- 
    H1 mod 2 =:= 0,
    remove_even(T1,_).
remove_even([H1|T1],[H2|T2]):-
    remove_even(T1,T2).

以下是在SWI-Prolog 7.1.37中运行的示例查询：

?- remove_even([1,2,3,4],NewList).
NewList = [_G252, _G255|_G256].     % BAD! expected: NewList = [1,3]

我的代码出了什么问题？

更新：下一次尝试，它没有起作用，因为remove_even一旦检查到它是有效的偶数，就会返回false并转到另一个规则，在那里递归发生...

remove_even([],[]).
remove_even([El|T],[T]):- El mod 2 =:= 0.
remove_even([H1|T1],[H2|T2]):-
    remove_even(T1,T1).

更新2: 在逻辑上迷失了：

remove_even([],[]).
remove_even([El|T],T):-El mod 2 =:= 0. % removing the head if head is even
remove_even([H|T1], [H|T2]) :-         % case where head is odd
    H mod 2 =\= 0,                     % rules that ensure head is odd
    remove_even(T1, T1). 

    % just copying T1 from source list to destination, 
    % will look up T1 values in next recursive iteration when it becomes a H.

更新3：按照建议进行了操作，但仍然无法正常工作。

remove_even([],[]).
remove_even([El|T], NewT)   :- El mod 2 =:= 0, remove_even(T, NewT).
remove_even([H|T1], [H|T2]) :- H  mod 2 =\= 0, remove_even(T1, T1).

更新4：无单例错误

remove_even([],[]).
remove_even([El|T], NewT)  :- El mod 2 =:= 0, remove_even(T, NewT).
remove_even([El|T1], NewT) :- El mod 2 =\= 0, remove_even(T1,[NewT|T1]).

更新5: 已经使其正常工作，但几乎不知道如何做到这一点（可能是一些魔法;)）。gtrace 很好，但有一个Prolog可以绘制某种决策树或易于理解的图形表示它的步骤会更有用。

remove_even([],[]).
remove_even([El|T], NewT)   :- El mod 2 =:= 0, remove_even(T, NewT).
remove_even([H|T1], [H|T2]) :- H  mod 2 =\= 0, remove_even(T1, T2).

如何在考虑递归调用的情况下解释逻辑上的最后一个子句？我的尝试：[H|T2] 是从 [H|T1] 中删除偶数元素后得到的列表当且仅当两个列表的头部都是奇数，并且目标列表的尾部 T2 是一个 T1 的尾部，其中所有偶数元素已被删除。正确吗？

- J.Olufsen

在你的第二个从句中，H2 和 T2 是单例，这意味着你没有在规则中指明它们来自哪里。在第三个从句中，H1 和 H2 都是单例，因此在这种情况下你也没有完成规则中的逻辑。 - lurker

1

在你的更新中，第二个子句 T（一个尾部）已经是一个列表。所以你不需要 [T] 而只需要 T。在你的第三个子句中，H1 和 H2 仍然是单例，现在 T2 也是。 - lurker

1

在你的第二次更新中，第二个条款将允许T具有偶数元素。换句话说，它表示*如果E1是偶数，则从列表[E1|T]中删除偶数元素后得到的结果是T*。换句话说，如果第一个元素是偶数，则删除它并宣布胜利。除了将其包含在结果中之外，它不指示如何处理T。我认为你的第三个条款看起来很好。 - lurker

1

这就是Prolog的工作方式。如果在呈现解决方案时，Prolog逻辑中存在选择点，则按下“;”并将寻找其他解决方案。当它找不到更多解决方案时，它会显示“false”或“no”（没有更多解决方案）。关于不知道程序如何工作，如果您按照我在答案中描述的方式进行思考，那么它应该是合乎逻辑的。例如，您的最后一个子句说，如果H是奇数，并且T2是从T1中删除偶数元素时得到的列表，则去除偶数元素后的偶数元素已被删除，即[H|T1]与[H|T2]相同。这难道不是合乎逻辑的吗？ :) - lurker

1

在您对第3条款的最后解释中，您说，“…当且仅当两个列表的头都是奇数时…”但这并不完全正确。该条款对于两个列表都使用H表示头部，因此这些头部不仅是奇数，而且是相同的（它们具有相同的值），这很重要，因为我们希望第二个列表与第一个列表具有相同的值，只是没有偶数值。 - lurker

显示剩余4条评论

5个回答

2

如果您的Prolog系统提供clpfd，那么这个答案就是为您准备的。（如果没有，请继续阅读！）

通过使用元谓语 tfilter/3和重言谓词 zodd_t/2，只需编写：

?- tfilter(zodd_t,[1,2,3,4],Zs). % remove even integers = keep odd integers
Zs = [1,3].

由于我们在这里仅使用单调代码，因此我们也可以获得更一般的查询的正确答案：

将上述内容翻译为中文：

?- tfilter(zodd_t,[A,B,C],Zs)。

当满足以下条件时，Zs分别为：

Zs = [ ]，A mod 2 #= 0, B mod 2 #= 0, C mod 2 #= 0； Zs = [ C]，A mod 2 #= 0, B mod 2 #= 0, C mod 2 #= 1； Zs = [ B ]，A mod 2 #= 0, B mod 2 #= 1, C mod 2 #= 0； Zs = [ B,C]，A mod 2 #= 0, B mod 2 #= 1, C mod 2 #= 1； Zs = [A ]，A mod 2 #= 1, B mod 2 #= 0, C mod 2 #= 0； Zs = [A, C]，A mod 2 #= 1, B mod 2 #= 0, C mod 2 #= 1； Zs = [A,B ]，A mod 2 #= 1, B mod 2 #= 1, C mod 2 #= 0； Zs = [A,B,C]，A mod 2 #= 1, B mod 2 #= 1, C mod 2 #= 1。

我们甚至可以不使用clpfd，而是使用不同的谓词来使用上述代码： eveninteger_t/2 → zeven_t/2，以及 oddinteger_t/2 → zodd_t/2。

示例查询：

？- tfilter(oddinteger_t,[1,2,3,4,5,6,7],Xs)。
Xs = [1,3,5,7]。

编辑于2015年06月06日

让我们尝试以下变化！

不要直接使用zodd_t/2，而是使用zeven_t/2和not_t/3：

truth_negated(true,false).
truth_negated(false,true).

not_t(Goal,Param,Truth1) :-       % meta-predicate, negate truth value
   call(Goal,Param,Truth0),
   truth_negated(Truth0,Truth1).

让我们通过一次头对头的比较来看看它是否有效：

？- tfilter（      zodd_t  ，[1,2,3,4]，Zs）。
Zs = [1,3]。
？- tfilter（not_t(zeven_t)，[1,2,3,4]，Zs）。
Zs = [1,3]。

- repeat

“_t”代表真值。在Prolog中，t和f不是常见的值，它们被Scheme称为“#t”。相反，使用“true”和“false”。下划线“_t”对应于前缀“t”。 - false

1

让我们看看你的一个从句：

remove_even([El|T],[T]) :- El mod 2 =:= 0.

首先，在符号[El|T]中，El是单个项，而T是一个列表。然后[T]将成为一个列表内部的列表，这可能不是您想要的。它应该只是“remove_even([El|T], T)”。

接下来，您规则的变体只是将T复制到答案中，而不是从尾部删除任何偶数。只有第一个数字（如果它是偶数）将被删除。remove_even也应用于T。

最后，我们应该得到像这样的结果：

remove_even([El|T], NewT) :- 
    El mod 2 =:= 0,
    remove_even(T, NewT).

- Sergii Dymchenko

你上次提出的“remove_even”规则单独使用并不起作用，会返回“False”。 - J.Olufsen

这只是其中一个子句。必须添加空列表的子句和第一个元素不是偶数的子句。 - Sergii Dymchenko

2

@RCola，Sergey已经给出了第二个子句的样式。您仍需要根据我的答案重新制定第一个子句和第三个子句。 - lurker

1

一种方便的内置库是 exclude。

1 ?- [user].
|: even(N) :- N mod 2 =:= 0.
% user://1 compiled 0.02 sec, 2 clauses
true.

2 ?- exclude(even, [1,2,3,4], L).
L = [1, 3].

- CapelliC

0

我的意思是，也许我读错了，但你们不觉得你们过度思考这个问题了吗？所以，将第一个列表中的所有偶数元素删除并将它们存储在第二个列表中，我只需跳过每个偶数元素即可完成：

remove_evens([], Ys).
remove_evens([X], [X|Ys]).
remove_evens([X,_|Xs], [X|Ys]):-
  remove_evens(Xs, Ys), !.

这将导致以下结果：

| ?- remove_evens([1,2,3,4,5,6,7], List2).
List2 = [1,3,5,7|_]

- Michael

1

这种剪裁加上错误的第一和第二个子句会导致许多奇怪的错误，例如：remove_evens([a,_,b,_,c],[a,b,c]) 可以正确地执行，但是 remove_evens([],[a,b,c]) 也会成功。 - false

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- lurker · Accepted Answer

你收到单例变量警告是一个暗示，说明某些地方不对。你的从句头表明你关心一个特定的变量，但从句逻辑并没有实例化它或以其他方式使用它。

分析你提供的规则（从句）。

remove_even([],[]).

好的规则。一个移除了偶数的空列表仍然是一个空列表。

remove_even([H1|T1],[H2|T2]):- 
    H1 mod 2 =:= 0,
    remove_even(T1,_).

这条规则说明：[H2|T2] 是列表 [H1|T1] 去除偶数后得到的列表，如果 H1 是偶数，那么还要去除 T1 中的偶数并将它们丢弃。这听起来不对劲。此外，这条规则也没有说明如何得到 H2。注意：如果逻辑不要求，您可能不想将结果列表在此子句中拆分为头和尾。
remove_even([H1|T1],[H2|T2]):- remove_even(T1,T2).

这条规则说如果 T2 与去除偶数后的 T1 相同，那么 [H2|T2] 就是去除偶数后的 [H1|T1]。听起来部分正确，但这个规则没有说明如何处理 H1 和 H2。 更新：在您的更新中，新的第二个子句为：
remove_even([El|T],[T]):- El mod 2 =:= 0.

这更接近了。一个问题是 T 已经是一个列表，所以你不需要 [T] 而只需要 T。那么它就变成了：
remove_even([E1|T], T) :- E1 mod 2 =:= 0.

这段文字的意思是：“它说：如果E1是偶数，那么删除偶数元素后的列表[E1|T]就是列表T。这是一个正确的陈述，但不完整。它没有对T做任何规定。如果列表T有偶数元素怎么办？请参见@Sergey的答案，以获得这个特定条款的更正版本。

你更新的第三条条款有一些新问题：

remove_even([H1|T1],[H2|T2]):- remove_even(T1,T1).

有三个单例变量。规则说，如果 T1 是没有偶数元素的（即 T1 没有偶数元素），那么从 [H1|T1] 中移除偶数元素得到 [H2|T2]。这听起来根本不合逻辑。因此，您需要重新考虑那个规则。我假设您打算处理头为奇数的情况（因为第二条子句处理的是偶数头）。在这种情况下，您只需将头复制到结果列表中即可。因此，您的子句标题应该如下所示：

remove_even([H|T1], [H|T2]) :- % case where head is odd % put rules here that ensure head is odd, and define how T1 and T2 are related

所以最终您将有3个子句：（1）从空列表中删除偶数元素，（2）从头部为偶数的列表中删除偶数元素，以及（3）从头部为奇数的列表中删除偶数元素。这听起来很完整。只需按照逻辑操作即可。
更新4回复：
新的第三个子句通过引入一些问题来消除单例。
remove_even([El|T1], NewT):- El mod 2 =\= 0, remove_even(T1, [NewT|T1]).

阅读如下：[E1|T1] 中删除偶数元素得到的列表为 NewT，如果 E1 是奇数且 [NewT|T1] 是从 T1 中删除偶数元素后的列表。一个重要问题是，你将 NewT（一个列表）作为另一个列表 [NewT|T1] 的头部使用，因此它现在是一个列表的列表，不会匹配任何内容。请参见上面第 3 条提示。此外，规则中不再有一个部分说 E1 是 NewT 的一部分。如果 E1 是奇数，则应将其作为另一个列表的一部分，在删除偶数元素时。

UPDATE5 回应（为什么它现在有效？）：

所以最终有效版本看起来像这样：

remove_even([],[]).

与以前一样：如果你从一个空列表中删除偶数元素，那么你会得到一个空列表。
remove_even([El|T], NewT):- El mod 2 =:= 0, remove_even(T, NewT).

“NewT”是列表“[E1|T]”，如果“E1”是偶数，则删除偶数元素后剩下的列表为“T”。如果“E1”是奇数，则“NewT”等于从“T”中删除偶数元素后得到的列表。“NewT”实际上就是原始列表的“尾部列表”“T”去除了偶数元素后的结果。换句话说，我们舍弃了“E1”（第一个列表的头部偶数元素），并得到了“T”，即我们想要“处理”的列表，并找到类似于“T”的列表，但删除了偶数元素。
remove_even([H|T1], [H|T2]):- H mod 2 =\= 0, remove_even(T1, T2).

我们之前已经讨论过这个问题，但为了完整起见：如果H不是偶数且T1中的偶数元素被删除，则[H|T1]中的偶数元素被删除后为[H|T2]，其中T1中的偶数元素被删除后为T2。你对这个子句的描述是：[H|T2]是从[H|T1]中删除偶数元素得到的列表，当且仅当两个列表的头部都是奇数且目标列表的尾部T2是一个在T1中删除所有偶数元素后的尾部。 这并不完全准确。你说，“...当且仅当两个列表的头部都是奇数...”，而在子句中，我们说头部是相同的和奇数（是相同的数字），而不仅仅是奇数。我在之前的回答中进一步描述了所有情况。如果你仔细思考一下，就会明白它的道理。 :)