Аккумуляторы в Haskell

Question

В Хаскеле, если я напишу

 fac n = facRec n 1
   where facRec 0 acc = acc
         facRec n acc = facRec (n-1) (acc*n)

и скомпилируйте его с помощью GHC, результат будет другим, чем если бы я использовал

 fac 0 = 1
 fac n = n * fac (n-1)

Я мог бы легко сделать fac n = product [1..n] и избежать всего этого, но меня интересует, как попытка хвостовой рекурсии работает на ленивом языке. Я понимаю, что все еще могу получить переполнение стека, потому что накапливаются thunks, но действительно ли что-то происходит иначе (с точки зрения конечной скомпилированной программы), когда я использую аккумулятор, чем когда я просто заявляю наивную рекурсию? Есть ли какая-то польза от исключения рекурсии хвоста, кроме улучшения разборчивости? Изменится ли ответ вообще, если я использую runhaskell для запуска вычисления вместо его компиляции вначале?

Answer 1

Хвостовая рекурсия имеет смысл в (GHC) Haskell, если ваш аккумулятор строг.Чтобы продемонстрировать проблему, вот «след» вашего хвостово-рекурсивного определения fac:

   fac 4
~> facRec 4 1
~> facRec 3 (1*4)
~> facRec 2 ((1*4)*3)
~> facRec 1 (((1*4)*3)*2)
~> facRec 0 ((((1*4)*3)*2)*1)
~> (((1*4)*3)*2) * 1
  ~> ((1*4)*3) * 2
    ~> (1*4) * 3
      ~> 1*4
    ~> 4 * 3
  ~> 12 * 2
~> 24 * 1
~> 24

Уровень отступа (приблизительно) соответствует уровню стека.Обратите внимание, что аккумулятор оценивается только в самом конце, и это может вызвать переполнение стека.Хитрость, конечно, состоит в том, чтобы сделать аккумулятор строгим.Теоретически возможно показать, что facRec является строгим, если он вызывается в строгом контексте, но я не знаю ни одного компилятора, который делает это, ATM.GHC выполняет оптимизацию хвостовых вызовов, поэтому для вызовов facRec используется постоянное пространство стека.

По той же причине foldl' обычно предпочтительнее foldl, поскольку перваястрог в аккумуляторе.

Что касается вашей второй части, runhaskell / runghc - это просто оболочка над GHCi.Если GHCi находит скомпилированный код, он будет использовать его, в противном случае он будет использовать интерпретатор байт-кода, который выполняет несколько оптимизаций, поэтому не ожидайте, что произойдут какие-либо необычные оптимизации.

Answer 2

В haskell это помогает писать вашу программу с хвостовой рекурсией, если ваш аккумулятор строг и вам нужен полный результат.

С помощью ghc runHaskell программа не будет оптимизирована, поэтому анализ строгости не будет, поэтому вы можете переполнить стек; в то время как если вы компилируете с оптимизацией, компилятор может обнаружить, что аккумулятор должен быть строгим и оптимизировать соответственно.

Чтобы увидеть, как все происходит по-другому (или нет), лучший способ - проверить сгенерированный основной язык, хороший пост в блоге от Дона Стюарта объясняет вещи . Кстати, многие из его постов в блоге интересны, если вы заинтересованы в производительности.

Answer 3

Ваш вопрос не завершен.Я предполагаю, что вы имеете в виду GHC, и по крайней мере без оптимизаций ответ «да», потому что рабочая функция (facRec в первом или fac во втором) имеет арность 2 по сравнению с единицей, и сборка будет отражать это.С оптимизацией или с JHC ответ, вероятно, "нет".