序言中的尾递归程序，在列表中输出奇数

Question

我在 Prolog 中编写了一个尾递归谓词，它在列表 K 中输出 A 和 B 之间的整数。我已经使用 "reverse" 将数字按正确的顺序排列：

numbers(A,B,K) :- numbers(A,B,[],K).
numbers(Y,Y,X,K) :- !, reverse([Y|X],K).
numbers(A,B,X,K) :- A<B, C is A+1, numbers(C,B,[A|X],K).

查询：

?- numbers(3,6, K).
   K=[3,4,5,6]

一切正常。我现在想做的是，我只想在列表 K 中包含 A 和 B 范围内的奇数。我怎样才能做到这一点？提前致谢！

Answer 1

这可能是一个解决方案，使用 mod/2 运算符。

numbers(A,B,K) :- 
    B1 is B+1,
    numbers(A,B1,[],K).
numbers(Y,Y1,X,K) :- 
    Y = Y1,
    reverse(X,K).
numbers(A,B,X,K) :- 
    A<B, 
    C is A+1,
    C1 is mod(C,2),
    (C1 = 0 ->  
        numbers(C,B,[A|X],K)
    ; numbers(C,B,X,K)).

Answer 2

首先，我会尽量避免使用reverse/2。如果您有这样的解决方案，通常表明有更好的方法可以更直接地转发答案。不总是，但最经常。 reverse/2 可能是 Prolog 中仅次于使用剪切的第二受欢迎的创可贴。 :)

在很多问题中，都需要辅助累加器。在这种特殊情况下，事实并非如此。此外，我倾向于在涉及整数时使用 CLP(FD) 操作，因为它是对整数进行推理的更相关的方法。但如果您愿意，可以将下面的解决方案与 is/2 等一起使用。只是不会那么一般。

numbers(S, E, []) :- S #> E.   % null case
numbers(X, X, [X]).
numbers(S, E, [S|T]) :-
    S #< E,
    S1 #= S + 1,
    numbers(S1, E, T).

| ?- numbers(3, 8, L).

L = [3,4,5,6,7,8] ? ;

no
| ?- numbers(A, B, [2,3,4,5]).

A = 2
B = 5 ? ;

no
| ?-

这个解决方案避免了reverse/2并且是尾递归的。

要为奇数更新它，第一个想法是我们可以很容易地修改上面的代码，只需添加 2 而不是 1 就可以每隔一个数字进行更新：

every_other_number(S, E, []) :- S #> E.
every_other_number(X, X, [X]).
every_other_number(S, E, [S|T]) :-
    S #< E,
    S1 #= S + 2,
    every_other_number(S1, E, T).

| ?- every_other_number(3, 7, L).

L = [3,5,7] ? ;

no
| ?- every_other_number(3, 8, L).

L = [3,5,7] ? ;

no
| ?- every_other_number(4, 8, L).

L = [4,6,8] ? ;

no
| ?-

然后我们可以通过创建一个初始谓词来确保第一个值是奇数的条件并调用every_other_number/3:

来做奇数

odd_numbers(S, E, L) :-
    S rem 2 #= 1,
    every_other_number(S, E, L).
odd_numbers(S, E, L) :-
    S rem 2 #= 0,
    S1 #= S + 1,
    every_other_number(S1, E, L).

| ?- odd_numbers(2, 8, L).

L = [3,5,7] ? ;

no
| ?- odd_numbers(2, 9, L).

L = [3,5,7,9] ? ;

no
| ?- odd_numbers(3, 8, L).

L = [3,5,7] ? ;

no
| ?-

Answer 3

另一种可能是使用 DCG :

numbers(A,B,K) :-
    phrase(odd(A,B), K).

odd(A,B) --> {A > B, !}, [].

odd(A,B) --> {A mod2 =:= 0, !, C is A+1}, odd(C,B).
odd(A,B) --> {C is A+2}, [A], odd(C, B).

序言中的尾递归程序，在列表中输出奇数

Tail-recursive program in prolog which outputs odd numbers in a list

prolog

tail-recursion