1

假设我们只查看 Peano 数字列表。让我们假设 pure_2 Prolog 不是带有 dif/2 的 pure_1 Prolog，而是带有带有 when/2 的 pure_1 Prolog。我们可以实现列表交集吗？

我们会退后一步，从编程语言 Gödel 和 Nu-Prolog 中汲取灵感。因此，对于任何需要的 if-then-else，我们将在此处使用此答案。会是什么：

/* pure_2 Prolog = pure_1 Prolog with when/2 */
intersect(A, B, C) :- ??

请注意，尽管如此，与 Gödel 和 Nu-Prolog 相反，为了在此问题中坚持 pure_2 Prolog，我们将不允许使用 ISO Prolog if-then-else ( -> ;_)。但是我们可以按照这里的要求使用分离关系。

一个测试用例将是坚定不移：

?- intersect([s(0)], [0], X).
X = []

?- intersect([X], [Y], Z), X = s(0), Y = 0.
X = []
4

2 回答 2

1

（从this和this获取代码）

less(0, s(_)).
less(s(X), s(Y)) :- less(X, Y).

neq(X, Y) :- less(X, Y); less(Y, X).

eq(0, 0).
eq(s(X), s(Y)) :- eq(X, Y).


horn_intersect([],_,[]).
horn_intersect(_,[],[]).

horn_intersect([X|Xs],List2,[X|Ms]) :- in(X,List2),horn_intersect(Xs,List2,Ms).
horn_intersect([X|Xs],List2,Ms)     :- not_in(X,List2),horn_intersect(Xs,List2,Ms).

in(X,[K|_]) :- eq(X, K).
in(X,[K|Ms]) :- neq(X, K),in(X,Ms).

not_in(_,[]).
not_in(X,[K|Ms]) :- neq(X, K),not_in(X,Ms).

测试：

?- horn_intersect([X], [Y], Z).
X = Y, Y = 0,
Z = [0] ;
X = Y, Y = s(0),
Z = [s(0)] ;
X = Y, Y = s(s(0)),
Z = [s(s(0))] ;
X = Y, Y = s(s(s(0))),
Z = [s(s(s(0)))] ;
X = Y, Y = s(s(s(s(0)))),
Z = [s(s(s(s(0))))] ;
X = Y, Y = s(s(s(s(s(0))))),
Z = [s(s(s(s(s(0)))))] ;
X = Y, Y = s(s(s(s(s(s(0)))))),
Z = [s(s(s(s(s(s(0))))))] ;
X = Y, Y = s(s(s(s(s(s(s(0))))))),
Z = [s(s(s(s(s(s(s(0)))))))] ;
X = Y, Y = s(s(s(s(s(s(s(s(0)))))))),
Z = [s(s(s(s(s(s(s(s(0))))))))] ;
X = Y, Y = s(s(s(s(s(s(s(s(s(0))))))))),
Z = [s(s(s(s(s(s(s(s(s(...)))))))))] ;
X = Y, Y = s(s(s(s(s(s(s(s(s(s(...)))))))))),
Z = [s(s(s(s(s(s(s(s(s(...)))))))))] .

?- horn_intersect(X, Y, Z).
X = Z, Z = [] ;
Y = Z, Z = [] ;
X = Z, Z = [0],
Y = [0|_2472] ;
X = Z, Z = [0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0, 0],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0, 0|...],
Y = [0|_2472] ;
X = Z, Z = [0, 0, 0, 0, 0, 0, 0, 0, 0|...],
Y = [0|_2472] .
于 2020-12-23T17:01:20.173 回答
-1

when/2 和 freeze/2 确实允许比 dif/2 更精细的控制。下面是一些使用 when/2 和 freeze/2 的代码，看起来很稳定，也很容易失败，并且没有为地面输入留下选择点：

/* reified and delayed equality */
eq(X, Y, R) :- when((nonvar(X), nonvar(Y)), eq2(X, Y, R)).
eq2(0, 0, 1).
eq2(0, s(_), 0).
eq2(s(_), 0, 0).
eq2(s(X), s(Y), R) :- eq(X, Y, R).

/* reified and delayed disjunction */
or(X, Y, R) :- when((nonvar(X), nonvar(Y)), or2(X, Y, R)).
or2(0, 0, 0).
or2(0, 1, 1).
or2(1, 0, 1).
or2(1, 1, 1).

/* reified and delayed membership */
member(_, [], 0).
member(X, [Y|Z], R) :-
   eq(X, Y, H),
   or(H, J, R),
   member(X, Z, J).

/* reified and delayed if-then-else */
ite(B, P, Q) :- freeze(B, ite2(B, P, Q)).
ite2(1, P, _) :- P.
ite2(0, _, Q) :- Q.

/* */
intersect([], _, []).
intersect([X|Y], Z, T) :-
   ite(B, T = [X|R], T = R),
   member(X, Z, B),
   intersect(Y, Z, R).

以下是一些测试稳定性的示例查询：

?- intersect([s(s(0))], [s(0)], X).
X = []

?- intersect([X], [Y], Z), X = s(s(0)), Y = s(0).
X = s(s(0)),
Y = s(0),
Z = []

下面是一个测试故障稳定性的示例查询：

?- intersect([s(_)], [0], X).
X = []

这是一个示例，显示了通过 when/2 延迟的内容：

?- intersect([X], [Y], Z).
freeze(_A, ite2(_A, Z = [X], Z = [])),
when((nonvar(X), nonvar(Y)), eq2(X, Y, _D)),
when(nonvar(_D), or2(_D, 0, _A))

以上是用 Jekejeke Prolog 1.4.6 测试的，需要导入库 library(term/suspend) 以使 when/2 可用。在 SWI-Prolog eq/3 中留下了一个选择点，但这与这里的问题相同。

于 2020-12-23T22:40:39.513 回答