Prolog 中的屏蔽

Question

我最近一直在努力弄清楚 Prolog，并且一直在搞乱 Prolog 中的列表列表。我正在尝试创建一种我认为在 p 中的掩码序言。我有一个谓词可以确定 Prolog 中两个列表列表（假设是 L1 和 L2）之间的差异，并将它们保存为列表列表（假设是 R）。我有另一个谓词，它简单地说明差值是否等于零 (noDifference)。我希望有两个基于 L1 和 L2 与 R 相比的结果列表列表（M1 和 M2）。例如，如果负值位于某个位置，我想将 L1 和 L2 的所有值与 R 进行比较R的值，然后将L1相同位置的值保存到M1中。如果正值位于 R 的位置，则如果有意义，则将 L2 相同位置的值保存到 M2 中。在所有这一切之前，我检查我的 noDifference 函数以查看差异是否为 0，如果是，则 M1 和 M2 的列表列表的所有值都将为 0。

这就是我目前的情况（我不确定我是否开始做对了）

masker(L1,L2,R,M1,M2):- noDifference(R1), M1=R, M2=R1;

其余部分是一些示例值在幕后应该是什么样子

L1=[[1,5,3,8],[1,5,3,8]]
L2=[[5,4,7,4],[5,4,7,4]]
R=[[4,-1,4,-4],[4,-1,4,-4]]
M1=[[0,5,0,8],[0,5,0,8]]Neg values of L1 at R are stored rest are 0)
M2=[[5,0,7,0],[5,0,7,0]](Pos values of L2 at R are stored rest are 0)

如果我到目前为止所做的事情是正确的，以及如何正确制定 subgoals/where 我接下来应该去的任何见解，那就太棒了！

用 ex 谓词编辑

?- masker([[1,5,3,8],[1,5,3,8]],
          [[5,4,7,4],[5,4,7,4]],
          [[4,-1,4,-4],[4,-1,4,-4]], M1, M2).
M1=[[0,5,0,8],[0,5,0,8]].
M2=[[5,0,7,0],[5,0,7,0]].

Answer 1

想想你的谓词应该描述什么。根据您提供的示例，它是五个列表列表之间的关系，它们的长度相同。这表明具有五个空列表的基本情况。否则所有五个列表的头部都是列表本身，彼此之间具有特定的关系，我们称之为 lists_mask_mlists/5。当然尾部也应该如此，可以通过递归目标来实现。所以你的谓词 masker/5 可能看起来像这样：

masker([],[],[],[],[]).
masker([X|Xs],[Y|Ys],[M|Ms],[R1|R1s],[R2|R2s]) :-
   lists_mask_mlists(X,Y,M,R1,R2),
   masker(Xs,Ys,Ms,R1s,R2s).

实际的屏蔽关系也有一个包含五个空列表的基本情况。否则还有两种情况：

1）当前掩码元素（第三个列表的头部）为负数：第一个列表的头部为第四个列表的头部，第五个列表的头部为0

2) 当前掩码元素为正：第二个列表的头部为第五个列表的头部，第四个列表的头部为0

你可以这样表达：

lists_mask_mlists([],[],[],[],[]).
lists_mask_mlists([X|Xs],[_Y|Ys],[M|Ms],[X|R1s],[0|R2s]) :-   % 1)
   M < 0,
   lists_mask_mlists(Xs,Ys,Ms,R1s,R2s).
lists_mask_mlists([_X|Xs],[Y|Ys],[M|Ms],[0|R1s],[Y|R2s]) :-   % 2)
   M >= 0,
   lists_mask_mlists(Xs,Ys,Ms,R1s,R2s).

使用此谓词，您的示例查询会产生所需的结果：

   ?- masker([[1,5,3,8],[1,5,3,8]],[[5,4,7,4],[5,4,7,4]],[[4,-1,4,-4],[4,-1,4,-4]],M1,M2).
M1 = [[0,5,0,8],[0,5,0,8]],
M2 = [[5,0,7,0],[5,0,7,0]] ? ;
no

