syntax - 为 prolog/haskell 编程考试而学习

Question

我开始为即将到来的考试学习，但我被困在一个琐碎的序言练习题上，这不是一个好兆头哈哈。

这应该很容易，但由于某种原因，我现在无法弄清楚。

任务是简单地计算序言中 Int 列表中奇数的数量。我在haskell中很容易做到，但我的序言很糟糕。有人可以告诉我一个简单的方法来做到这一点，并简要解释你做了什么？

到目前为止，我有：

odd(X):- 1 is X mod 2.

countOdds([],0).
countOdds(X|Xs],Y):-
?????

Answer 1

你对奇数/1的定义很好。

空列表的事实也很好。

在递归子句中，您需要区分奇数和偶数。如果数字是奇数，则应增加计数器：

countOdds([X|Xs],Y1) :- odd(X), countOdds(Xs,Y), Y1 is Y+1.

如果数字不是奇数（=偶数），则不应增加计数器。

countOdds([X|Xs],Y) :- \+ odd(X), countOdds(Xs,Y).

其中\+表示否定为失败。

或者，您可以使用 ! 在第一个递归子句中并删除第二个中的条件：

countOdds([X|Xs],Y1) :- odd(X), !, countOdds(Xs,Y), Y1 is Y+1.

countOdds([X|Xs],Y) :- countOdds(Xs,Y).

Answer 2

在 Prolog 中，您使用递归来检查递归数据结构的元素，就像列表一样。模式匹配允许选择正确的规则来应用。完成任务的简单方法：

您有一个列表 = [X|Xs]，对于每个元素 X，如果是奇数 (X)，则返回 countOdds(Xs)+1，否则返回 countOdds(Xs)。

countOdds([], 0).
countOdds([X|Xs], C) :-
  odd(X),
  !, % this cut is required, as rightly evidenced by Alexander Serebrenik
  countOdds(Xs, Cs),
  C is Cs + 1.
countOdds([_|Xs], Cs) :-
  countOdds(Xs, Cs).

注意if, 是用不同的规则和same模式处理的：当 Prolog 找到一个非奇数元素时，它会回溯到最后一条规则。

ISO Prolog 有语法糖If Then Else，你可以用它写

countOdds([], 0).
countOdds([X|Xs], C) :-
  countOdds(Xs, Cs),
  (  odd(X)
  -> C is Cs + 1
  ;  C is Cs
  ).

在第一个版本中，递归调用在 testodd(X)之后，以避免在回溯时重复对 list'tail 的无用访问。

edit Without the cut, we get multiple execution path, and so possibly incorrect results under 'all solution' predicates (findall, setof, etc...)

This last version put in evidence that the procedure isn't tail recursive. To get a tail recursive procedure add an accumulator:

countOdds(L, C) :- countOdds(L, 0, C).

countOdds([], A, A).
countOdds([X|Xs], A, Cs) :-
  (  odd(X)
  -> A1 is A + 1
  ;  A1 is A
  ),
  countOdds(Xs, A1, Cs).