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サンクを構築する原因のようです：

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 にも同じ問題があります。それはサンクを構築します。その問題を回避するには、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/1] Main のコンパイル ( tail.hs、tail.o )
しっぽをつないで……
jmg$ ./テール
スタック スペースのオーバーフロー: 現在のサイズは 8388608 バイトです。
それを増やすには、「+RTS -Ksize -RTS」を使用します。
girard:haskell jmg$ ghc -O --make tail.hs -fforce-recomp
[1/1] Main のコンパイル ( tail.hs、tail.o )
しっぽをつないで……
jmg$ ./テール
10000000
jmg$

@Hynek -Pichi- Vychodil 上記のテストは、それぞれ 32 ビット バージョンの GHC 7 および GHC 6.12.1 を搭載した Mac OS X Snow Leopard 64 ビットで行われました。あなたが反対票を投じた後、Ubuntu Linuxでこの実験を繰り返し、次の結果を得ました。

jmg@girard:/tmp$ 猫の長さ.hs
myLength :: [a] -> 整数

myLength xs = 長さ xs 0
    ここで、len [] l = l
          長さ (x:xs) l = 長さ xs (l+1)

main = print $ myLength [1..10000000]

jmg@girard:/tmp$ ghc --バージョン
The Glorious Glasgow Haskell Compilation System、バージョン 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/1] Main のコンパイル ( length.hs、length.o )
連結長さ...
jmg@girard:/tmp$ time ./length
スタック スペースのオーバーフロー: 現在のサイズは 8388608 バイトです。
それを増やすには、「+RTS -Ksize -RTS」を使用します。

実質 0m1.359s
ユーザー 0m1.140s
システム 0m0.210s
jmg@girard:/tmp$ ghc -O --make length.hs -fforce-recomp
[1/1] Main のコンパイル ( length.hs、length.o )
連結長さ...
jmg@girard:/tmp$ time ./length
10000000

実質 0m0.268s
ユーザー 0分0.260秒
システム 0m0.000s
jmg@girard:/tmp$

したがって、興味がある場合は、これが失敗した理由を引き続き調べることができます。この場合、リストに対するそのような単純な再帰が効率的なループに最適化されていない場合、GHC HQはそれをバグとして受け入れると思います。

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'は、0から始まるアキュムレータに1を追加するたびに、リストを左から右に調べます。

プログラムの実行例は次のとおりです。

---

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

ご存知のように、この関数を記述するはるかに簡単な方法があります。

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

アレックス