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

Это потому, что у вас заканчивается пространство на куче. По умолчанию для кучи программ Clean установлено значение 2M. Вы можете это изменить, конечно. При использовании clm из командной строки вы можете добавить -h 4M в свою командную строку или в командную строку самой чистой программы. Если вы используете чистую среду 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 может отбросить элементы он итерированные над и кучи не заполняется.