Ответ 1
Шаблоны взлома - это просто сахар для seq - всякий раз, когда вы видите let !x = y in z, который может быть переведен в let x = y in x `seq` z. seq является стандартным, поэтому нет проблем с переводами программ, которые используют шаблоны ударов в переносимую форму.
Верно, что Haskell не дает никаких гарантий относительно производительности - отчет даже не определяет порядок оценки (только он должен быть нестрогим), не говоря уже о существовании или поведении стека времени выполнения. Однако, хотя в отчете не указан конкретный метод реализации, вы можете, безусловно, оптимизировать его.
Например, call-by-need (и, следовательно, совместное использование) используется на практике всеми реализациями Haskell, и имеет жизненно важное значение для оптимизации кода Haskell для использования и скорости памяти. Действительно, чистый трюк memoisation 1 (как полагается на совместное использование (без него он просто замедлит работу).
Эта базовая структура позволяет нам, например, увидеть, что переполнение стека вызвано созданием слишком больших трюков. Поскольку вы не опубликовали весь свой код, я не могу сказать вам, как его переписать без шаблонов, но я подозреваю, что [ (c, [r | t]) | ... ] должен стать [ c `seq` r `seq` t `seq` (c, [r | t]) | ... ]. Разумеется, диаграммы ударных более удобны; почему они являются таким распространенным распространением! (С другой стороны, вам, вероятно, не нужно вытеснять всех из них, зная, что заставить полностью зависит от конкретной структуры кода, и дико добавляя шаблоны ударов ко всему, как правило, просто замедляет работу.)
В самом деле, "хвостовая рекурсия" сама по себе не означает, что все в Haskell: если ваши параметры аккумулятора не являются строгими, вы переполните стек, когда позже попытаетесь заставить их, и действительно, благодаря лени, многие нерекурсивные программы не переполняют стек; печать repeat 1 никогда не будет переполнять стек, хотя определение - repeat x = x : repeat x - явно имеет рекурсию в не-хвостом положении. Это связано с тем, что (:) ленив во втором аргументе; если вы пройдете по списку, у вас будет постоянное использование пространства, поскольку repeat x thunks будут принудительно, а предыдущие ячейки cons будут выбрасываться сборщиком мусора.
В более философской заметке хвосто-рекурсивные петли обычно считаются субоптимальными в Haskell. В общем, вместо того, чтобы итеративно вычислять результат в шагах, мы предпочитаем создавать структуру со всеми степенными эквивалентами у листьев и делать на ней преобразование (например, сгиб) для получения конечного результата. Это гораздо более высокоуровневое представление о вещах, сделанное эффективно с лени (структура строится и сбор мусора, как она обрабатывается, а не все сразу). 2
Вначале это может занять некоторое время, и это, безусловно, не работает во всех случаях - чрезвычайно сложные структуры циклов могут быть болью, чтобы эффективно транслировать 3 но непосредственно переводить хвост-рекурсивный петли в Haskell могут быть болезненными именно потому, что на самом деле это не так уж идиоматично.
Что касается пасты, к которой вы привязаны, id $! x не работает, чтобы заставить что-либо, так как это то же самое, что и x `seq` id x, что совпадает с x `seq` x, что совпадает с x. В принципе, всякий раз, когда x `seq` y принудительно, x принудительно, а результат y. Вы не можете использовать seq, чтобы просто заставить вещи в произвольных точках; вы используете его для того, чтобы заставить фортуны зависеть от других thunks.
В этом случае проблема заключается в том, что вы создаете большой бит в c, поэтому вы, вероятно, захотите сделать auxk и auxj принудительно; простым методом было бы добавить предложение, подобное auxj _ _ c _ | seq c False = undefined, в начало определения. (guard всегда проверяется, заставляя c оцениваться, но всегда приводит к False, поэтому правая сторона никогда не оценивается.)
Лично я бы предложил сохранить шаблон удара, который у вас есть в финальной версии, так как он более читабельен, но f c _ | seq c False = undefined будет работать так же хорошо.
1 См. Элегантная memoization с помощью функциональных заметок memo и data-memocombinators библиотека.
2 Действительно, GHC часто может даже полностью исключить промежуточную структуру с помощью слияния и обезлесения, производя машинный код, аналогичный тому, как вычисление будет записываться на языке низкого уровня.
3Хотя, если у вас есть такие циклы, вполне возможно, что этот стиль программирования поможет вам упростить их - ленивость означает, что вы можете легко отделить независимые части вычислений от отдельных структур, затем фильтровать и комбинировать их, не опасаясь, что вы будете дублировать работу, делая промежуточные вычисления, которые позже будут выброшены.