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



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

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

Prolog代码中存在一些基本问题:

  • sum是一个Prolog原子,所以它永远不会与列表统一。
  • 在Prolog中,我们定义了实体之间的关系,你需要谓词参数来引用这些实体。

因此,您不能逐字翻译代码。尽管如此,一个相当字面的Haskell&rightarrow;Prolog翻译是 可能的,例如,如果你引入一个新的参数来保存原始函数的返回值。你的第二个代码段是朝着这个方向前进的,但它不是自包含的,并且还包含几个错误。例如,xssum原子,而Prolog变量以大写 字母或 下划线开头。

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


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

我们的第一个观察结果,从类型签名中可以清楚地看出:我们正在推理整数。因此,我建议您使用 Prolog 系统的CLP(FD) 约束来实现完全声明性的整数 算术。有关此功能的详细信息,请参阅 clpfd。

其次,该任务可以看作是"过滤"列表,为此我们使用library(reif)提供的 tfilter/3

以下是完整的Prolog解决方案:

sublist_sum(Lss0, Sum, Lss) :- tfilter(sum_intlist(Sum), Lss0, Lss). sum_intlist(总和, Ls, T) :- sum(Ls, #=, Sum0), zcompare(C, Sum0, Sum), eq_truth(C, T). eq_truth(=,真)。 eq_truth(<,错误)。 eq_truth(>,错误)。

将此谓词视为将列表Lss0总和和第二个列表 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 英寸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#=总和; Ls = [], A+B+C#=_15806, _15806#=<总和+>, _15806, Sum).

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

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

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

在这里,我们问:这个具体 案例成立吗?,Prolog用true回应,表明在这种情况下,这种关系完全按照预期 工作。

相关内容

  • 没有找到相关文章

最新更新