2

我正在尝试翻译以下 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)).

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

4

1 回答 1

4

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

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

因此，您不能逐字翻译代码。尽管如此，如果您例如引入一个新参数来保存原始函数的返回值，则可以进行相当字面的 Haskell→Prolog 翻译。您的第二个片段朝这个方向发展，但它不是独立的，并且还包含几个错误。例如and是atom，而 Prolog变量以大写字母或下划线开头。xssum

此外，如果您继续尝试直译，您将失去真正受益于关系普遍性的机会。典型的 Prolog 谓词不仅可以用在一个方向上，还可以用在多个方向上，不仅可以用于计算，还可以用于测试和完成部分结果。

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

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

其次，该任务可以看作是“过滤”一个列表，为此我们使用library(reif)tfilter/3提供的 。

这是完整的 Prolog 解决方案：

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

sum_intlist(Sum, Ls, T) :-
        总和（Ls，#=，Sum0），
        zcompare(C, Sum0, Sum),
        eq_truth(C, T)。

eq_truth(=, true)。
eq_truth（<，假）。
eq_truth（>，假）。

将此谓词视为与list Lss0、sum和第二个 list 相关联Lss，这样您陈述的所有要求都得到满足。请注意，我没有说这些参数中的哪些是“给定的”，因为它们中的任何一个都可能是完全、部分或根本没有指定的。

您的示例按要求工作：

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

这个例子停留在原始 函数的范围内：第一个和第二个参数是完全指定的，第三个用于表示“结果”。

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

例如：

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

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

作为回应，Prolog生成不同的可能性，以析取形式呈现：

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

请注意如何Ls取决于N.

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

?- sublist_sum([[A,B,C]], Sum, Ls)。
Ls = [[A, B, C]],
A+B+C#=总和；
LS = [],
A+B+C#=_15806,
_15806#=<总和+ -1,
zcompare(<, _15806, Sum) ;
LS = [],
A+B+C#=_15806,
总和#=<_15806+ -1,
zcompare（>，_15806，总和）。

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

此外，我们可以专门化查询并使用它来测试关系：

?- sublist_sum([[1,2,3]], 5, [])。
真的。

在这里，我们问：这个具体案例是否成立？，并且 Prolog 以 响应true，表明该关系在这种情况下完全按照预期工作。

于 2017-04-10T22:07:02.400 回答