Haskellの末尾再帰はどのように機能しますか？
https://stackoverflow.com/questions/412919
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
このコードスニペットを作成し、 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]
解決
Haskellは怠zyであることを思い出してください。計算（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]
他のヒント
遅延が原因で len がサンクを構築するようです：
len [1..100000] 0
-> len [2..100000] (0+1)
-> len [3..100000] (0+1+1)
など。毎回 l を減らすように len を強制する必要があります：
len (x:xs) l = l `seq` len xs (l+1)
詳細については、 http://haskell.org/haskellwiki/Stack_overflow をご覧ください。
>foldlにも同じ問題があります。サンクを構築します。 Data.Listのfoldl 'を使用して、この問題を回避できます。
import Data.List
myLength = foldl' (const.succ) 0
foldlとfoldl 'の唯一の違いは厳密な累積であるため、foldl'はseqおよび$！と同じ方法で問題を解決します。上記の例。 （const.succ）は、ここでは（\ a b-＆gt; a + 1）と同じように機能しますが、succのタイプはそれほど制限されていません。
問題の最も簡単な解決策は、最適化を有効にすることです。
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 上記のテストは、それぞれ32ビットバージョンのGHC 7およびGHC 6.12.1を搭載したMac OS X Snow Leopard 64ビットで実行されました。あなたがダウン票を投じた後、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は、リストに対するこのような単純な再帰がこの場合に効率的なループに最適化されていない場合、バグとして受け入れると思います。
ご存知のように、この関数を作成するはるかに簡単な方法があります：
myLength xs = foldl step 0 xs where step acc x = acc + 1
アレックス
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 'は、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>
