N-Queens 示例程序奇怪的输出

Question

我尝试使用 squeen.icl 示例中的代码。当我用 BoardSize :== 11 尝试时，没有问题。但是当我将其更改为 12 时，输出是 [。为什么？如何解决？

module squeen
import StdEnv

BoardSize :== 12

Queens::Int [Int] [[Int]] -> [[Int]]
Queens row board boards
    | row>BoardSize =  [board : boards]
    | otherwise     =  TryCols BoardSize row board boards

TryCols::Int Int [Int] [[Int]] -> [[Int]]
TryCols 0 row board boards =  boards
TryCols col row board boards
    | Save col 1 board  =   TryCols (col-1) row board queens
    | otherwise         =   TryCols (col-1) row board boards
where   queens  = Queens (row+1) [col : board] boards

Save::!Int !Int [Int] -> Bool
Save  c1 rdiff [] =  True
Save  c1 rdiff [c2:cols]
    | cdiff==0 || cdiff==rdiff || cdiff==0-rdiff    =   False
    | otherwise                                     =   Save c1 (rdiff+1) cols
where   cdiff   = c1 - c2


Start::(Int,[Int])
Start   =   (length solutions, hd solutions)
where   solutions   = Queens 1 [] []

Answer 1

这是因为您运行超出 space 堆。默认情况下，Clean 程序的堆设置为 2M。当然，您可以更改此设置。从命令行使用 clm 时，您可以将 -h 4M 添加到其命令行或 clean 程序本身的命令行。如果您使用的是 Clean IDE，您可以通过“项目选项”、“应用程序”更改堆大小。

仍然打印 ( 的原因（这是我得到的，而不是 [），如下所示。 Clean 程序将输出尽可能多的输出，而不是等到知道整个输出。这意味着，例如，像 Start = [0..] 这样的简单行将向您的终端发送垃圾邮件，而不是等到整个无限列表都在内存中然后打印它。在 squeen.icl 的情况下，Clean 看到 Start 的结果将是一个元组，因此直接打印左大括号。但是，当尝试计算元组的元素时（length solutions 和 hd solutions），堆会填满，导致程序终止。

我不知道当你在 Windows 上堆满时会是什么样子，但在 Linux(/Mac) 上，它看起来像这样:

$ clm squeen -o squeen && ./squeen -h 2M
Linking squeen
Heap full.
Execution: 0.13  Garbage collection: 0.03  Total: 0.16
($

注意元组左大括号在最后一行。所以，当使用终端时，很容易发现这个错误。

有趣的是，由于 length 利用了尾递归，元组的第一个元素可以计算出来，即使堆很小（您可以通过用 [] 替换第二个元素来尝试）。元组的第二个元素也可以在小堆上计算（用 0 替换第一个元素）。

关键是长度是在之前计算的，因为它必须首先打印。虽然通过正常的 length 调用，列表的部分内容被垃圾收集（在遍历前 100 个元素后，它们可以被丢弃，从而允许较小的堆使用），hd 调用确保第一个列表的元素未被丢弃。如果第一个元素没有被丢弃，那么第二个、第三个等等也不会被丢弃。因此，整个列表都保存在内存中，而这实际上并不是必需的。翻转 length 和 hd 调用解决问题：

Start :: ([Int], Int)
Start = (hd solutions, length solutions)
where solutions = Queens 1 [] []

现在，在调用 hd 之后，没有理由将整个列表保留在内存中，因此 length 可以丢弃它已经迭代过的元素，并且堆不会填满向上。

N-Queens 示例程序奇怪的输出

N-Queens example program strange output

functional-programming

n-queens

clean-language