将 Haskell 翻译成 Prolog - 查找总和的子列表

Question

我正在尝试翻译以下 Haskell 代码：

-- sublistSums list sum returns a list of the sublists of list that add up to sum
sublistSums :: [Int] -> Int -> [[Int]]
sublistSums [] 0 = [[]]
sublistSums [] _ = []
sublistSums (x:xs) sum = [x:tailList | tailList <- sublistSums xs (sum-x)] ++
                         sublistSums xs sum

...进入序言。该代码应该给我一个总和等于目标数字的所有列表的列表。例如，

?- sublistSums([[1,2,3],[4,5,6]],6).

如果绑定的话应该给你 [[1,2,3]] 因为 1+2+3=6.

这是我目前所拥有的：

sublistSums([], 0) :-
    sublistSums([],0,[]).
sublistSums([], _) :-
    sublistSums([],0,[]).
sublistSums([x|xs], sum) :-
    conc(conc(x,findall(xs,(sublistSums(xs, (sum-x))),List)), sublistSums(xs, sum)).

然而，当我调用 sublistSums 函数时，它给了我这个：

?- sublistSums([[1,2,3],[4,5,6]],6).
false.

我也试过：

sublistSums([], 0, ReList) :-
   [[]].
sublistSums([], _, ReList) :-
   [].
sublistSums([x|xs], sum, ReList) :-
   conc(conc(x,findall(xs,(sublistSums(xs, (sum-x)),ReList),List)), sublistSums(xs, sum, ReList)).

仍然给我相同的结果。不确定我在这里做错了什么。

Answer 1

您的 Prolog 代码中存在一些基本问题：

sum 是 Prolog atom，因此它永远不会 与列表统一。
在Prolog中，我们定义了实体之间的关系，你需要谓词参数来引用这些实体。

因此，您无法逐字翻译代码。不过，相当文字 Haskell→Prolog 翻译是可能的，例如，如果您引入一个新的 argument 来保存原始函数的return 值。您的第二个片段进入了这个方向，但它不是独立的，并且还包含一些错误。例如 xs 和 sum 是 atoms，而 Prolog variables 以大写字母或下划线开头。

此外，如果您继续尝试文字翻译，您将放弃真正受益于[的普遍性的机会=87=]关系。典型的 Prolog 谓词不仅可以用于一个，还可以用于多个方向，您不仅可以使用它们来计算，还有 test 和 complete 部分结果。

因此，我想向您展示一个更惯用此任务的 Prolog 解决方案，而不是直译。

我们的第一个观察结果，从 类型签名 中可以清楚地看出：我们正在推理整数。因此，我建议您使用 Prolog 系统的 CLP(FD) 约束 进行完全 声明式 整数运算。有关此功能的更多信息，请参阅 clpfd。

其次，任务可以被视为 "filtering" 一个列表，为此我们使用 library(reif) 提供的 tfilter/3。

这是完整的 Prolog 解决方案：

sublist_sum(Lss0, Sum, Lss) :-
        tfilter(sum_intlist(Sum), Lss0, Lss).

sum_intlist(Sum, Ls, T)  :-
        sum(Ls, #=, Sum0),
        zcompare(C, Sum0, Sum),
        eq_truth(C, T).

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

将此谓词视为 relating 列表 Lss0、sum 和第二个列表 Lss，以便满足您声明的所有要求。请注意，我没有说这些参数中的哪些是 "given"，因为它们中的任何一个都可能完全、部分或根本没有指定。

您的示例按要求运行：

?- sublist_sum([[1,2,3],[4,5,6]], 6, Ls).
Ls = [[1, 2, 3]].

此示例保持在原始函数的范围内：第一个和第二个参数已完全指定，第三个参数用于表示"result"。

然而，正如 Prolog 的典型情况，我们还可以进行更多一般查询，其中不仅 "result"，而且其他部分都未指定。显然，这远远超出了函数的范围，直接翻译原始代码可能没有这个好处。

例如：

?- sublist_sum([[1,2,N]], 6, Ls).

在这种情况下，我们留下N未指定，并要求Prolog考虑所有可能申请的情况N.

作为响应，Prolog 生成不同的可能性，呈现为析取:

N = 3,
Ls = [[1, 2, 3]] ;
Ls = [],
N in inf..2,
-3+_10694#=N,
_10694 in inf..5 ;
Ls = [],
N in 4..sup,
-3+_10662#=N,
_10662 in 7..sup.

请注意 Ls 如何依赖于 N。

我们还可以进一步概括这个，甚至不指定总和：

?- sublist_sum([[A,B,C]], Sum, Ls).
Ls = [[A, B, C]],
A+B+C#=Sum ;
Ls = [],
A+B+C#=_15806,
_15806#=<Sum+ -1,
zcompare(<, _15806, Sum) ;
Ls = [],
A+B+C#=_15806,
Sum#=<_15806+ -1,
zcompare(>, _15806, Sum).

同样，Prolog 列举了不同的情况。

此外，我们可以专门化查询并将其用于测试关系：

?- sublist_sum([[1,2,3]], 5, []).
true.

在这里，我们问了：这个具体案例成立吗？，Prolog 以 true 响应，表明这种关系在这种情况下完全符合预期。

将 Haskell 翻译成 Prolog - 查找总和的子列表

Translate Haskell to Prolog - finding sublist of sum

haskell

list-comprehension

prolog

sublist

prolog-findall