修复 Prolog 中的列表输出

Question

我正在尝试解决荷兰国旗问题。基本上，给定一个列表，我想按红-白-蓝的顺序对它们进行排序。红色、白色和蓝色由它们的谓词定义（即 red(x)、white(x) 等）目前，我有以下代码：

red(1).
white(2).
blue(3).

dutch(Xs,Ys):- 
    getRed(Xs,[], Red), getWhite(Xs,[],White), getBlue(Xs,[],Blue), 
    append([], Red, Y1), append(Y1, White, Y2), append(Y2, Blue, Ys).

getRed([],Rs,Rs).
getRed([X|Rest], Acc, Rs) :- red(X), getRed(Rest, [X,Acc] , Rs).
getRed([X|Rest], Acc, Rs) :- getRed(Rest, Acc, Rs).

getWhite([],Rs,Rs).    
getWhite([X|Rest], Acc, Rs) :- white(X), getWhite(Rest, [X,Acc], Rs).
getWhite([X|Rest], Acc, Rs) :- getWhite(Rest, Acc, Rs).

getBlue([],Rs,Rs).
getBlue([X|Rest], Acc, Rs) :- blue(X), getBlue(Rest, [X,Acc], Rs).    
getBlue([X|Rest], Acc, Rs) :- getBlue(Rest, Acc, Rs).

我的输出如下所示：

?- dutch([1,2,3],R).
R = [1, [], 2, [], 3, []]
R = [1, [], 2, []]
R = [1, [], 3, []]
R = [1, []]
R = [2, [], 3, []]
R = [3, []]
R = []

我想要的是它看起来像这样：

R = [1, 2, 3]

我已经尝试了几种方法来强制输出到我想要的，但一直无法接近。

编辑：看起来我可以通过使用强力解决方案来解决它，该解决方案将所有可能的集合排列并评估该集合是否按 "Dutch Flag" 顺序排列。有没有更好的解决方案？

Answer 1

我在您的代码中看到两个错误：

1) 您的终端子句 getRed([],Rs,Rs)、getWhite([],Rs,Rs)、getBlue([],Rs,Rs) 接受空列表作为值结果（当 Rs 等于 []);我建议将它们重写为

getRed([],Rs,Rs)   :- Rs \= [].
getWhite([],Rs,Rs) :- Rs \= [].
getBlue([],Rs,Rs)  :- Rs \= [].

2) 在接受子句中（当 X 是搜索颜色时），当您应该使用竖线时（[X,Acc]; 应该是 ([X|Acc]); 我建议将它们重写为

getRed([X|Rest], Acc, Rs)   :- red(X),   getRed(Rest, [X|Acc], Rs).
getWhite([X|Rest], Acc, Rs) :- white(X), getWhite(Rest, [X|Acc] , Rs).
getBlue([X|Rest], Acc, Rs)  :- blue(X),  getBlue(Rest, [X|Acc], Rs).

题外话：没有理由将Red附加到一个空列表；结果列表 (Y1) 是 Red 本身；我建议简化

append([], Red, Y1), append(Y1, White, Y2), append(Y2, Blue, Ys)

如下

append(Red, White, Mid), append(Mid, Blue, Ys)

--- 编辑 ---

不确定您到底想要什么，但我怀疑第三个版本条款中的第三个错误：当 X 未累积时。

我认为您应该添加一个检查以确保 X 不是搜索到的颜色；我建议将它们重写如下

getRed([X|Rest], Acc, Rs)   :- \+ red(X),   getRed(Rest, Acc, Rs).
getWhite([X|Rest], Acc, Rs) :- \+ white(X), getWhite(Rest, Acc, Rs).
getBlue([X|Rest], Acc, Rs)  :- \+ blue(X),  getBlue(Rest, Acc, Rs).

--- 编辑 2 ---

我认为您的 getRed/3、getWhite/3 和 getBlue/3 子句中不需要累加器。

我建议一个只有 2 个参数的版本

red(1).
white(2).
blue(3).

dutch(Xs,Ys):- 
    getRed(Xs, Red), getWhite(Xs, White), getBlue(Xs, Blue), 
    append(Red, White, Mid), append(Mid, Blue, Ys).

getRed([],[]).
getRed([X|Rest], [X|Rs]) :- red(X),    getRed(Rest, Rs).
getRed([X|Rest], Rs)     :- \+ red(X), getRed(Rest, Rs).

