haskell优化尾递归中的代码和堆栈溢出

Question

当我试图学习函数式编程时，我决定在haskell中出现代码挑战。

在使用输入数据https://adventofcode.com/2017/day/5进行挑战5 https://adventofcode.com/2017/day/5/input时，我遇到了几个问题。

这是我的代码

import Data.Array
import System.IO

listToArray l =
  let n_elem = length l
      pos_val = zip (range (0, n_elem)) l
  in array (0, n_elem-1) pos_val

getData filename = do
  s <- readFile filename
  let l = map read (lines s) ::[Int]
      a = listToArray l 
  return a

-- Part 1

updatePosArray i a =
  let i_val = a ! i
  in (i+i_val, a//[(i, i_val + 1)])

solution1 a n_steps i
 | i >= length a || i < 0 = n_steps
 | otherwise =
    let ai = updatePosArray i a
    in solution1 (snd ai) (n_steps+1) (fst ai)

-- Part 2

updatePosArray2 i a =
  let i_val = a ! i
  in
    if i_val>=3 then (i+i_val, a//[(i, i_val-1)])
    else (i+i_val, a//[(i, i_val+1)])

solution2 a n_steps i
 | i >= length a || i < 0 = n_steps
 | otherwise =
    let ai = updatePosArray2 i a
    in solution2 (snd ai) (n_steps+1) (fst ai)


main = do
  x <- getData "/Users/lucapuggini/Documents/AdventOfCode/data/data_ch5_p1.txt"
  let x_ex = array (0,4) [(0, 0), (1, 3), (2, 0), (3, 1), (4, -3)]

  let n_steps_ex1 = solution1 x_ex 0 0
  print $ n_steps_ex1

  let n_steps1 = solution1 x 0 0
  print $ n_steps1

  let n_steps_ex2 = solution2 x_ex 0 0
  print $ n_steps_ex2

  -- very slow. Probably due to the immutable array
  let n_steps2 = solution2 x 0 0
  print $ n_steps2

这是我得到的结果：

lucas-MacBook-Pro:src lucapuggini$ stack runhaskell challenge5.hs

    5
    381680
    10
    stack overflow

代码是安静的慢但这可能是由于我使用不可变数组的事实，但我对堆栈溢出错误感到惊讶。我认为尾部递归不应该发生这种情况。

总之，我有两个问题：

1）为什么我得到stackoverflow错误？我错误地使用尾递归吗？

2）运行此代码的更有效但功能更强的方法是什么？不可变数组是一个糟糕的选择吗？

我对haskell很新，所以请说清楚。

Answer 1

关于你的第一个问题（为什么堆栈溢出）：

使用stack runhaskell（或等效的stack runghc）以特殊的“及时”编译模式运行代码，这与在GHCi提示符下输入的表达式运行方式非常相似。代码未被优化，并且经常表现出可怕的性能特征。

对于您的特定程序，这意味着它运行速度非常慢，内存占用不断扩大，最终会产生堆栈溢出。

如果您改为编译并运行：

stack ghc -- -O2 challenge5.hs
./challenge5

你会发现它运行得更快（在我的笔记本电脑上大约一分钟），在恒定的内存中，显然没有堆栈溢出。

如注释中所示，GHC中的堆栈溢出错误与尾递归实际上没有任何关系。相反，它源于懒惰评估的特定方面。 （例如，请参阅Do stack overflow errors occur in Haskell?。）

简而言之，GHC创建了“thunk”代表未评估的表达式，其价值可以在未来的点上得到满足。有时，这些thunk以长链的形式链接在一起，当需要链的一端的thunk的值时，链中的所有thunks需要“部分评估”到链的末尾在程序开始计算thunk值之前，获取最后一个thunk的值。 GHC在有限大小的堆栈中维护所有这些“正在进行的thunk评估”，并且可能溢出。

触发堆栈溢出的一个简单示例是：

-- Sum.hs
main = print $ sum [1..100000000]

如果你运行这个：

stack runhaskell -- Sum.hs      # using GHC version 8.0.2

你会得到：

Sum.hs: stack overflow

但是，使用ghc -O2编译它足以使问题消失（对于Sum.hs和原始程序）。其中一个原因可能是应用了“严格性分析”优化，这种优化可以提前推动th th，从而无法形成这些长链。

关于你的第二个问题（一个不可变数组是正确的方法）：

正如@WillNess指出的那样，使用未装箱的阵列取代盒装阵列可以带来巨大的性能提升：在我的笔记本电脑上，未装箱的代码版本在8秒内运行，而在63秒内运行。

然而，使用这种类型的算法 - 基本上，在向量的大量小变化中，以这样的方式进行变化，使得所做的变化取决于累积的先前变化的整个历史 - 你可以做得更好有一个可变数组。我有一个使用Data.Vector.Unboxed.Mutable的版本，它在0.12秒内运行第2部分，你应该能够通过Data.Array.Unboxed的可变无箱数组实现类似的性能。

Answer 2

如果导入Data.Array.Unboxed而不是Data.Array，并将数组声明为

    ....
        a :: UArray Int Int 
        a = listToArray l
    return a

或者什么，在getData，你将获得显着的加速，接近奇迹。

此外，您将不得不重新实现lengthArr = rangeSize . bounds，因此它适用于未装箱的阵列。