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會接受它作爲一個錯誤，如果這種直接向列表的遞歸在這種情況下沒有被優化成一個有效的循環。