Гарантия оптимизации хвоста - циклическое кодирование в Haskell
Итак, короткая версия моего вопроса такова: как мы вообще должны кодировать циклы в 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 для оптимизации кода.
Большое спасибо всем за вашу помощь.
2 ответа
Модели взрыва просто сахар для seq - всякий раз, когда вы видите let !x = y in z, что можно перевести на let x = y in x `seq` z, seq стандартно, поэтому нет проблем с переводом программ, использующих шаблоны взрыва, в переносимую форму.
Это правда, что Haskell не дает никаких гарантий относительно производительности - в отчете даже не определяется порядок оценки (только то, что он должен быть нестрогим), не говоря уже о существовании или поведении стека времени выполнения. Однако, хотя в отчете не указан конкретный метод реализации, вы, безусловно, можете оптимизировать его.
Например, вызов по требованию (и, следовательно, совместное использование) используется на практике всеми реализациями Haskell и имеет жизненно важное значение для оптимизации кода Haskell для использования памяти и скорости. Действительно, чистый трюк с запоминанием 1 (так как полагается на совместное использование (без него это просто замедлит процесс).
Эта базовая структура позволяет нам видеть, например, что переполнение стека вызвано созданием слишком больших блоков. Поскольку вы не опубликовали весь свой код, я не могу сказать вам, как переписать его без шаблонов взрыва, но я подозреваю, [ (c, [r | t]) | ... ] должен стать [ c `seq` r `seq` t `seq` (c, [r | t]) | ... ], Конечно, шаблоны взрыва более удобны; вот почему они такие распространенные расширения! (С другой стороны, вам, вероятно, не нужно форсировать все это; знание того, что форсировать, полностью зависит от конкретной структуры кода, и дикое добавление паттернов взрыва ко всему обычно просто замедляет процесс.)
Действительно, "хвостовая рекурсия" сама по себе не так уж много значит в Haskell: если параметры вашего аккумулятора не являются строгими, вы переполните стек, когда позже попытаетесь их форсировать, и действительно, благодаря лени, многие не хвостовые рекурсивные программы не переполняют стек; печать repeat 1 никогда не переполнит стек, даже если определение - repeat x = x : repeat x - явно имеет рекурсию в нехвостом положении. Это потому что (:) ленив в своем втором аргументе; если вы пройдете по списку, у вас будет постоянное использование пространства, так как repeat x вынуждают греметь, а сборщики мусора выбрасывают предыдущие минусы.
На более философском замечании хвостовые рекурсивные циклы обычно считаются субоптимальными в Хаскеле. В целом, вместо того, чтобы итеративно вычислять результат по шагам, мы предпочитаем генерировать структуру со всеми шаговыми эквивалентами на листьях и выполнять преобразование (например, сложение) для получения конечного результата. Это гораздо более высокоуровневое представление о вещах, которое становится эффективным благодаря лени (структура создается и собирается как мусор по мере обработки, а не все сразу). 2
Сначала это может потребовать некоторого привыкания, и, конечно, это работает не во всех случаях - чрезвычайно сложные структуры циклов могут быть проблемой для эффективного перевода 3 - но прямой перевод хвост-рекурсивных циклов в Haskell может быть болезненным именно потому, что это не так. на самом деле все это идиоматично.
Что касается пасты, на которую вы ссылаетесь, id $! x не работает, чтобы заставить что-либо, потому что это так же, как x `seq` id x, который так же, как x `seq` x, который так же, как x, В основном, всякий раз, когда x `seq` y вынужден, x вынужден, и результат y, Вы не можете использовать seq просто навязывать вещи в произвольных точках; вы используете его, чтобы заставить гудков зависеть от других гангстеров.
В этом случае проблема в том, что вы создаете большой поток в c так что вы, вероятно, хотите сделать auxk а также auxj заставить его; простой способ - добавить предложение типа auxj _ _ c _ | seq c False = undefined к началу определения. ( Охранник всегда проверяется, заставляя c оценивается, но всегда приводит к False, поэтому правая часть никогда не оценивается.)
Лично я бы предложил сохранить шаблон взрыва в финальной версии, так как он более читабелен, но f c _ | seq c False = undefined будет работать так же хорошо.
1 См. Элегантное запоминание с функциональными запоминаниями и библиотекой data-memocombinators.
2 Действительно, GHC часто может даже полностью исключить промежуточную структуру, используя слияние и вырубку лесов, создавая машинный код, подобный тому, как вычисления были бы написаны на низкоуровневом императивном языке.
3 Хотя у вас есть такие циклы, вполне возможно, что этот стиль программирования поможет вам упростить их - лень означает, что вы можете легко разделить независимые части вычислений на отдельные структуры, а затем отфильтровать и объединить их, не беспокоясь о том, что вы ' Я буду дублировать работу, делая промежуточные вычисления, которые позже будут выброшены.
Хорошо, давайте работать с нуля здесь.
У вас есть список записей
entries = [(k,j) | j <- [0..jmax], k <- [0..kmax]]
И на основе этих индексов у вас есть тесты и подсчеты
tests m n = map (\(k,j) -> j + k == m + n - 3) entries
counts = map (\(_,j) -> if (rem j 3) == 0 then 2 else 1) entries
Теперь вы хотите построить две вещи: "общее" количество и список записей, которые "проходят" тест. Проблема, конечно, в том, что вы хотите генерировать последние лениво, в то время как первые (чтобы не взорвать стек) должны оцениваться строго.
Если вы оцениваете эти две вещи по отдельности, то вы должны либо: 1) предотвратить совместное использование entries (сгенерируйте его дважды, один раз для каждого расчета) или 2) сохраните все entries список в памяти. Если вы оцениваете их вместе, то вы должны либо: 1) строго оценить, либо 2) иметь много стекового пространства для огромного блока, созданного для подсчета. Вариант № 2 для обоих случаев довольно плохой. Ваше императивное решение решает эту проблему просто путем оценки одновременно и строго. Для решения в Haskell вы можете выбрать вариант № 1 для отдельной или одновременной оценки. Или вы могли бы показать нам свой "настоящий" код и, возможно, мы могли бы помочь вам найти способ изменить ваши зависимости данных; может оказаться, что вам не нужен общий счет или что-то в этом роде.