haskell - 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]

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]

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。

Answer 3

foldl 也有同样的问题；它建立了一个thunk。您可以使用 Data.List 中的 foldl' 来避免该问题：

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

foldl 和 foldl' 唯一的区别是严格的累加，所以 foldl' 解决问题的方式与 seq 和 $! 上面的例子。(const.succ) 这里的工作方式与 (\ab -> a+1) 相同，但 succ 的类型限制较少。

Answer 4

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

我在一个名为 tail.hs 的文件中有你的源代码。

jmg$ ghc --make tail.hs -fforce-recomp
[1 of 1] 编译 Main (tail.hs, tail.o)
连接尾...
jmg$ ./尾
堆栈空间溢出：当前大小 8388608 字节。
使用`+RTS -Ksize -RTS'来增加它。
girard:haskell jmg$ ghc -O --make tail.hs -fforce-recomp
[1 of 1] 编译 Main (tail.hs, tail.o)
连接尾...
jmg$ ./尾
10000000
jmg$

@Hynek -Pichi- Vychodil 上面的测试是在 Mac OS X Snow Leopard 64bit 上完成的，带有 GHC 7 和 GHC 6.12.1，每个都是 32 位版本。在你投反对票后，我在 Ubuntu Linux 上重复了这个实验，结果如下：

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

我的长度 xs = 长度 xs 0
    其中 len [] l = l
          长度 (x:xs) l = 长度 xs (l+1)

主 = 打印 $ myLength [1..10000000]

jmg@girard:/tmp$ ghc --version
Glorious Glasgow Haskell 编译系统，版本 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] 编译 Main (length.hs, length.o)
连接长度...
jmg@girard:/tmp$ 时间 ./length
堆栈空间溢出：当前大小 8388608 字节。
使用`+RTS -Ksize -RTS'来增加它。

真实0m1.359s
用户 0m1.140s
系统 0m0.210s
jmg@girard:/tmp$ ghc -O --make length.hs -fforce-recomp
[1 of 1] 编译 Main (length.hs, length.o)
连接长度...
jmg@girard:/tmp$ 时间 ./length
10000000

实际0m0.268s
用户 0m0.260s
系统 0m0.000s
jmg@girard:/tmp$

因此，如果您有兴趣，我们可以继续找出原因，这对您来说失败了。我猜，GHC HQ 会接受它作为一个错误，如果在这种情况下没有将这种对列表的直接递归优化为一个有效的循环。

Answer 5

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

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

亚历克斯

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>