Образцы взрыва - просто сахар для 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]) | ... ]. Конечно, взрывшаблоны более удобны, поэтому они являются таким распространенным расширением! (С другой стороны, вам, вероятно, не нужно форсировать всех из них; знание того, что форсировать, полностью зависит от конкретной структурыкода, и дикое добавление паттернов взрыва ко всему обычно просто замедляет ход событий.)
Действительно, "хвостовая рекурсия" per se не так уж много значит в Haskell: если ваш аккумуляторпараметры не являются строгими, вы переполните стек, когда позже попытаетесь их форсировать, и, действительно, благодаря лени, многие non -tail-рекурсивные программы не работаютпереполнить стек;печать repeat 1 никогда не будет переполнять стек, хотя определение - repeat x = x : repeat x - явно имеет рекурсию в нехвостовой позиции.Это потому, что (:) ленив во втором аргументе;если вы пройдете по списку, у вас будет постоянное использование пространства, так как форсируются repeat x thunks, а предыдущие cons-ячейки выбрасываются сборщиком мусора.
На более философском замечании tail-рекурсивные циклы обычно считаются субоптимальными в Хаскеле.В общем, вместо того, чтобы итеративно вычислять результат по шагам, мы предпочитаем сгенерировать структуру со всеми шаговыми эквивалентами на листьях и выполнить преобразование (например, складку) для получения окончательного результата.,Это гораздо более высокоуровневое представление о вещах, которое становится эффективным благодаря лени (структура создается и собирается как мусор по мере обработки, а не сразу). 2
Этосначала может потребоваться некоторое привыкание, и это, конечно, не работает во всех случаях - чрезвычайно сложные структуры циклов могут быть проблемой для эффективного перевода 3 - но прямой перевод хвост-рекурсивных циклов в Haskell может бытьбольно именно потому, что на самом деле это не так уж идиоматично.
Что касается вставки, на которую вы ссылаетесь, id $! x не работает, чтобы принудить что-либо, потому что это то же самое, что x `seq` id x, который являетсятакой же как x `seq` x, который совпадает с x.По сути, всякий раз, когда форсируется x `seq` y, форсируется x, и в результате получается y.Вы не можете использовать seq, чтобы просто заставить вещи в произвольных точках;вы используете его, чтобы принудительно настроить * thunks в зависимости от других thunks.
В этом случае проблема в том, что вы создаете большой thunk в c, поэтому вывероятно, хотите заставить auxk и auxj форсировать его;простой способ - добавить предложение типа auxj _ _ c _ | seq c False = undefined в начало определения.( guard всегда проверяется, заставляя c быть оцененным, но всегда приводит к False, поэтому правая часть никогда не оценивается.)
Лично я быПредложите сохранить шаблон взрыва в окончательной версии, так как он более читабелен, но f c _ | seq c False = undefined будет работать так же хорошо.
1 См. Элегантное запоминание с функциональными попытками запоминания и библиотекой данных-мемокомбинаторов .
2 Действительно, GHC часто может даже исключить промежуточную структуру полностью , используя fusion и вырубку леса , создавая машинный код, подобный тому, как вычисление будет записано в низкоуровневый императивный язык.
3 Хотя, если у вас есть такие циклы, вполне возможно, что этот стиль программирования поможет вам упростить их - лень означает, что вы можете легко разделить независимые части вычисления на отдельные структуры, а затем отфильтровать и объединять их, не беспокоясь о том, что вы будете дублировать работу, делая промежуточные вычисления, которые впоследствии будут отброшены.