将约束变量与`length / 2`一起使用

Question

这是问题所在：$ swiplWelcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.6-5-g5aeabd5)Copyright (c) 1990-2015 University of Amsterdam, VU AmsterdamSWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,and you are welcome to redistribute it under certain conditions.Please visit http://www.swi-prolog.org for details.For help, use ?- help(Topic). or ?- apropos(Word).?- use_module(library(clpfd)).true.?- N in 1..3, length(L, N).N = 1,L = [_G1580] ;N = 2,L = [_G1580, _G1583] ;N = 3,L = [_G1580, _G1583, _G1586] ;ERROR: Out of global stack % after a while（我可以切换子查询的顺序，结果是一样的）。我想我需要贴标签N才能使用它，但是我想知道是什么问题？我以前没有设法cho缩length/2。前言 clpfd

Answer 1

length/2适当的列表长度约束可能比不确定性稍强的有用。你可以找到一个日食实现它在这里，所谓的len/2。这样，您将获得以下行为：

?- N :: 1..3, len(Xs, N).

N = N{1 .. 3}

Xs = [_431|_482]               % note it must contain at least one element!

There is 1 delayed goal.

Yes (0.00s cpu)

然后，您可以通过枚举来枚举有效列表N：

?- N :: 1..3, len(Xs, N), indomain(N).

N = 1

Xs = [_478]

Yes (0.00s cpu, solution 1, maybe more)

N = 2

Xs = [_478, _557]

Yes (0.02s cpu, solution 2, maybe more)

N = 3

Xs = [_478, _557, _561]

Yes (0.02s cpu, solution 3)

或通过生成具有良好旧标准的列表length/2：

?- N :: 1..3, len(Xs, N), length(Xs, _).

N = 1

Xs = [_488]

Yes (0.00s cpu, solution 1, maybe more)

N = 2

Xs = [_488, _555]

Yes (0.02s cpu, solution 2, maybe more)

N = 3

Xs = [_488, _555, _636]

Yes (0.02s cpu, solution 3)

Answer 2

以下基于clpfd和meta-predicate的巴洛克式变通办法如何？ tcount/3

：-use_module（[ library（clpfd），library（lambda） ]）。

list_FDlen（Xs，N）：-

   tcount（\ _ ^ =（true），Xs，N）。

让我们查询！

1..3中的？-N，list_FDlen（Xs，N）。

   N = 1，Xs = [_A]

; N = 2，Xs = [_A，_B]

; N = 3，Xs = [_A，_B，_C]

; 假。％普遍终止

？.2中的？-N，list_FDlen（Xs，N）。

   N = 0，Xs = []

; N = 1，Xs = [_A]

; N = 2，Xs = [_A，_B]

; 假。％也普遍终止

那这个特定的查询呢？

？-2..sup中的N，list_FDlen（Xs，N）。

   N = 2，Xs = [_A，_B]

; N = 3，Xs = [_A，_B，_C]

; N = 4，Xs = [_A，_B，_C，_D]

...％未终止（按预期）

Answer 3

让我们从最明显的一个开始。如果您切换目标，那么您将：

?- length(L, N), N in 1..3.

具有与以下相同的终止属性：

？ -长度（L，N），假，N的1..3。

因此很明显，这一定不能以Prolog的执行机制终止。

但是，如果放在N in 1..3前面，则可能会影响终止。为此，必须使用有限的手段来证明N从4开始不存在这种情况。您如何在没有约束的系统中（即仅存在语法统一性）证明这一点？好吧，你不能。而length/2被普遍定义只是没有约束的存在。随着library(clpfd)事情是微不足道的，对于N #>= 4, N in 1..3简单的故障1。还请注意，library(clpfd)与其合作不多library(clpq)，可能也很有趣。

结果，您将需要定义自己的长度-对于您感兴趣的每个约束包。这有点可惜，但是目前尚无通用的方法可以看到。（（（也就是说，如果您有兴趣并对此进行了思考，您可能会想出一个不错的API，每个约束系统都应遵循该API。A，我怀疑这将花费数十年的时间。目前，还有很多差异很大））

所以这是第一种天真的方法fd_length/2：

fd_length([], N) :-

   N #= 0.

fd_length([_|L], N0) :-

   N0 #>= 1,

   N1 #= N0-1,

   fd_length(L, N1).

好的，可以对此进行优化以避免不必要的选择点。但是还有一个更根本的问题：如果要确定length列表的长度N，这将创建N约束变量！但是我们只需要一个。

fd_length(L, N) :-

   N #>= 0,

   fd_length(L, N, 0).

fd_length([], N, N0) :-

   N #= N0.

fd_length([_|L], N, N0) :-

   N1 is N0+1,

   N #>= N1,

   fd_length(L, N, N1).

同样，由于许多原因，这也不是完美的：它可以像当前系统一样使用Brent算法；并结合所有fd属性。同样，算术表达式可能也不是一个好主意。但我必须(#)/1在SWI中等待...

1：严格来说，这仅对SICStus，SWI和YAP而言“根本失败”。对于在那些系统中，不会由于当前表示的耗尽而导致意外故障。也就是说，他们的失败总是可以被视为诚实。