3

在我之前对最近的问题“ Prolog二叉搜索树测试 - 不需要的父母的父节点比较”的回答中，我提出lazy_chain/2了使用混合......

:- use_module ( library(clpfd) )。

懒惰链（Zs，R_2）：-
   (   var (R_2) ->实例化_error (R_2)
   ; clpfd:chain_relation(R_2) ->冻结(Zs,lazy_chain_aux(Zs,R_2))
   ;  否则                 -> domain_error (chain_relation, R_2)
   ）。

懒惰链辅助（[]，_）。
懒惰链辅助（[Z0|Zs]，R_2）：-
   冻结（Zs，lazy_chain_aux_（Zs，R_2，Z0））。

惰性链_辅助_（[]，_，_）。
lazy_chain_aux_([Z1|Zs], R_2, Z0) :-
   调用（R_2，Z0，Z1），
   冻结（Zs，lazy_chain_aux_（Zs，R_2，Z1））。

...与 in_order//1 ...

in_order(nil) --> []。
in_order（节点（X，L，R））-> in_order（L），[X]，in_order（R）。

...像这样：

?-lazy_chain(Zs, #<),
   短语(in_order(node(1,nil,nil)), Zs)。
Zs = [1,23]。

有没有一种简单的方法可以“推动” ，lazy_chain使其phrase/3范围仅限于描述的序列部分in_order//1？

现在，我得到...

?-lazy_chain(Zs, #<),
   短语(in_order(node(1,nil,nil)), Zs0,Zs)。
Zs0 = [1|Zs]，冻结（Zs，lazy_chain_aux（Zs，#<））。

...（当然）在进一步实例化时可能会失败Zs：

?-lazy_chain(Zs, #<),
   短语（in_order（节点（1，nil，nil）），Zs0，Zs），
   Zs = [3,2,1]。
假的。

我该如何解决这个问题并限制lazy_chain到的一部分？

4

2 回答 2

1

与此同时，我想出了以下技巧：

lazy_chain_upto(R_2, P_2, Xs0, Xs) :-
   (  var(R_2)                  -> instantiation_error(R_2)
   ;  clpfd:chain_relation(R_2) -> when((nonvar(Xs0) ; ?=(Xs0,Xs)),
                                        lazy_chain_upto_aux(Xs0,Xs,R_2)),
                                   phrase(P_2, Xs0, Xs)
   ;  otherwise                 -> domain_error(chain_relation, R_2)
   ).

lazy_chain_upto_aux(Xs0, Xs, _) :-
   Xs0 == Xs,
   !.
lazy_chain_upto_aux([], _, _).
lazy_chain_upto_aux([X|Xs0], Xs, R_2) :-
   when((nonvar(Xs0) ; ?=(Xs0,Xs)), lazy_chain_upto_prev_aux(Xs0,Xs,R_2,X)).

lazy_chain_upto_prev_aux(Xs0, Xs, _, _) :-
   Xs0 == Xs,
   !.
lazy_chain_upto_prev_aux([], _, _, _).
lazy_chain_upto_prev_aux([B|Xs0], Xs, R_2, A) :-
   call(R_2, A, B),
   when((nonvar(Xs0) ; ?=(Xs0,Xs)), lazy_chain_upto_prev_aux(Xs0,Xs,R_2,B)).

基于此，我们可以这样定义in_orderX//1：

in_orderX(T) --> lazy_chain_upto(#<, in_order(T)).

问题中显示的示例查询...

?- phrase(in_orderX(node(1,nil,nil)), Zs0,Zs), Zs = [3,2,1].
Zs0 = [1,3,2,1], Zs = [3,2,1].

......现在检查好了，但我仍然想知道：值得吗？

于 2016-01-15T15:20:57.177 回答
0

我认为混合使用 corouting 和 DCG 没有任何问题。DCG 只是从 DCG 规则H --> B到一些普通 Prolog 规则的翻译H' :- B'。任何约束发布都可以包装到{}/1.

这是Quines的一个例子：

% eval(+Term, +List, -Term, +Integer)
eval([quote,X], _, X) --> [].
eval([cons,X,Y], E, [A|B]) -->
   step,
   eval(X, E, A),
   eval(Y, E, B).
eval([lambda,X,B], E, [closure,X,B,E]) --> [].
eval([X,Y], E, R) -->
   step,
   {neq(X, quote), sto(B)},
   eval(X, E, [closure,Z,B,F]),
   {sto(A)},
   eval(Y, E, A),
   eval(B, [Z-A|F], R).
eval(S, E, R) -->
   {freeze(S, is_symbol(S)), freeze(E, lookup(S, E, R))}.

你可以对lazy_chain_upto//2. 作为开始，您可以继续定义lazy_chain_upto//2 如下的第一个子句：

lazy_chain_upto(R_2, P_2) -->
   (  {var(R_2)}                  -> {instantiation_error(R_2)}
   ;  {clpfd:chain_relation(R_2)} -> /* ?? */
   ;  {otherwise}                 -> {domain_error(chain_relation, R_2)}
   )

在这一/* ?? */部分中，您也可以从 DCG 化的lazy_chain_upto_aux//1谓词中获利。当然，我假设 DCG 翻译理解 (->) 和 (;)/2。

再见

于 2016-02-28T20:26:42.390 回答