prolog - 如何重写以下内容以使其使用 if_？

Question

我正在做一些简单的exercises感受该语言。

is_list([]).
is_list([_|_]).

my_flatten([],[]).
my_flatten([X|Xs],RR) :-
   my_flatten(Xs,R),
   (is_list(X), !, append(X,R,RR); RR = [X | R]).

这是一个使用 cut 的版本，用于将列表展平一级的谓词。

my_flatten([],[]).
my_flatten([X|Xs],RR) :-
   my_flatten(Xs,R),
   if_(is_list(X), append(X,R,RR), RR = [X | R]).

我想这样写，但是不行。 is_list(X) = true 也不作为 if_ 条件。我打算如何在这里使用 if_ ？

Answer 1

(抱歉，我有点跳过了这一点)

• 请参阅P07 。它清楚地表明它会展平[a, [b, [c, d], e]]，但你和@Willem 产生:

    ?- my_flatten([a, [b, [c, d], e]], X).
       X = [a,b,[c,d],e].   % not flattened!

• 那里给出的解决方案成功了

    ?- my_flatten(non_list, X).
       X = [non_list].      % unexpected, nothing to flatten

• 对于 is_list([a|non_list])，您对 is_list/1 的定义成功。通常，我们希望此操作失败。

您需要的是一个安全谓词来测试列表。因此，让我们首先关注这一点:

is_list/1 和 if-then-else 有什么问题？它是非单调的，如 many other impure type testing predicates .

?- Xs = [], is_list([a|Xs]).
   Xs = [].
?- is_list([a|Xs]).     % generalization, Xs = [] removed
   false.                  % ?!? unexpected

虽然原始查询正确成功，但其泛化却意外失败。在 Prolog 的单调部分，我们期望泛化能够成功(或者循环、产生错误、耗尽所有资源，但永远不会失败)。

您现在有两种选择来改善这种非常不受欢迎的情况:

通过安全推理保持安全，_si!

只需采用 list_si/1 的定义即可代替 is_list/1。在有问题的情况下，您的程序现在将因实例化错误而中止，这意味着“很抱歉，我不知道如何回答这个查询”。为这个回应感到高兴!您不会被错误答案误导。

换句话说:( If_0 -> Then_0 ; Else_0 ) 没有任何问题，只要 If_0 正确处理实例化不足的情况(并且不这样做)不要引用用户定义的程序，否则您将再次处于非单调行为)。

这是这样一个定义:

my_flatten(Es, Fs) :-
   list_si(Es),
   phrase(flattenl(Es), Fs).

flattenl([]) --> [].
flattenl([E|Es]) -->
   ( {list_si(E)} -> flattenl(E) ;  [E] ),
   flattenl(Es).

?- my_flatten([a, [b, [c, d], e]], X).
   X = [a,b,c,d,e].

因此 ( If_0 -> Then_0 ; Else_0 ) 有两个弱点:条件 If_0 可能对实例化不足敏感，而 Else_0可能是非单调性的根源。但除此之外它是有效的。那么为什么我们想要更多呢？在许多更一般的情况下，这个定义现在会反击:“实例化错误”!虽然不正确，但这仍然可以改进。此练习不是理想的示例，但我们会尝试一下。

使用具体化条件

为了使用if_/3，您需要一个具体化条件，即一个将其真值作为显式额外参数的定义。我们将其命名为 list_t/2。

?- list_t([a,b,c], T).
   T = true.
?- list_t([a,b,c|non_list], T).
   T = false.
?- list_t(Any, T).
   Any = [],
   T = true
;  T = false,
   dif(Any,[]),
   when(nonvar(Any),Any\=[_|_])
;  Any = [_],
   T = true
;  Any = [_|_Any1],
   T = false,
   dif(_Any1,[]),
   when(nonvar(_Any1),_Any1\=[_|_])
;  ... .

所以list_t也可以用来枚举所有true和false情况。让我们来看看它们:

1. T = true, Any = [] 这是空列表
2. T = false, diff(Any, []), Any is not [_|_] 请注意这个不等式如何使用 when/2
3. T = true, Any = [_] 这是包含一个元素的所有列表
4. T = true, Any = [_|_Any1] ... 含义:我们从一个元素开始，但没有列表

list_t(Es, T) :-
   if_( Es = []
      , T = true
      , if_(nocons_t(Es), T = false, ( Es = [_|Fs], list_t(Fs, T) ) )
      ).

nocons_t(NC, T) :-
   (  NC \= [_|_] -> T = true
   ;  nonvar(NC) -> T = false
   ;  /* var(NC) -> */ freeze(NC, NC \= [_|_], T = true
   ;  NC = [_|_], T = false
   ).

最后，具体化定义:

:- meta_predicate( if_(1, 2, 2, ?,?) ).

my_flatten(Es, Fs) :-
   phrase(flattenl(Es), Fs).

flattenl([]) --> [].
flattenl([E|Es]) -->
   if_(list_t(E), flattenl(E), [E] ),
   flattenl(Es).

if_(C_1, Then__0, Else__0, Xs0,Xs) :-
   if_(C_1, phrase(Then__0, Xs0,Xs), phrase(Else__0, Xs0,Xs) ).

?- my_flatten([a|_], [e|_]).
   false.
?- my_flatten([e|_], [e|_]).
   true
;  true
;  true
;  ... .
?- my_flatten([a|Xs], [a]).
   Xs = []
;  Xs = [[]]
;  Xs = [[],[]]
;  ... .
?- my_flatten([X,a], [a]).
   X = []
;  X = [[]]
;  X = [[[]]]
;  X = [[[[]]]]
;  ... .
?- my_flatten(Xs, [a]).
   loops. % at least it does not fail