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是懒惰的。你的计算（1 + 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

只要你知道，有写这个功能更简单的方法：

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

亚历

Answer 4

的与foldl携带同样的问题;它构建了一个thunk。你可以用与foldl“从Data.List模块，以避免这样的问题：

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

与foldl和与foldl之间唯一的区别”是严格的积累，因此foldl”以同样的方式作为序列和$解决问题！上面的例子。 （const.succ）与（\ a b - > a + 1）的作用相同，但succ的限制较少。

Answer 5

eelco.lempsink.nl回答你问的问题。这里的晏的回答示范：

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> 

Answer 6

最简单的解决方案就是开启优化。

我有一个叫做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雪豹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会接受它作为一个错误，如果这种直接向列表的递归在这种情况下没有被优化成一个有效的循环。