Итак, короткая версия моего вопроса: как мы должны кодировать циклы в Haskell,в общем? В Haskell нет гарантии оптимизации хвоста, паттерны взрыва даже не являются частью стандарта (верно?), А парадигма фолд / фолдне гарантированно работать в любой ситуации. ВотДело в точке были только паттерны взрыва, которые помогли мне заставить его работать в постоянном пространстве (даже не используя$! помогло ... хотятестирование было сделано на Ideone.com, который использует ghc-6.8.2).

В основном речь идет о вложенном цикле, который в list-paradigm можно сформулировать как

prod (sum,concat) . unzip $ 
    [ (c, [r | t]) | k<-[0..kmax], j<-[0..jmax], let (c,r,t)=...]
prod (f,g) x = (f.fst $ x, g.snd $ x)

Или в псевдокоде:

let list_store = [] in
for k from 0 to kmax
    for j from 0 to jmax
        if test(k,j) 
            list_store += [entry(k,j)]
        count += local_count(k,j)
result = (count, list_store)

До тех пор, пока я не добавил к нему паттерн взрыва, я получал выброс памяти или даже переполнение стека. Но шаблоны взрыва не являются частью стандарта, верно? Итак, вопрос в том,как Можно ли кодировать вышеизложенное в стандартном Haskell для работы в постоянном пространстве?

Воттестовый код, Расчет поддельный, но проблемы те же.РЕДАКТИРОВАТЬ: foldrСформулированный код:

testR m n = foldr f (0,[]) 
               [ (c, [(i,j) | (i+j) == d ])
                 | i<- [0..m], j<-[0..n], 
                   let c = if (rem j 3) == 0 then 2 else 1 ]
  where d = m + n - 3
    f (!c1, [])     (!c, h) = (c1+c,h) 
    f (!c1, (x:_))  (!c, h) = (c1+c,x:h)

Пытаясь запустить print $ testR 1000 1000 производит переполнение стека. Изменение наfoldl только успешно, если использование взрыва образцов вf, но он строит список в обратном порядке. Я хотел бы построить его лениво и в правильном порядке. Это может быть сделано с любым видомfold, дляидиоматический решение?

РЕДАКТИРОВАТЬ: Подводя итог полученному от @ehird ответу: нечего бояться, используя шаблон взрыва. Хотя не в самом стандартном Haskell, он легко закодирован в нем какf ... c ... = case (seq c False) of {True -> undefined; _ -> ...}, Урок заключается в том, что только сопоставление с образцом приводит к значению, иseq делаетНЕ заставить что-нибудь само по себе, а скорее устраиваеткогда seq x y принудительно - путем сопоставления с образцом -x будет вынужден тоже, иy будет ответом. Вопреки тому, что я мог понять из онлайн-отчета,$! делаетНЕ заставить что-нибудь само по себе, хотя этоявляется называется«оператор строгой заявки».

И точка из @stephentetley -взыскательность очень важно в управлении поведением пространства. Таким образом, вполне нормально кодировать циклы в Haskell с надлежащим использованием аннотаций строгости с шаблонами взрыва, где это необходимо, для написания любого вида специальной функции свертывания (то есть, потребления структуры), которая необходима - как я в конечном итоге делал в первую очередь. - и полагаться на GHC для оптимизации кода.

Большое спасибо всем за вашу помощь.