getWhite([],[]).
getWhite([X|Rest], [X|Rs]) :- white(X),    getWhite(Rest, Rs).
getWhite([X|Rest], Rs)     :- \+ white(X), getWhite(Rest, Rs).

getBlue([],[]).
getBlue([X|Rest], [X|Rs]) :- blue(X),    getBlue(Rest, Rs).
getBlue([X|Rest], Rs)     :- \+ blue(X), getBlue(Rest, Rs).

Answer 2

一个纯粹的解决方案

前言

我想在现有解决方案的基础上添加一个纯、关系解决方案。

理想情况下，您可以在 所有方向 中使用 Prolog 谓词，现在我将展示一个可以让您这样做的实现：您不仅可以对 实例化 根据你的标准列出，不，你也可以生成解决方案和完整部分实例化解决方案。

为此，我使用了来自 library(reif).

的元谓词 if_/3

具体化谓词

我从你的谓词的化版本开始，还冒昧地使用更有说服力的名称 red、white 和 blue 表示颜色：

red(R, T)   :- =(R, red, T).

white(W, T) :- =(W, white, T).

blue(B, T)  :- =(B, blue, T).

请注意，我使用的是 (=)/3，它随 library(reif) 免费提供。

使用 DCG 描述列表

接下来，纯粹为了方便起见，我使用dcg符号来描述感兴趣的子序列：

reds([]) --> [].
reds(Rs) -->
        [R],
        { if_(red(R), Rs = [R|Rest], Rs = Rest) },
        reds(Rest).

whites([]) --> [].
whites(Ws) --> [W],
        { if_(white(W), Ws = [W|Rest], Ws = Rest) },
        whites(Rest).

blues([]) --> [].
blues(Bs) --> [B],
        { if_(blue(B), Bs = [B|Rest], Bs = Rest) },
        blues(Rest).

我把它简化为一个简单的练习。

解决方案

有了这些积木，我们就可以表达出整体的解决方案：

dutch(Colors, Ds) :-
        phrase(reds(Rs), Colors),
        phrase(whites(Ws), Colors),
        phrase(blues(Bs), Colors),
        phrase((Rs,Ws,Bs), Ds).

例子

当然，这适用于简单的实例化情况，例如：

?- dutch([red,white,blue], Ds).
Ds = [red, white, blue] ;
false.

现在重点是：也适用于最一般的情况，其中所有参数都是变量:

?- length(Cs, _), dutch(Cs, Ds).
Cs = Ds, Ds = [] ;
Cs = Ds, Ds = [red] ;
Cs = Ds, Ds = [white] ;
Cs = Ds, Ds = [blue] ;
Cs = [_G1322],
Ds = [],
dif(_G1322, blue),
dif(_G1322, white),
dif(_G1322, red) ;
Cs = Ds, Ds = [red, red] ;
Cs = Ds, Ds = [red, white] ;
Cs = Ds, Ds = [red, blue] ;
Cs = [red, _G1340],
Ds = [red],
dif(_G1340, blue),
dif(_G1340, white),
dif(_G1340, red) .

通过添加更多目标，我们可以专门化此查询以观察现在生成的具体解决方案：

?- length(Cs, _), Cs = [_,_,_|_], dutch(Cs, Ds), ground(Cs).
Cs = Ds, Ds = [red, red, red] ;
Cs = Ds, Ds = [red, red, white] ;
Cs = Ds, Ds = [red, red, blue] ;
Cs = [red, white, red],
Ds = [red, red, white] ;
Cs = [red, blue, red],
Ds = [red, red, blue] .

将其与进行比较，不能用于公平枚举解决方案：

?- length(Xs, _), Xs = [_,_,_|_], dutch(Xs, Ys).
Xs = Ys, Ys = [1, 1, 1] ;
Xs = Ys, Ys = [1, 1, 1, 1] ;
Xs = Ys, Ys = [1, 1, 1, 1, 1] ;
Xs = Ys, Ys = [1, 1, 1, 1, 1, 1] ;
Xs = Ys, Ys = [1, 1, 1, 1, 1, 1, 1] .

总结

因此，通过保留logical-purity，我们得到了一个更通用的逻辑程序，我们可以全方位使用

诚然，您并没有要求这种普遍性。但是，虽然我们正在这样做，为什么要放弃它？

修复 Prolog 中的列表输出

Fixing list output in Prolog

prolog

dutch-national-flag-problem

一个纯粹的解决方案

前言

具体化谓词

使用 DCG 描述列表

解决方案

例子

总结