16

我想知道为什么

Prelude> head $ reverse $ [1..10000000] ++ [99]
99

不会导致堆栈溢出错误。前奏中的 ++ 似乎是直截了当且非尾递归的：

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

编辑：最初，我认为这个问题与前奏中定义 ++ 的方式有关，特别是与重写规则有关，因此问题继续如下。讨论告诉我，事实并非如此。我现在认为一些惰性求值效果会导致代码在没有堆栈溢出的情况下运行，但我不太清楚如何。

所以就这样，它应该会遇到堆栈溢出，对吧？所以我认为这可能与遵循 ++ 定义的 ghc 魔法有关：

{-# RULES "++" [~1] forall xs ys。xs ++ ys = 增加 (\cn -> foldr cn xs) ys #-}

*这有助于避免堆栈溢出吗？有人可以为这段代码中发生的事情提供一些提示吗？**

4

3 回答 3

9

前奏中的 ++ 似乎是直截了当且非尾递归的......所以就这样，它应该会遇到堆栈溢出，对吧？

在 Haskell 中，非尾递归通常比尾递归更好，因为非尾递归的东西可能是惰性的。您在那里列出的定义比尾递归的定义要好得多，因为尾递归的定义会继续递归并生成整个列表，即使您只需要第一个元素；而非尾递归只会做必要的工作。

于 2010-05-19T23:02:57.163 回答
8

这不会堆栈溢出 - 即使在没有优化和重写规则的解释器中 - 因为它不使用堆栈。

看(++)的定义，例如：

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

关键是x : (xs ++ ys)——也就是说，它是由 (:) "cons" 构造函数保护的递归。因为 Haskell 是惰性的，它为 cons 操作分配了一个 thunk，递归调用转到这个（堆分配的）thunk。所以你的堆栈分配现在是堆分配，它可以扩展很多。所以这一切都是遍历大列表，在堆上分配新的 cons 对象来替换它正在遍历的那些。简单的！

“反向”有点不同：

reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)

这是一个尾递归、累加器风格的函数，所以它会在堆上分配。

所以你看，这些函数依赖于在堆上使用 cons 单元，而不是在堆栈上，因此没有堆栈溢出。

要真正确定这一点，请查看 GC vm 的运行时统计信息：

$ time ./B +RTS -s
99

         833 MB total memory in use (13 MB lost due to fragmentation)
         Generation 0:  3054 collections,     0 parallel,  0.99s,  1.00s elapsed
         %GC time      82.2%  (85.8% elapsed)

这是你的大列表——它被分配在堆上，我们花费 80% 的时间清理由 (++) 创建的 cons 节点。

教训：你经常可以用栈换堆。

于 2010-05-31T04:59:53.177 回答
4

编辑：下面的答案是完全不相关的，如果不是完全错误的话。证明他实际上理解惰性评估的唐斯图尔特有正确的解释。

如果你运行ghc -ddump-simpl，你会看到正在使用的函数是GHC.Base.++和GHC.List.reverse。这些函数被设计为不会溢出大型列表上的堆栈。您在 Prelude 中看到的是“参考实现”，而不是实际编译的代码。

这是我从 GHC 源代码分发中挖出的一些代码：

reverse                 :: [a] -> [a]
#ifdef USE_REPORT_PRELUDE
reverse                 =  foldl (flip (:)) []
#else
reverse l =  rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x:a)
#endif

和这个：

(++) :: [a] -> [a] -> [a]
(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

{-# RULES
"++"    [~1] forall xs ys. xs ++ ys = augment (\c n -> foldr c n xs)     ys
  #-}

在第一种情况下，应该清楚发生了什么。第二，我对重写规则有点模糊......

于 2010-05-19T22:16:14.423 回答