Haskell尾递归如何工作？

Question

我写了这段代码，假设len是尾递归的，但仍然发生堆栈溢出。问题出在哪里？

myLength :: [a] -> Integer

myLength xs = len xs 0
    where len [] l = l
          len (x:xs) l = len xs (l+1)

main = print $ myLength [1..10000000]

- Hynek -Pichi- Vychodil

---

我想指出，这是一个非常好的问题。延迟求值具有有趣的副作用，可能不会立即为所有程序员所注意到。 - jrockway

在使用Haskell和其他非纯函数式语言进行编程时，你会意识到一些愚蠢的技巧，例如为了实现尾递归而进行的重写通常是不必要的甚至有害的。相反，你应该将精力集中在真正需要评估的内容上。 - ephemient

Answer 1

请记住，Haskell是一种惰性语言。只有在绝对必要时才会执行计算(l+1)。

“简单”的解决方案是使用'$!'来强制求值：

myLength :: [a] -> Integer
myLength xs = len xs 0
where len [] l = l
      len (x:xs) l = len xs $! (l+1)

      main = print $ myLength [1..10000000]

- eelco

Answer 2

似乎是因为懒惰，导致len构建了thunk：

len [1..100000] 0
-> len [2..100000] (0+1)
-> len [3..100000] (0+1+1)

等等等。你必须强制使用len每次减少l：

len (x:xs) l = l `seq` len xs (l+1)

欲了解更多信息，请查看http://haskell.org/haskellwiki/Stack_overflow。

- mattiast

---

嘿，我找到了，它强制 l 在下一次递归 thunk 中进行评估，因此在下一个 len 应用之前会评估 (l+1)。这并不容易阅读和理解。 - Hynek -Pichi- Vychodil

实际上，该页面链接到一个完全回答了这个问题的页面：http://haskell.org/haskellwiki/Performance/Accumulating_parameter。 - slim

Answer 3

foldl存在同样的问题，它会构建一个thunk。您可以使用Data.List中的foldl'来避免这个问题：

import Data.List
myLength = foldl' (const.succ) 0

foldl和foldl'唯一的区别是严格累加，因此foldl'解决了与上述seq和$!示例相同的问题。 (const.succ)与(\a b -> a+1)的作用相同，尽管succ具有更少的限制性类型。

- Yann Vernier

Answer 4

您的问题的最简单解决方案是开启优化。

我已经将您的源代码放在名为tail.hs的文件中。

jmg$ ghc --make tail.hs -fforce-recomp
[1 of 1] Compiling Main             ( tail.hs, tail.o )
Linking tail ...
jmg$ ./tail 
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
girard:haskell jmg$ ghc -O --make tail.hs -fforce-recomp
[1 of 1] Compiling Main             ( tail.hs, tail.o )
Linking tail ...
jmg$ ./tail 
10000000
jmg$ 

@Hynek -Pichi- Vychodil 以上测试是在Mac OS X Snow Leopard 64位操作系统上使用GHC 7和GHC 6.12.1进行的，每个版本都是32位的。在您downvote之后，我在Ubuntu Linux上重复了这个实验，结果如下：

jmg@girard:/tmp$ cat length.hs
myLength :: [a] -> Integer

myLength xs = len xs 0
    where len [] l = l
          len (x:xs) l = len xs (l+1)
main = print $ myLength [1..10000000]
jmg@girard:/tmp$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.12.1
jmg@girard:/tmp$ uname -a
Linux girard 2.6.35-24-generic #42-Ubuntu SMP Thu Dec 2 02:41:37 UTC 2010 x86_64 GNU/Linux
jmg@girard:/tmp$ ghc --make length.hs -fforce-recomp
[1 of 1] Compiling Main             ( length.hs, length.o )
Linking length ...
jmg@girard:/tmp$ time ./length 
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.
real    0m1.359s
user    0m1.140s
sys 0m0.210s
jmg@girard:/tmp$ ghc -O --make length.hs -fforce-recomp
[1 of 1] Compiling Main             ( length.hs, length.o )
Linking length ...
jmg@girard:/tmp$ time ./length 
10000000
real    0m0.268s
user    0m0.260s
sys 0m0.000s
jmg@girard:/tmp$ 

因此，如果您有兴趣，我们可以继续找出为什么这对您失败的原因。我猜，如果这种直接递归列表的方式不能在这种情况下被优化成有效的循环，那么GHC HQ将会把它视为一个bug。

- jmg

---

它在版本6.12.1中使用我的问题代码失败 $ ghc -O --make length.hs -fforce-recomp [1 of 1] Compiling Main (length.hs, length.o) Linking length ... hynek@hynek:~/work/haskell$ ./length 栈空间溢出：当前大小为8388608字节。使用+RTS-Ksize-RTS'来增加它。 - Hynek -Pichi- Vychodil

Answer 5

你知道吗，有一种更简单的方法来编写这个函数：

myLength xs = foldl step 0 xs where step acc x = acc + 1

Alex

- Alex Fort

---

myLength = foldl (+) 0也是一样的，尽管需要更复杂的推理来证明它。优化器会使其高效，因此无需显式地进行尾递归。 - luqui

你是不对的：*Main> foldl (+) 0 [1..1000000]*** 异常：堆栈溢出 - Hynek -Pichi- Vychodil

还有错误的结果，你把列表求和了，应该是*Main> foldl (+) 0 [1..10] => 55 - Hynek -Pichi- Vychodil

可以使用foldl'来解决这个问题，它是foldl的严格版本。 - mattiast

Answer 6

eelco.lempsink.nl回答了你提出的问题。这是Yann答案的演示：

module Main
    where

import Data.List
import System.Environment (getArgs)

main = do
  n <- getArgs >>= readIO.head
  putStrLn $ "Length of an array from 1 to " ++ show n
               ++ ": " ++ show (myLength [1..n])

myLength :: [a] -> Int
myLength = foldl' (const . succ) 0

foldl' 从左到右遍历列表，每次将 1 加到从 0 开始的累加器中。

这是运行程序的示例：

---

C:\haskell>ghc --make Test.hs -O2 -fforce-recomp
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking Test.exe ...

C:\haskell>Test.exe 10000000 +RTS -sstderr
Test.exe 10000000 +RTS -sstderr

Length of an array from 1 to 10000000: 10000000
     401,572,536 bytes allocated in the heap
          18,048 bytes copied during GC
           2,352 bytes maximum residency (1 sample(s))
          13,764 bytes maximum slop
               1 MB total memory in use (0 MB lost due to fragmentation)

  Generation 0:   765 collections,     0 parallel,  0.00s,  0.00s elapsed
  Generation 1:     1 collections,     0 parallel,  0.00s,  0.00s elapsed

  INIT  time    0.00s  (  0.00s elapsed)
  MUT   time    0.27s  (  0.28s elapsed)
  GC    time    0.00s  (  0.00s elapsed)
  EXIT  time    0.00s  (  0.00s elapsed)
  Total time    0.27s  (  0.28s elapsed)

  %GC time       0.0%  (0.7% elapsed)

  Alloc rate    1,514,219,539 bytes per MUT second

  Productivity 100.0% of total user, 93.7% of total elapsed


C:\haskell>

- Michael Steele