Пример программы 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

Это потому, что вам не хватает места в куче. По умолчанию куча чистых программ установлена ​​на 2M. Вы можете изменить это, конечно. Когда используешь clm из командной строки вы можете добавить -h 4M в его командную строку или в командную строку самой чистой программы. Если вы используете Clean IDE, вы можете изменить размер кучи через Параметры проекта, Приложение.

Причина того, что ( все еще печатается (что я получаю, а не [), заключается в следующем. Чистая программа будет выводить как можно большую часть своих выходных данных, вместо того, чтобы ждать, пока не будет известен весь вывод. Это означает, например, что простая строка 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 может отбросить элементы, которые он повторял, и куча не заполняется.