但是请注意，由于 < 和 >= 这仅适用于第三个列表是可变的。用变量替换第三个参数中的第一个 4 会产生实例化错误：

   ?- masker([[1,5,3,8],[1,5,3,8]],[[5,4,7,4],[5,4,7,4]],[[X,-1,4,-4],[4,-1,4,-4]],M1,M2).
     ERROR at  clause 2 of user:masked/5 !!
     INSTANTIATION ERROR- =:=/2: expected bound value

如果您打算使用带有非自由变量的第三个参数的谓词，您可能会考虑使用 clpfd。包括行

:-use_module(library(clpfd)).

在您的源文件中并像这样更改 lists_mask_mlists/5：

lists_mask_mlists([],[],[],[],[]).
lists_mask_mlists([X|Xs],[_Y|Ys],[M|Ms],[X|R1s],[0|R2s]) :-
   M #< 0,                                                    % <- here
   lists_mask_mlists(Xs,Ys,Ms,R1s,R2s).
lists_mask_mlists([_X|Xs],[Y|Ys],[M|Ms],[0|R1s],[Y|R2s]) :-
   M #>= 0,                                                   % <- here
   lists_mask_mlists(Xs,Ys,Ms,R1s,R2s).

现在第二个查询也有效了：

   ?- masker([[1,5,3,8],[1,5,3,8]],[[5,4,7,4],[5,4,7,4]],[[X,-1,4,-4],[4,-1,4,-4]],M1,M2).
M1 = [[1,5,0,8],[0,5,0,8]],
M2 = [[0,0,7,0],[5,0,7,0]],
X in inf.. -1 ? ;
M1 = [[0,5,0,8],[0,5,0,8]],
M2 = [[5,0,7,0],[5,0,7,0]],
X in 0..sup ? ;
no

Answer 2

@tas 给出了很好的解决方案和解释(+1)。

基于此代码，我想提高程序的space效率。再次考虑使用基于 CLP(FD) 的解决方案的示例查询：

?- masker([[1,5,3,8],[1,5,3,8]],[[5,4,7,4],[5,4,7,4]],[[4,-1,4,-4],[4,-1,4,-4]],M1,M2).
M1 = [[0, 5, 0, 8], [0, 5, 0, 8]],
M2 = [[5, 0, 7, 0], [5, 0, 7, 0]] ;
false.

我们从 ; false 中看到 选择点 是在该程序执行期间累积的，因为对于 Prolog 引擎来说，这些子句在事实互斥。

显然，此类程序使用的内存超出了跟踪剩余选项所需的内存。

抵制诱惑不纯粹地切断计算的分支，因为那只会导致更多的问题。

相反，请考虑使用 if_/3。

在这种情况下应用 if_/3 所需要做的就是非常简单地具体化 CLP(FD) 约束 (#<)/2，这很容易用 zcompare/3 实现：

#<(X, Y, T) :-
        zcompare(C, X, Y),
        less_true(C, T).

less_true(<, true).
less_true(>, false).
less_true(=, false).

有了这个定义，整个程序就变成了：

:- use_module(library(clpfd)).

masker([], [], [], [], []).
masker([X|Xs], [Y|Ys], [M|Ms], [R1|R1s], [R2|R2s]) :-
        lists_mask_mlists(X, Y, M, R1, R2),
        masker(Xs, Ys, Ms, R1s, R2s).

lists_mask_mlists([], [], [], [], []).
lists_mask_mlists([X|Xs], [Y|Ys], [M|Ms], R1s0, R2s0) :-
        if_(M #< 0,
            (R1s0 = [X|R1s], R2s0 = [0|R2s]),
            (R1s0 = [0|R1s], R2s0 = [Y|R2s])),
        lists_mask_mlists(Xs, Ys, Ms, R1s, R2s).

现在重点是：

?- masker([[1,5,3,8],[1,5,3,8]],[[5,4,7,4],[5,4,7,4]],[[4,-1,4,-4],[4,-1,4,-4]],M1,M2).
M1 = [[0, 5, 0, 8], [0, 5, 0, 8]],
M2 = [[5, 0, 7, 0], [5, 0, 7, 0]].

此示例查询现在 确定性!

而且该程序仍然足够通用也可以处理第二个示例查询！

Prolog 中的屏蔽

Masking in Prolog

list

prolog

masking

clpfd