如何Haskell尾recursion工作？

我写了这段代码，我假设len是尾recursion的，但仍然会发生堆栈溢出。 哪里不对？

 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

似乎懒惰导致lenbuild立thunk：

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

等等。 你必须每次强制len减lessl ：

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

有关更多信息，请参阅http://haskell.org/haskellwiki/Stack_overflow 。

Answer 3

褶皱带有同样的问题; 它build立了一个thunk。 您可以使用Data.List中的foldl来避免这个问题：

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

foldl和foldl'之间的唯一区别是严格的积累，所以foldl以和seq和$相同的方式解决问题！ 上面的例子。 （const.succ）在这里和（\ ab – > a + 1）是一样的，虽然succ有一个限制较less的types。

Answer 4

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

我有一个叫做tail.h的文件

 jmg $ ghc --make tail.hs -fforce-recomp
 [1 of 1]编译Main（tail.hs，tail.o）
连接尾巴...
 jmg $ ./tail 
堆栈空间溢出：当前大小为8388608字节。
使用'+ RTS -Ksize -RTS'来增加它。
 girard：haskell jmg $ ghc -O  - 生成tail.hs -fforce-recomp
 [1 of 1]编译Main（tail.hs，tail.o）
连接尾巴...
 jmg $ ./tail 
千万
 JMG $ 

@Hynek -Pichi- Vychodil上面的testing是在Mac OS X Snow Leopard 64bit上完成的，GHC 7和GHC 6.12.1都是32位版本。 在你失败后，我在Ubuntu Linux上重复了这个实验，结果如下：

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

 myLength xs = len xs 0
    其中len [] l = l
           len（x：xs）l = len xs（l + 1）

 main = print $ myLength [1..10000000]

 jmg @ girard：/ tmp $ ghc --version
格拉斯哥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 $ time ./length 
堆栈空间溢出：当前大小为8388608字节。
使用'+ RTS -Ksize -RTS'来增加它。

真正的0m1.359s
用户0m1.140s
 sys 0m0.210s
 jmg @ girard：/ tmp $ ghc -O --make length.hs -fforce-recomp
 [1 of 1]编译Main（length.hs，length.o）
链接长度...
 jmg @ girard：/ tmp $ time ./length 
千万

实际0m0.268s
用户0m0.260s
 sys 0m0.000s
 JMG @吉拉德：/ tmp目录$ 

所以，如果你有兴趣，我们可以继续找出是什么原因，这对你来说是失败的。 我想GHC HQ会接受它作为一个bug，如果这样一个简单的列表recursion在这种情况下没有被优化成一个有效的循环。

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>