haskell生成堆栈溢出时可能的尾递归解决方案

Question

我一直在努力解决第5天的问题2(https://adventofcode.com/2017/day/5).它与第一个问题的不同之处在于,如果项目大于等于3,则减少而不是增加1.

当使用测试数据运行实现时,它会产生正确的结果,因此看起来实现是完美的.此外,递归调用看起来处于尾部位置,但它仍然产生stackoverflow异常.

代码看起来像这样

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继续,例如,之前count `seq` otherwise在中后卫;
• 或者使用优化进行编译.

ghci正在解释它,而不是编译它.特别是,它不执行自动修复泄漏所需的严格性分析.

您可以运行此命令以使用optimizations(-O)进行编译

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

(尽管即使没有优化,编译似乎也足以减少空间使用量.)