在Haskell中可能会产生堆栈溢出的尾部递归解决方案

Question

我一直在尝试解决AdventofCode第5天问题2（https://adventofcode.com/2017/day/5）。它与第一个问题不同，如果项目大于3，则它会降低，而不是增加1。

。

使用测试数据运行实施时，它会产生正确的结果，因此实现似乎是完美的。另外，递归电话看起来处于尾部位置，但仍会产生堆叠的异常。

代码看起来像

module AdventOfCode5 where
type Instruction = Int
type Position = Int
main :: IO ()
main = do
  input <- readFile "day5input.txt"
  let instructions = fmap (read :: String -> Instruction) $ lines input
  _ <- putStrLn $ show $ computeResult (Prelude.length instructions) 0 (+1) $ instructions
  return ()
main2 :: IO ()
main2 = do
  input <- readFile "day5input.txt"
  let instructions = fmap (read :: String -> Instruction) $ lines input
  _ <- putStrLn $ show $ computeResult (Prelude.length instructions) 0 decAbove3AndIncBelow3 instructions
  return ()
decAbove3AndIncBelow3 :: Int -> Int
decAbove3AndIncBelow3 x
  | x >= 3 = x - 1
  | otherwise = x + 1
computeResult :: Int -> Position -> (Int -> Int) -> [Instruction] -> Int
computeResult = takeStep' 0
  where takeStep' :: Int -> Int -> Position -> (Int -> Int) -> [Instruction] -> Int
        takeStep' count max pos changeInteger instructions
          | pos >= max = count
          | otherwise =
              let
                elementAtPos = instructions!!pos
                newCount = count + 1
                newPos = pos + elementAtPos
                newInstructions = (take pos instructions) ++ ([(changeInteger elementAtPos)]) ++ (drop (pos + 1)) instructions
              in
                takeStep' newCount max newPos changeInteger newInstructions

实现的想法是，您可以持有计数器并为每次迭代增加计数器，结合使用更新版本（其中int-> int是知道如何更新的函数）的说明列表）。一旦位置大于列表的大小，您就可以在哪里查看，并且递归停止（我以输入为输入，但也可以从指令列表中得出）。

任何人都可以向我解释为什么这是一个堆叠量？

Answer 1

在takeStep'的第一个参数中存在空间泄漏，因为它构建了一个thunk (... ((0 + 1) + 1) ...) + 1，而不仅仅是评估整数。

当thunk得到评估时，堆栈可能会爆炸。

• 使用seq在继续之前强制count，例如，Guard中的count `seq` otherwise;
• 或通过优化进行编译。

ghci正在解释它，而不是对其进行编译。特别是，它没有执行自动修复泄漏所需的严格分析。

您可以运行此命令以优化（-O）

编译

ghc -O -main-is AdventOfCode5.main2 AdventOfCode5.hs

（尽管即使没有优化汇编，似乎也可以减少空间的使用足以成功。）